Travail d'étude et de recherche

Maîtrise d'Informatique

Algorithmes de pliage pour le problème d'ordonnancement

Encadrements : 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 [#!violet!#], 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}$.

Dans les problèmes d'ordonnancement, nous pouvons considérer deux types de problèmes :

• le problème avec un nombre illimités de machines ou processeurs
• le problème avec un nombre limités de machines

Dans ce stage nous nous intéressons aux deuxième problème c'est-à-dire à l'ordonnancement de tâches unitaires ( $\forall i \in V, ~ p_i=1$) et des durées unitaires ( $\forall (i,j) \in E, c_{ij}=1$) sur un nombre limité de machines.

Lorsqu'on étudie un problème d'ordonnancement sur un nombre limité de machines, deux approches sont possibles :

• La première consiste a prendre en compte le fait que l'on travaille sur un nombre limité de machines,
• La deuxième consiste a travaillé sur un nombre illimité de machines et enseuite utilisé un algorithme de pliage pour effectuer le passage sur un nombre limité.

Dans ce stage, nous considérons la deuxième approche. Vous devrez programmer les trois algorithmes de pliages suivants et faire une évaluation statistiques des résultats obtenus.

• Le pliage simple [#!aussois!#],
• Le pliage basé sur la notion de fils favorit [#!munier!#],
• Le pliage évolué.

Pour plus de détail veuillez me contacter : rgirou@lirmm.fr