Travail d'étude et de recherche

Maîtrise d'Informatique

Algorithmes de listes sur les problèmes d'ordonnancement

Encadrements : J.C. König (LIRMM), R. Giroudeau(LIRMM)

L'utilisation du parallélisme pour le traitement des applications de grande taille qui réclament une puissance de calcul de plus en plus importante est aujourd'hui une réalité. Néanmoins, les puissances de calcul théoriques des machines parallèles ne sont, en pratique, jamais atteintes. Ceci est dû principalement aux difficultés liées à la gestion des ressources et des contraintes de fonctionnement des architectures multiprocesseurs. Parmi les difficultés que l'on rencontre, on peut citer l'étape d'extraction du parallélisme intrinsèque d'une application ou les problèmes de routage et d'ordonnancement des communications entre les différents processeurs de l'architecture.

Pour tenter de pallier la première difficulté, une phase de partitionnement est nécessaire. Elle correspond à la première étape fondamentale de la parallélisation et consiste en l'extraction du parallélisme potentiel d'une application.

L'extraction du parallélisme détermine les dépendances fonctionnelles entre les parties de l'application. Ainsi, une application parallèle peut être représentée sous forme d'un graphe orienté sans cycle (graphe de précédence) où chaque sommet du graphe représente une partie (instruction ou ensemble d'instructions) du programme et les arcs les contraintes chronologiques entre ces parties (dites aussi contraintes de précédence). Dans le modèle avec communications homogènes [2], nous pouvons distinguer deux types de communications :

• les communications intra-processeurs : ce sont les communications entre deux tâches adjacentes dans le graphe de précédence, qui s'exécutent sur le même processeur (en respectant les contraintes de précédence). Nous supposerons ces délais négligeables.

• les communications inter-processeurs : ce sont les communications entre deux tâches adjacentes dans le graphe de précédence qui s'exécutent sur des processeurs différents.

Formellement, nous considérons un graphe orienté sans cycle $G=(V,E)$ avec $V$ l'ensemble des sommets et $E$ l'ensemble des arcs. Chaque tâche $i \in V$ a une durée d'exécution de $p_i$ et à chaque arc $(i,j)$ est associé un délais de communications $c_{ij}$. Soit $t_i$ (resp. $t_j$) la date de début d'exécution de la tâche $i$ (resp. $j$), alors si $i$ et $j$ sont exécutées sur le même processeur alors nous avons $t_j \geq t_i+p_i$, sinon si elles sont exécutées sur des processeurs différents, nous avons $t_j \geq t_i+p_i+c_{ij}$.

Le stage consiste dans un premier temps d'appliquer dans le cas du modèle homogène, des heuristiques comme $LS$ (List scheduling), $LPT$ (Large processing time), $\ldots$, pour le problème d'ordonnancement sans communication dans un premier temps (c'est à dire $c_{ij}=0, \forall (i,j) \in E$), avec des tâches indépendantes sur un nombre de machines fixé. Ces heuristiques pouront être étendues dans un premier temps en introduisant des communications et dans un second temps au modèle avec des communications hiérarchiques qui est défini ci-après.

Ces dernières années, un regain d'intérêt se manifeste pour le calcul parallèle dû en grande partie à l'utilisation de plus en plus croissante des réseaux de stations de travail (NOW : network of workstations) [4,1] comme machines parallèles. En effet, il y a quelques années les seules machines parallèles proposées par les fabricants de super-calculateurs étaient des machines massives et d'un coût élevé nécessitant des besoins humains importants pour l'exploitation de leur puissance de calcul. L'utilisation des réseaux de stations de travail comme machines parallèles semble être une réponse adéquate aux contraintes économiques et aux besoins des utilisateurs pour une puissance de calcul de plus en plus importante.

Dans le modèle avec communications hiérarchiques [3] que nous proposons, nous pouvons distinguer trois types de communications :

• les communications intra-processeurs : identiques à celles du modèle avec communications homogènes.

• les communications intra-modulaires (ou intra-clusters) : ce sont les communications entre deux tâches adjacentes dans le graphe de précédence qui s'exécutent sur le même cluster mais sur des processeurs différents. Ces communications seront notées par la suite $\epsilon_{ij}$.

• les communications extra-modulaires (ou extra-clusters) : elles sont introduites dans le cas où deux tâches adjacentes dans le graphe de précédence sont ordonnancées sur des modules différents. Ce sont des communications de coût supérieur par rapport aux communications intra-modulaires, et elles seront notées par la suite $c_{ij}$.

Formellement, nous considérons un graphe orienté sans cycle $G=(V,E)$ avec $V$ l'ensemble des sommets et $E$ l'ensemble des arcs. Chaque tâche $i \in V$ a une durée d'exécution de $p_i$ et à chaque arc $(i,j)$ est associé un couple de délais de communications $(c_{ij},\epsilon_{ij})$. Soit $t_i$ (resp. $t_j$) la date de début d'exécution de la tâche $i$ (resp. $j$), alors si $i$ et $j$ sont exécutées sur le même module et sur le même processeur alors nous avons $t_j \geq t_i+p_i$, sinon si elles sont exécutées sur des processeurs différents du même module, alors $t_j \geq t_i+p_i+\epsilon_{ij}$. Dans le cas où les tâches sont exécutées sur des modules différents nous avons $t_j \geq t_i+p_i+c_{ij}$.

Cette extension du modèle classique est appelée par la suite le modèle à communications hiérarchiques.

Clairement, le modèle à communications hiérarchiques est une généralisation du modèle à communications homogènes puisque si pour toutes les tâches $i$ et $j$ adjacentes dans le graphe de précédence nous avons $\epsilon_{ij}=c_{ij}$ alors, le modèle hiérarchique est identique au modèle avec communications homogènes.