Introduction générale
D
E nos jours, aussi bien dans l'industrie que dans les
laboratoires de recherche, la puissance de calcul est de plus en plus
recherchée pour l'exécution d'applications de plus en plus
gourmandes en ressources. Par exemple dans l'industrie cinématographique
la puissance de calcul est employée
pour du calcul d'image. Dans des laboratoires de biologie,
elle peut être employée pour des calculs d'affinité
génétique entre différentes familles d'animaux. Dans tous
les cas, l'objectif est d'exécuter les applications le plus rapidement
possible, c'est-à-dire réduire le temps entre la soumission de
l'application et l'obtention des résultats. C'est cela qu'on appelle le
calcul à haute performance (HPC - High Performance Computing). Dans les
années quatre-vingt à quatre-vingt dix, ce dernier s'appuyait sur
des solutions coûteuses, basées sur des processeurs et des
logiciels spécialisés, et destinés à un nombre
limité de domaines tels que la météorologie, les
phénomènes physiques, le nucléaire etc.. Cela exigeait que
les centres de recherche disposent d'une puissance de calcul sans cesse
croissante, qui n'était pas accessible financièrement à
des organisations moyennes. L'évolution technologique permet aujourd'hui
de disposer d'ordinateurs de bureau standard très performants à
tel point qu'il est envisageable de construire à partir de ces machines
des systèmes parallèles aussi rapides que les supercalculateurs
dédiés type CRAY, IBM SP, NEC, Fujitsi. Chaque progression
technologique ouvre l'horizon à de nouveaux besoins; et de nouvelles
exigences. En effet, les applications deviennent de plus en plus gourmandes en
temps de calcul et en espace mémoire.
Le calcul parallèle a toujours été une
possibilité de répondre à cette demande de performances.
Il consiste en l'exécution d'un traitement pouvant être
partitionné en tâches élémentaires adaptées
afin de pouvoir être réparties entre plusieurs processeurs
opérant simultanément. L'objectif est de traiter des
problèmes de grandes tailles plus rapidement que dans une
exécution séquentielle. Les avantages du calcul parallèle
sont nombreux. Du fait de contraintes physiques et technologiques, la puissance
d'un ordinateur monoprocesseur reste limitée. En effet, il est difficile
pour les fabricants de processeurs de produire des processeurs dont la
puissance atteigne les centaines de MégaFlops1. La
quantité de mémoire présente dans les ordinateurs
monoprocesseurs est également limitée et il est par
conséquent impossible d'exécuter certaines applications de grande
taille sur de telles machines. Le calcul parallèle peut en revanche
permettre de résoudre ce genre de problème. Ainsi, les machines
parallèles actuelles utilisent des techniques originales de calcul
parallèle pour maintenir l'activité des unités de
calcul.
Les machines peuvent, par exemple disposer d'une
mémoire partagée physique pour permettre aux différentes
unités de calcul de coopérer. Dans d'autres cas, les machines
parallèles sont construites
'million d'opérations ou calcul par seconde en
virgule flottante
autour d'unités de calcul dotées de leur propre
mémoire. Ces unités communiquent par échange de messages;
on parle ici de machine à mémoire distribuée. Aujourd'hui,
on assiste au développement rapide des machines parallèles de ce
type: les grappes. Elles sont construites à partir de l'interconnexion
de composants standards donc bon marché, comme les stations de travail
ou les ordinateurs (PC). Ces architectures pouvant être
constituées de plusieurs centaines de processeurs, offrent des
performances potentiellement exceptionnelles pour un prix modeste. Avec
l'avènement du logiciel libre et le coût assez bas des ordinateurs
de bureau, la très forte demande en calcul haute performance
(scientifique et technique) peut être satisfaite à un coût
raisonnable. Les grappes de PC apparaissent donc comme une très bonne
alternative aux moyens de calculs traditionnels. Cependant, leur exploitation
reste très délicate et pose encore de très nombreux
problèmes.
La programmation sur ce type de machines demande beaucoup plus
d'efforts que l'écriture d'un programme séquentiel pour plusieurs
raisons:
- Peu d'équipes sont capables de développer et de
maîtriser l'environnement de grappe.
- l'hétérogénéité de la grappe
au niveau des ressources de calcul (processeur) et au niveau des
capacités de communication (réseau) contraint
l'utilisateur de monter lui même son système
afin d'adapter l'exécution des applications sur ce
système.
- La programmation dépend fortement de la machine cible
et de son support au parallélisme. Par exemple, les processeurs d'une
machine parallèle peuvent avoir des propriétés distinctes,
telles que le mode d'échange des données (mémoire
partagée ou distribuée via un réseau d'interconnexion), de
même que la cadence de son mode de fonctionnement.
L'environnement de grappes hétérogènes
admet donc une complexité liée à l'application que l'on
veut exécuter en termes de graphe de tâches (dépendances),
à la topologie du système (communications entre les noeuds via le
réseau), aux ressources disponibles dans le système (processeurs,
mémoire). Il est donc capital de tenir en compte ces différents
paramètres pour pouvoir exécuter efficacement une application sur
une plate-forme hétérogène.
Il est question pour nous de proposer un algorithme
d'ordonnancement efficace de tâches d'une application en tenant compte de
ces éléments.
L'élaboration des applications
parallèles
Dans l'informatique séquentielle, l'écriture
d'une application consiste à choisir un algorithme qui
résout un problème et de faire son analyse. Pour concevoir une
application parallèle, nous devons d'abord choisir un algorithme qui
résout le problème envisagé. Cet algorithme est alors
partitionné en tâches lesquelles correspondent à
des portions du code qui seront exécutées en séquentiel.
Ensuite, le programme parallèle est conçu en attribuant à
chaque tâche un processeur et une date d'exécution. La performance
de l'application est mesurée alors par le temps d'exécution
parallèle. Si une tâche a besoin des données produites par
une autre tâche, il existe une relation de dépendance. Les
tâches et leurs relations de dépendance sont
représentées sous la forme d'un graphe, où les sommets
correspondent aux tâches et les arcs aux relations de
précédence entre elles. Ce graphe exprime le degré de
parallélisme de l'algorithme et est nommé graphe de
précédence ou de tâches. L'opération qui
attribue aux tâches des dates d'exécution et des processeurs est
dénommée ordonnancement, elle sera présentée en
détail au chapitre 3.
Il est clair qu'il faut distinguer la phase d'extraction du
parallélisme d'un algorithme de la phase d'exploitation de ce
parallélisme. Dans un premier temps un graphe de
précédence est construit, et ensuite un schéma
d'ordonnancement est appliqué en fonction de l'architecture du
modèle de machine. Or, pour certains problèmes, le graphe de
précédence est construit au cours de l'exécution. Dans ce
cas, les deux étapes ne peuvent pas être dissociées dans le
temps.
Nous nous intéressons aux problèmes où le
graphe de précédence est fourni de façon explicite avant
le début de l'exécution (ordonnancement statique). Dans ces
problèmes d'ordonnancement notre objectif est de minimiser le temps
d'exécution total encore appelé makespan.
Problématique
La répartition des calculs et des données est
l'un des problèmes majeurs à résoudre pour réaliser
une application parallèle efficace. Il faut décider de la date et
du lieu d'exécution des calculs du programme parallèle sur
l'ensemble des ressources (processeur, mémoire..) de la machine.
L'efficacité de l'exécution va dépendre de ces
décisions. Dans ce mémoire, nous nous attachons à
décrire le modèle de coût de notre grappe et de proposer
une solution au problème d'ordonnancement de tâches d'une
application sur une grappe hétérogène.
Organisation du travail
Ce document est divisé en quatre chapitres : le premier
nous introduit à l'architecture des grappes et au calcul
parallèle en présentant de manière concise les
différents types d'architectures parallèles d'après la
classification de Flynn et de l'évolution des grappes de PCs. Ce
chapitre est l'occasion pour nous d'insister sur l'architecture de grappes
hétérogènes notamment sur leurs caractéristiques
matérielles, logicielles et sur
l'hétérogénéité qui les rend plus complexes.
Il parle également de la notion de programmation sur ces types
d'architecture et de certains standards de programmation d'applications
parallèles dont MPI qui nous intéresse. Ce standard est la cible
d'un nombre impressionnant dans le monde et est doté des
caractéristiques favorables aux grappes
hétérogènes. Comment analyser les performances d'une
application parallèle a été la question répondue
après avoir présenté des postulats existants. La
représentation d'une application parallèle en graphe de
tâches, l'ordonnancement de ces dernières suivant les
modèles de communication font l'objet du deuxième chapitre.
L'étude des éléments définis aux chapitres
précédents nous permet de formuler au chapitre 3 un modèle
d'ordonnancement sur grappes hétérogènes en tenant compte
de ses caractéristiques. Le chapitre 4 est la partie pratique de notre
contribution car il expose l'implémentation de notre modèle en
effectuant des évaluations sur un exemple. Nous concluons ensuite ce
travail et apportons des perspectives pour la suite de nos recherches.
| 
