Options
Dynamic Load Balancing in Heterogeneous Distributed Environments
Auteur(s)
Rotaru, Tiberiu
Editeur(s)
Date de parution
2003
Résumé
Les systèmes distribués apparaissent de plus en plus comme des plates-formes viables pour le calcul à haute performance. L'existence des librairies standard pour la programmation parallèle facilite l'utilisation de telles plates-formes pour exécuter des applications complexes dans divers domaines de la science et la technique. Cependant, par rapport aux systèmes homogènes, un certain nombre de facteurs additionnels devraient être pris en considération afin de pouvoir assurer une exécution efficace dans des environnements de calcul hétérogènes. Dans de tels systèmes on doit prendre en compte non seulement le comportement dynamique de l'application mais également la dynamique de l'environnement. Nous avons traité le problème de l'équilibrage dynamique de charge pour des simulations adaptatives parallèles dans des environnements de calcul distribués hétérogènes. De telles applications sont habituellement caractérisées par le fait que les charges de travail assignées aux processeurs peuvent changer de manière significative et imprévisible. Notre travail a suivi deux directions principales. Dans une première étape nous avons développé un modèle hétérogène théorique et nous avons généralisé et analysé les algorithmes de diffusion. Ensuite, la variante de diffusion généralisée proposée a été comparée à d'autres approches et elle s'est avérée plus rapide qu'une autre technique populaire, l'algorithme hydrodynamique. La possibilité d'employer des schémas d'accélération polynomiaux dans un contexte dynamique a été également étudiée. D'autres schémas d'équilibrage dynamique, plus rapides, ont été proposés et étudiés. Un algorithme incrémental capable de tirer profit d'une distribution équitable déjà calculée pour calculer une autre, nouvelle, a été décrit. Dans une deuxième étape, nous avons conçu un testbed pour des simulations numériques adaptatives dans des environnements de calcul hétérogènes. Un outil, appelé HeRMeS, qui donne la possibilité d'effectuer de telles simulations et qui incorpore les méthodes développées à la première étape, a été développé. Des expériences avec les méthodes discutées et avec HeRMeS ont été faites, Parallel and distributed architectures are emerging as commonplace platforms for high performance computing. The existence of standard parallel programming libraries facilitates the use of such platforms for running challenging applications in science or engineering. However, as compared to the homogeneous case, a number of additional factors should be taken into account in order to ensure an efficient execution on heterogeneous computing environments. In such systems one must consider not only the application's dynamic behavior but also the environment's dynamics. We dealt with the dynamic load balancing for parallel adaptive simulations in heterogeneous computing environments. Such applications are usually characterized by the fact that the workloads assigned to processors may change significantly and unpredictably. Our work followed two main directions. In a first step we developed a theoretical heterogeneous computational model and we extended and analyzed the well-known diffusion algorithms with respect to such a model. Afterwards, our variant of generalized diffusion was further compared with other approaches and was shown to be faster than another popular technique, the hydrodynamic algorithm. The possibility of using polynomial acceleration schemes in a dynamic context was further investigated. Other faster dynamic load balancing schemes were proposed and investigated. An incremental algorithm that is capable of taking advantage of an already computed fair distribution for computing a new one was described. In a second step, we designed and implemented a testbed for adaptive numerical simulations in heterogeneous computing environments. A tool, called HeRMeS, which allows to perform such simulations and that incorporates the methods developed at the first step, was designed and implemented. Experiments with the discussed methods and with HeRMeS were performed
Notes
Thèse de doctorat : Université de Neuchâtel : 2003 ; 1689
Identifiants
Type de publication
doctoral thesis
Dossier(s) à télécharger
