Abstract FR:

Cette these a pour but d'etudier l'interet de l'equilibrage de charge pour le traitement d'applications a comportement dynamique irregulier sur machine simd. Elle passe en revue quelques algorithmes existants, et propose un nouvel algorithme d'equilibrage dynamique de donnees adapte a ce type de machine. Les algorithmes les plus efficaces sur machines simd sont ceux qui mettent en oeuvre les communications du reseau de voisinage moins couteuses que celles du reseau global. L'algorithme d'equilibrage propose utilise ce type de communications et associe une qualite d'equilibrage (difference entre la charge maximale apres equilibrage et la moyenne) satisfaisante a un cout modere. Il est base sur une architecture logique se plongeant de maniere naturelle dans une grille et permet l'execution d'algorithmes en un nombre d'iterations logarithmique en fonction du nombre de processeurs de la structure physique. Une modelisation des primitives de communications ainsi que du nombre de charges transferees au cours de l'equilibrage a ete realisee pour obtenir un modele de cout theorique pour chacun des algorithmes compares. L'etude montre que l'algorithme propose est meilleur que les autres. Afin de preciser l'influence des repartitions spatiales et temporelles de donnees sur le cout des algorithmes d'equilibrage, nous avons etudie differentes situations a priori caracteristiques de la majorite des applications reelles. Cette etude confirme, l'influence de ces repartitions sur le cout de l'algorithme et verifie la pertinence les modeles de cout proposes. Les differents algorithmes d'equilibrage proposes ont ete implantes sur maspar mp-1 a 2048 processeurs ; l'interet du nouvel algorithme d'equilibrage a pu etre mesure concretement par son integration effective dans deux applications irregulieres : la transformee de hough et l'ensemble de mandelbrot. Globalement, cette etude montre l'interet de l'equilibrage de donnees sur machine simd.