Les problèmes NP-complets, la répartition de charge et la propagation de la chaleur : SimGrid vs Grid'5000

• Cadre de travail

  En collaboration avec Abdou Guermouche, je me suis intéressée à la progation de la chaleur avec des comparaisons entre le simulateur SimGrid et une application réelle pour évaluer les algorithmes d'équilibre de charge et de redistribution de données.

  Nous allons étudier le comportement de nos algorithmes (équilbrage de charge et redistribution de données - (cf Travaux de thèse dans le menu « RECHERCHE ») sur des plates-formes hétérogènes. Pour ce faire, nous allons comparer les deux cadres expérimentaux. Le premier est ce qu'on appelle la simulation de plates-formes - SimGrid - pour l'étude du comportement de nos algorithmes. Le second est l'implémentation en exécution réelle pour la mise en oeuvre de notre application. Notez que l'objet de cet article est l'étude des algorithmes et la comparaison des comportements observés entre la exécution réelle et la simulation de SimGrid.

• La propagation de la chaleur

  • Description

  Pour étudier le comportement de nos algorithmes, nous allons nous concentrer sur une simple application : la propagation de la chaleur. La propagation de la chaleur est une application parmi tant d'autres qui correspond à notre modèle. Nous l'avons choisie pour sa simplicité. Toutefois, les résultats présentés dans ce document restent valables pour des applications plus complexes (simulation de tourbillon, simulation de turbulence en aérodynamique, ...) à condition qu'elles respectent le modèle. Dans ce contexte, nous nous concentrerons sur des algorithmes d'équilibrage de charge et des algorithmes de redistribution de données.

  Imaginez une plaque de métal sur laquelle est appliquée une source de chaleur sur les bords. La chaleur se propage à l'intérieur de la plaque. La température sur les bords est maintenue constante, la distribution de la chaleur vers la plaque tend vers un état stable. Ce problème peut-être résolu en utilisant les méthodes de différences finies pour discrétiser la plaque à deux dimensions dans une grille à deux dimensions. Ensuite, une méthode itérative, comme Jacobi, est utilisée pour résoudre l'équation discrétisée. Pour des raisons de simplicité, nous ne considérerons que des communications associées à la métode en différences finies de Jacobi. Dans cette classe de méthodes numériques, une grille multidimensionnelle est mise à jour plusieurs fois par le remplacement de la valeur à chaque point à l'aide d'une opération sur les valeurs d'un nombre fixe de points voisins. Nous appelons l'ensemble des valeurs nécessaires à la mise à jour d'un point de la grille un stencil.

  Cette simple application correspond pleinement à notre modèle. En effet, vu que les communications sont dans un proche voisinage, si nous donnons à chaque processeur un bloc vertical de colonnes de la grille discrétisée, les communications entre les processeurs correspondront à notre anneau-hypothèse. Ainsi, chaque processeur P_i communiquera seulement avec ses voisins P_i-1 et P_i+1.

  Nos algorithmes s'appliquent parfaitement à la discrétisation en deux dimensions où chaque processeur P_i a besoin d'échanger ses données avec ses voisins P_i-1 et P_i+1.

• De la théorie à la pratique

  Ayant pour objectif d'évaluer expérimentalement l'impact de nos algorithmes de redistribution, nous avons conçu deux prototypes expérimentaux : le premier est basé sur le simulateur SimGrid alors que le second est une implémentation réelle. L'idée derrière une telle approche est de comparer le comportement de l'application cible (i.e. la propagation de la chaleur) sur chacun des environnements.

  Nous avons écrit un prototype illustrant l'intérêt des algorithmes de redistribution dans le contexte d'une application simple qui correspond totalement à notre modèle : la propagation de la chaleur. Le programme correspondant a été écrit en langage C en utilisant les sockets UNIX standards pour les communications ainsi que la couche XDR pour assurer l'intéropérabilité durant les communications entre machines hétérogènes.

  Notre étude expérimentale suivra une approche dans laquelle nous tenterons (autant que possible) d'avoir les mêmes conditions expérimentales entre l'environnement réel et l'environnement simulé. Pour se faire, nous avons utilisé l'outil wrekavoc pour contrôler l'hétérogénéité de la plate-forme cible. L'idée est donc dégrader périodiquement certaines caractéristiques de ressources de la plate-forme choisies aléatoirement et d'évaluer le comportement de nos algorithmes. L'objectif est de comparer le comportement des algorithmes dans le cas d'une exécution réelle et dans le cas d'une exécution simulée. Il est à noter que la principale différence de comportement entre l'exécution réelle et l'exécution simulée est que dans le premier cas, nous laissons l'application découvrir le nouvel état de la plate-forme (par le biais de mesures), alors que dans le cas simulé nous fournissons au simulateur la plate-forme modifiée.

• Conclusion

  Nous avons présenté dans cet article une étude du comportement d'un algorithme de redistribution conçu pour équilibrer la charge de travail sur un ensemble de processeurs organisés en anneau virtuel. Pour se faire, nous avons mis en oeuvre deux versions d'une même application : la propagation de la chaleur. La première implémentation a été faite au dessus du simulateur SimGrid et représente une mise en oeuvre de haut niveau très adaptée à l'étude algorithmique. La seconde, quant à elle, est une implémentation réelle utilisant les sockets UNIX standards. Vu que nos algorithmes sont conçus pour gérer des plates-formes hétérogènes, nous avons utilisé l'outil wrekavoc pour contrôler de manière externe et dynamique les caractéristiques de la plate-forme. Les modifications apportées à la plate-forme sont stockées pour être par la suite utilisées lors de l'exécution simulée. L'étude expérimentale a montré l'intérêt de notre algorithme de redistribution. De plus, nous avons pu mettre en évidence l'intérêt du simulateur. En effet, le comportement observé pendant une exécution simulée est très proche de celui d'une exécution réelle. Cependant, nous avons aussi observé qu'il existe dans certains cas quelques différences en terme de « performance » entre les deux approches. Pour comprendre les raisons de ces différences, il est nécessaire de concevoir plus finement la version simulée. Autant que nous sachions, cette étude est une des premières confrontant SimGrid à une exécution réelle dans le contexte d'une vraie application. Ce travail représente une première étape pour la validation à travers la comparaison avec des cas réels de SimGrid dans le contexte d'applications complexes.