Travaux de thèse

Nombre d'utilisateurs de l'informatique -- principalement ceux qui ont besoin de beaucoup de puissance de calcul -- aimeraient pouvoir exécuter sur des ordinateurs parallèles leurs programmes « séquentiels », c'est-à-dire écrits pour être exécutés sur des ordinateurs classiques. Il est donc devenu nécessaire de savoir transformer, « paralléliser », les programmes séquentiels en programmes exécutables efficacement sur machines parallèles.

Ma thèse porte sur différents aspects de l'algorithmique hétérogène : mes travaux se sont principalement orientés dans les domaines de l'équilibrage de charge et de la redistribution de données en environnement hétérogène; les systèmes sur lesquels nous avons travaillé sont constitués de processeurs de caractéristiques différentes reliés entre eux par des réseaux différents. Nous nous sommes dirigés aussi vers les problèmes soulevés par le partage des liens du réseau.

  • Équilibrage de charge sur plate-forme hétérogène

    En collaboration avec mes directeurs de thèse, je me suis intéressée à la mise en oeuvre d'algorithmes itératifs sur des grappes hétérogènes. Ces algorithmes fonctionnent avec un volume important de données, qui sera réparti sur l'ensemble des processeurs. à chaque itération, des calculs indépendants sont effectués en parallèle et certaines communications ont lieu.

    • Sans partage de liens

    Dans un premier temps, nous nous sommes placés sur un réseau hétérogène complet, composé de processeurs ayant des vitesses de calcul différentes, communicant par des liens de bandes passantes différentes.

    D'un point de vue architectural, le problème se décompose en deux parties : (i) sélectionner les processeurs participant à la solution; (ii) décider de leur position dans l'anneau. Tout cela, de manière à ce que le temps total d'exécution soit minimal.

    Nous avons énoncé le problème comme suit : l'algorithme itératif fonctionne répétitivement sur une matrice rectangulaire de données qui est divisée en tranches verticales allouées aux processeurs. à chaque étape de l'algorithme, les tranches sont mises à jour localement et les informations frontières sont échangées entre tranches consécutives. Cette contrainte géométrique implique que les processeurs soient organisés en anneau virtuel. Chaque processeur communique seulement deux fois à chaque étape, une fois avec son prédécesseur (virtuel) dans l'anneau et une fois avec son successeur. Il n'existe pas de raison a priori de réduire le partitionnement des données à une unique dimension et de ne l'appliquer que sur un anneau de processeurs unidimensionnel. Cependant, un tel partitionnement est très naturel et trouver l'optimal est déjà très difficile : nous avons en effet montré que ce problème est un problème NP-complet. Nous avons développé une heuristique (l'heuristique gloutonne) qui commençait par sélectionner le processeur le plus rapide, puis, qui itérativement ajoutait un nouveau processeur dans la solution de manière à minimiser notre fonction objectif. Une autre méthode a été la résolution exacte par programmation linéaire en entiers (ILP) à l'aide de pipMP (réalisé par M. Paul Feautrier - ENS Lyon). Nous avons alors comparé nos deux méthodes, à savoir la résolution linéaire en entiers et l'heuristique gloutonne. Il s'avère que pipMP demande beaucoup trop de ressources pour arriver à la solution (nous avons pourtant utilisé une machine avec 2 gigaoctets de mémoire vive !).

    • Avec partage de liens

    La seconde étape de mon travail fut alors de considérer un réseau totalement hétérogène, mais cette fois non complet. Nous sommes donc dans le même cas de figure que précédemment mais sans l'hypothèse de complétude. Une difficulté majeure est alors que certaines routes partagent des liens physiques, les réseaux de communication de grappes hétérogènes n'étant pas totalement connectés. Si plusieurs routes partagent le même lien physique, nous décidons, dans notre heuristique, quelle sera la fraction de bande passante attribuée à chaque route.

    Une fois l'anneau et le routage décidés, il reste à déterminer le meilleur partitionnement des données. La qualité de la solution finale dépend alors d'un grand nombre de paramètres de l'application ainsi que de l'architecture, et le problème d'optimisation est naturellement difficile à résoudre. Nous avons montré que ce problème est un problème NP-complet. Nous avons alors de nouveau développé et implémenté une heuristique gloutonne qui prend en compte le partage des liens. Cette heuristique étant simpliste, nous lui avons apporté deux améliorations : le Max-Min fairness [D.Bertsekas et R.Gallager, Data Networks, Prentice Hall, 1987] et la résolution quadratique en utilisant le logiciel KINSOL. La meilleure amélioration obtenue n'est cependant que de 3% ce qui prouve l'efficacité de notre heuristique.

    • Impact du partage de liens

    Pour évaluer l'impact du partage de la bande passante des liens, nous avons retravaillé avec la version simple du problème où nous voyions le réseau comme un graphe complet : entre chaque paire de noeuds, le routage est fixé (plus court chemin en terme de bande passante), et la bande passante est définie par le lien le plus lent dans le chemin routé. Ce modèle simplifié nous permet d'obtenir un anneau de processeurs en ne tenant pas compte du partage de liens (cet anneau étant trop optimiste) ainsi qu'un temps d'exécution. Ce même anneau est alors donné à la seconde partie de notre heuristique gloutonne, qui va calculer l'allocation de bandes passantes en prenant en compte le partage de liens. Au final, nous obtenons un anneau dont les liens sont partagés (anneau réaliste) et un nouveau temps d'exécution que nous comparons au premier temps d'exécution obtenu. Par ce biais, nous obtenons une manière commode d'évaluer l'impact des différentes hypothèses faites sur les communications.

    Les conclusions pouvant être tirées de ces expérimentations sont les suivantes :

    • Lorsque l'impact du coût de communication est faible, le but principal est d'équilibrer les calculs et les deux heuristiques (avec et sans partage de liens) sont équivalentes.
    • Lorsque le rapport communication/travail devient plus important, l'effet de la contention des liens devient évident et la solution retournée par l'heuristique avec partage de liens est bien meilleure.

    • Conclusion

    Notre but principal a été de mettre l'accent sur une modélisation réaliste de communications concurrentes sur des plate-formes hétérogènes. Un résultat majeur est la NP-complétude des deux problèmes auxquels nous nous sommes intéressés; à savoir, avec partage de liens et sans partage de liens. Plus que la preuve, le résultat lui-même est intéressant puisqu'il fournit une nouvelle preuve de la difficulté intrinsèque de la conception d'algorithmes hétérogènes. Une autre avancée importante de notre recherche est la conception d'une heuristique efficace, qui fournit une ligne de conduite pragmatique au concepteur de calculs scientifiques itératifs. L'importance d'une modélisation précise des communications, qui prend pleinement en compte les contentions, est clairement mise en évidence par les résultats expérimentaux que nous avons obtenus. Notre heuristique rend possible l'implémentation efficace de calculs itératifs sur des plate-formes constituées de plusieurs ressources hétérogènes, ce qui constitue une alternative prometteuse à l'usage de super-ordinateurs coûteux. Pour conclure, nous mettons donc en avant le fait qu'une modélisation précise des communications a un impact important sur la performance des stratégies d'équilibrage de charge.

  • Ré-équilibrage de charge sur plate-forme hétérogène

    En collaboration avec mes directeurs de thèse, je me suis intéressée ensuite au problème de redistribution de données sur grappes hétérogènes. à cause des variations des ressources ou des besoins de l'application, les données ont besoin d'être redistribuées sur l'ensemble des processeurs participants afin que la charge de travail soit mieux répartie. Le problème de l'équilibrage de charge lui-même a été étudié précédemment

    • Cadre de travail

    Nous avons énoncé le problème comme suit : l'algorithme itératif fonctionne répétitivement sur une matrice rectangulaire de données qui est divisée en tranches verticales allouées aux processeurs. Chaque processeur doit travailler sur un ensemble contigu de données : l'ordre des données doit donc être préservé. Un processeur surchargé peut envoyer ses premières colonnes à son prédécesseur dans l'anneau et/ou ses dernières colonnes à son successeur et ce sont les seules possibilités.

    Nous nous sommes placés dans le cadre de travail suivant : nous supposons que les processeurs participant à la solution sont organisés en anneau, unidirectionnel ou bidirectionnel, et ayant des liens de communication homogènes ou hétérogènes (nous avons donc traité quatre cadres de travail). Chaque processeur possède dès le départ un certain nombre de données, puis le système (l'oracle) décide que chaque processeur est surchargé ou sous-chargé. Le but est alors de déterminer les communications nécessaires afin de rétablir l'équilibre (c'est ce que nous avons appelé la redistribution de données) et d'effectuer ces communications en un temps minimal.

    • Anneau unidirectionnel

    Dans un premier temps, nous nous sommes placés dans le cadre d'un anneau unidirectionnel homogène; c'est-à-dire qu'un processeur Pi ne peut envoyer des données qu'à son successeur Pi+1 et les liens de communication ont une capacité constante. Nous avons obtenu une borne inférieure du temps d'exécution de la redistribution de données ainsi qu'un algorithme optimal. Nous avons implémenté cet algorithme en C afin de vérifier nos hypothèses puis nous avons prouvé son exactitude ainsi que son optimalité.

    Dans un second temps, nous nous sommes placés dans le cadre d'un anneau unidirectionnel hétérogène; c'est-à-dire dont les liens de communication n'ont plus même capacité. Nous avons, de la même manière que précédemment, obtenu un algorithme optimal. Cependant, du fait de l'hétérogénéité des liens de communication, nous obtenons un algorithme asynchrone. Cette dernière caractéristique implique l'exactitude de notre algorithme par construction; nous n'avons eu qu'à prouver son optimalité.

    Le cas unidirectionnel a donc été complètement résolu grâce à nos algorithmes optimaux et aux preuves que nous avons fournies.

    • Anneau bidirectionnel

    La seconde étape de mon travail a été de considérer les anneaux bidirectionnels. Nous avons tout d'abord considéré un anneau bidirectionnel homogène, c'est-à-dire dont les liens ont les mêmes capacités mais où un processeur peut envoyer des données à ses deux voisins dans l'anneau. Nous avons procédé de la même manière que dans le cas de l'anneau unidirectionnel homogène : nous avons établi une borne inférieure du temps d'exécution de la redistribution de données ainsi qu'un algorithme optimal qui atteint cette borne. Nous avons implémenté cet algorithme en C et nous l'avons testé intensivement afin de vérifier nos hypothèses puis nous avons prouvé son exactitude ainsi que son optimalité.

    Nous nous sommes intéressés ensuite à un anneau bidirectionnel hétérogène, i.e., le cas général. Nous n'avons par contre pas obtenu d'algorithme optimal dans ce cas de figure. Cependant, en supposant que chaque processeur possède initialement les données nécessaires à envoyer pendant l'exécution de l'algorithme (principe de la redistribution légère), nous sommes capables d'obtenir une solution optimale. Avec cette hypothèse, nous avons obtenu un programme linéaire en entier pour résoudre notre problème. Si l'hypothèse de redistribution légère est réalisable, nous pouvons résoudre notre problème de manière moins coûteuse qu'avec la résolution linéaire en entier (qui est exponentielle dans le pire des cas). L'idée pour cela est de résoudre le programme linéaire en rationnel, ce qui se fait toujours en temps polynomial, et d'obtenir une partie entière inférieure et supérieure, sachant que l'une des deux est la solution optimale entière. Si par contre, l'hypothèse de redistribution légère n'est pas réalisable, nous avons une borne inférieure du temps d'exécution de la redistribution de données mais nous ne savons pas si cette borne est toujours atteignable. Cependant, nous n'avons pas de contre-exemple comme quoi cette borne n'est pas toujours atteignable. Le problème reste donc ouvert dans le cas général et la complexité de la borne inférieure montre que ce problème est ardu.

    • L'impact de la redistribution de données

    Pour évaluer l'impact du partage de la redistribution de données, nous avons utilisé le simulateur SimGrid (réalisé par Arnaud Legrand - ENS Lyon et Henri Casanova - UCSD) pour modéliser une application itérative sur une plate-forme générée par Tiers. Nous avons sélectionné aléatoirement des processeurs dans notre plate-forme afin de construire un anneau. De manière à motiver une redistribution de données, nous avons fait varier les vitesses de calcul des processeurs deux fois au cours de notre application itérative. L'application a été lancée 100 fois et les phases de redistributions ont eu lieu de la manière suivante :

    • pas de redistribution;
    • seule redistribution à la 50è itération;
    • 4 redistributions aux 20è, 40è, 60è et 80è itérations;
    • 9 redistributions (une toutes les 10 itérations);
    • 19 redistributions (une toutes les 5 itérations).

    Nous avons pris en compte, afin de pouvoir comparer nos différentes phases de redistribution, le quotient (volume de calcul)/(vitesse de communication). Comme prévu, nous avons pu alors remarquer que plus la puissance de calcul était grande, moins les redistributions étaient nécessaires. Et inversement, moins la puissance de calcul est importante, plus les redistributions de données sont nécessaires; cependant, il ne faut pas non plus faire trop de redistributions.

    • Conclusion

    Notre but a été de montrer l'efficacité de la redistribution de données lorsque les caractéristiques de la plate-forme ont changé. En ce qui concerne les anneaux homogènes (unidirectionnels ou bidirectionnels), le problème a été complètement résolu : nous avons des algorithmes optimaux ainsi que les preuves de leur optimalité. L'algorithme bidirectionnel s'est avéré complexe et a nécessité une longue preuve.

    En ce qui concerne les anneaux hétérogènes, il reste un problème ouvert. Le cas unidirectionnel a été assez simple à résoudre; par contre, le cas bidirectionnel n'a pas été totalement résolu : nous avons obtenu une solution optimale pour la redistribution légère. Cependant, la complexité de la borne dans le cas général montre qu'obtenir un algorithme optimal est une tâche ardue, si un tel algorithme polynomial existe.

    Tous nos algorithmes ont été implémentés et intensivement testés.