Conclusion
Il n'est pas toujours utile de paralléliser une
application car elle peut fournir un temps inférieur au temps
séquentiel. C'est le cas dans notre exemple avec la matrice de taille
100. La parallélisation de notre exemple pour les tailles 1000, 3000,
5000 et 8000 améliore le temps séquentiel selon que le nombre de
processus ne dépasse pas 25 sinon l'algorithme séquentielle est
préférable. Ceci nous amène à dire que dans une
grappe hétérogène, augmenter le nombre de processeurs
n'améliore pas nécessairement le temps de calcul. En plus,
l'hétérogénéité ne permet pas d'avoir des
performances stables, elles varient beaucoup. En effet,
l'accélération n'implique pas forcément une bonne
efficacité. Pour avoir une bonne efficacité sur une telle grappe,
il faudrait ordonnancer convenablement en tenant compte de toutes ses
caractéristiques et de toutes les caractéristiques de
l'application.
Conclusion générale et perspectives
Rappel des objectifs
Le problème d'ordonnancement est un problème
complexe. Il est encore plus difficile lorsque l'on veut l'appliquer sur une
grappe de ressources non uniformes. Il a été question pour nous
dans ce travail de proposer un modèle d'ordonnancement de tâches
issues d'une application parallèle sur une grappe de calcul
hétérogène. Car il a été constaté que
la majorité des travaux sur l'ordonnancement s'applique sur les grappes
homogènes c'est à dire des grappes constitués de machines
identiques interconnectées par réseau uniforme. Dans certains,
des éléments indispensables comme la pile réseau pour
évaluer le coût sont négligés. Or les grappes
homogènes limitent le passage à l'échelle ce qui n'est pas
le cas pour les clusters hétérogènes qui nous permettent
d'avoir n'importe quel type de ressources de calcul mis ensemble pour fournir
une certaine puissance de calcul. Cependant beaucoup de contraintes
liées à l'hétérogénéité
existent dans ce type d'architecture puisque les différents modules
processeurs/mémoires sont différents, les liens d'interconnexion
aussi pour ne citer que ceux-là. Pour parvenir à nos objectifs,
nous avons d'abord fait une revue de la littérature; une revue qui
devait nous permettre d'une part d'étudier les différents types
d'architectures parallèles existantes et leur fonctionnement, d'autre
part comprendre les principes et concepts du calcul parallèle ainsi que
de l'ordonnancement des tâches. Ensuite, il a été question
pour nous d'extraire de la littérature des éléments
nécessaires sur ce qui a déjà été fait
jusqu'aujourd'hui pour constituer notre modèle de base pour allouer les
processeurs aux tâches et leur date de début d'exécution
bien sûr sur une grappe quelconque non homogène. Enfin,
après avoir installé une grappe de manière
matérielle et logicielle nous avons évalué ses
performances telles que décrite dans le modèle sur un exemple
d'application.
Bilan et évaluation du travail
réalisé
Pour une bonne compréhension de ce qui a été
fait, il importe que nous présentons d'une part le bilan du travail qui
a été réalisé et d'autre part que nous essayons de
l'évaluer.
Bilan
Ici, il est question pour nous de revenir sur tout ce qui a
été fait tout au long de notre travail. En effet nous avons
divisé notre travail en cinq principaux chapitres.
Le premier chapitre traite du calcul parallèle et de
l'architecture des grappes de calcul. Il a été question pour nous
de décrire les raisons qui incitent à faire du calcul en
parallèle et quels sont ses fondements. En effet le calcul
parallèle est un moyen pour fournir de la haute puissance de calcul
à un prix raisonnable en utilisant des ordinateurs standards. Son
efficacité dépend fortement de la programmation sou jacente qui
consiste à répartir les tâches sur plusieurs processeurs,
à repartir les données des problèmes de grande taille qui
satureraient la mémoire d'un seul ordinateur et de recouvrir les calculs
et les opérations d'entrées-sorties. Nous avons fait ressortir
deux types d'applications : statiques et dynamiques ainsi que
deux types de parallélisme explicites et implicites
qui sont des notions qui nous ont été utiles dans la suite.
Egalement, nous avons distingué les différentes architectures
parallèles décrites selon la classification de Flynn et
expliqué leurs modes de fonctionnement. De cette taxonomie, nous avons
extrait notre architecture qui est la grappe de calcul. Calculer les
critères de performances d'une application parallèle qui sont
l'accélération et l'efficacité ont fait
l'objet de la dernière section de ce chapitre.
Le second chapitre a traité essentiellement des
concepts de l'ordonnancement. L'ordonnancement est le fait d'allouer aux
processeurs des tâches et la date de début de l'exécution
de ces dernières. Il a été question pour nous de
présenter comment représenter une application parallèle
sous forme de graphe de tâches : les sommets sont les tâches, les
arêtes sont les synchronisations entre les tâches. Après
avoir défini la notion d'ordonnancement, nous avons
présenté les modèles classiques d'ordonnancement et les
modèles d'exécution pour ces ordonnancements. Il en est ressorti
que pour avoir des performances optimales, les éléments de
coût comme le surcoût induit par la pile réseau
nécessaire pour une grappe devait être négligée
ainsi que la congestion du réseau.
L'objet du troisième chapitre a été de
modéliser formellement un ordonnancement sur une grappe
hétérogène en tenant compte des éléments de
coût tels que les stations de travail qui peuvent avoir des
caractéristiques différentes, les éléments
d'interconnexion ( concentrateurs, commutateurs, routeurs ) utilisés
pour interconnecter les stations de travail qui ont des modes de fonctionnement
distincts l'un de l'autre, la pile réseau qui induit un surcoût
non négligeable puisqu'une trame doit parcourir toutes les couches avant
de quitter la machine source ainsi qu'à l'arrivée à la
machine de destination. A l'issue de cela, nous avons caractérisé
une grappe hétérogène en utilisant un modèle de
graphe où les sommets sont les stations de travail
caractérisées par leur puissance, leur capacité
mémoire, l'impact du protocole réseau et les arcs sont les liens
réseau caractérisés par leurs latences et leurs
débits.
L'ordonnancement sera donc constitué du graphe
représentant l'architecture et du graphe représentant
l'application parallèle. Nous avons aussi modéliser les
communications entre les tâches de l'application en tenant compte des
éléments de coût. Ce modèle permettra d'estimer le
temps de traitement d'un message transitant entre deux tâches.
Etant conscient du fait que notre problème est
NP-Complet, nous nous sommes limités à donner une solution
heuristique à notre problème. Elle a pour idée
générale de choisir à un instant t, la
tâche de coût minimal qui s'exécutera sur le processeur le
plus rapide et libre de telle sorte que le temps de transfert des
données nécessaires pour son exécution soit minimal.
Le dernier chapitre a constitué la partie pratique de
notre travail. C'est la partie d'implémentation de notre modèle.
Pour cela, nous avons dans un premier temps installer la grappe sur le plan
matériel et logiciel en y intégrant tous les outils logiciels
nécessaire à l'évaluation des performances du
réseau et à la programmation de l'application exemple sur
laquelle nous avons travaillé. Nous avons dans le même cadre
dévéloppé certains programmes pour estimer les temps de
latence et de surcoût induits par la pile réseau. Nous avons
choisi le problème de multiplication d'une matrice par un vecteur et
nous y avons appliqué un ordonnancement statique par nous-même et
avons recueilli des performances.
Une fois que nous avons fait le bilan du travail qui a
été fait, nous sommes passé à l'évaluation
pour faire une sorte de mesure par rapport aux objectifs du départ.
Evaluation
Comme nous l'avons dit dans l'introduction
générale, notre travail était de pouvoir modéliser
un ordonnancement sur une grappe de calcul hétérogène
après avoir décrit son modèle de coût.
Nous pensons avoir réalisé une revue de
littérature consistante pour la bonne compréhension de notre
problème. Cette bonne compréhension nous a permis de ressortir et
illustrer correctement et essentiellement les éléments qui
devaient nous être utiles tout au long de notre travail. En effet, les
concepts de parallélisme et d'ordonnancement ont été bien
compris ainsi que leurs constituants.
Nous avons pu élaborer un modèle d'ordonnancement
qui correspond effectivement à un environnement de grappe
hétérogène.
Concernant l'implémentation de notre modèle,
nous nous sommes confrontés à un problème : celui de la
non-existence d'un support d'exécution qui puisse permettre
d'ordonnancer en tenant compte des éléments de coût tels
que présentés dans notre modèle. Néanmoins, nous
avons utilisé la bibliothèque de communication MPICH2 qui nous
permet de faire une gestion dynamique des tâches tout au long de
l'exécution de l'application. Elle nous a aussi permis de programmer une
application parallèle test notamment la multiplication d'une matrice par
un vecteur. Elle ne permet que de faire un ordonnancement est statique, c'est
à dire le choix des processeurs est fixé au début de
l'exécution du programme et reste inchangée jusqu'à la fin
de l'exécution du dit programme. Ceci le rend indépendant
après la première étape ( qui est celle
réalisée par le programmeur ) des paramètres du
modèle comme par exemple quelle tâche est minimale en terme de
coût et qui nécessite ses données en temps minimal et quel
processeur choisir?
Malgré ces manquements, nous avons pu mesurer les
performances du réseau tels que les latences des liens, leurs
débits respectifs et les surcoûts relatifs à chaque station
de travail et paralléliser l'application test. Bien que l'ordonnancement
a été statique nous avons pu tirer des analyses
intéressantes sur les performances obtenues.
Perspectives
Afin d'atteindre nos objectifs, nous devons
développé un gestionnaire de tâches qui tiendra en compte
toutes les spécifications de notre modèle et de lui associer
MPICH25 pour permettre la gestion dynamique des
processeurs. Ensuite, il faudra le rendre générique pour
certaines applications sur toutes les plateformes
hétérogènes.
5ou éventuellement un autre outil
| 
