Placement de tâches sur ordinateurs parallèles à mémoire distribuée
Institution:
Grenoble INPGDisciplines:
Directors:
Abstract EN:
The growing needs in computing performance imply more complex computer architectures. The lack of good programming environments for these machines must be filled. The goal to be reached is to find a compromise solution between portability and performance. The subject of this thesis is studying the problem of static allocation of task graphs onto distributed memory parallel computers. This work takes part of the project INRIA-IMAG APACHE and of the european one SEPP-COPERNICUS (Software Engineering for Parallel Processing). The undirected task graph is the chosen programming model. A survey of the existing solutions for scheduling and for mapping problems is given. The possibility of using directed task graphs after a clustering phase is underlined. An original solution is designed and implemented ; this solution is implemented within a working programming environment. Three kinds of mapping algorithms are used: greedy, iterative and exact ones. Most developments have been done for tabu search and simulated annealing. These algorithms improve various objective functions (from most simple and portable to the most complex and architecturaly dependant). The weigths of the task graphs can be tuned using a post-mortem analysis of traces. The use of tracing tools leads to a validation of the cost function and of the mapping algorithms. A benchmark protocol is defined and used. The tests are runned on the Meganode (a 128 transputer machine) using VCR from the university of Southampton as a router, synthetic task graphs generation with ANDES of the ALPES project (developped by the performance evaluation team of the LGI-IMAG) and the Dominant Sequence Clustering of PYRROS (developped by Tao Yang and Apostolos Gerasoulis)
Abstract FR:
La demande croissante de puissance de calcul est telle que des ordinateurs de plus en plus performants sont fabriqués. Afin que ces machines puissent être facilement exploitées, les lacunes actuelles en terme d'environnements de programmation doivent être comblées. Le but à atteindre est de trouver un compromis entre recherche de performances et portabilité. Cette thèse s'intéresse plus particulièrement au placement statique de graphes de taches sur architectures parallèles a mémoire distribuée. Ce travail s'inscrit dans le cadre du projet INRIA-IMAG APACHE et du projet européen SEPP-COPERNICUS (Software Engineering for Parallel Processing). Le graphe de taches sans précédence est le modèle de représentation de programmes parallèles utilise dans cette thèse. Un tour d'horizon des solutions apportées dans la littérature au problème de l'ordonnancement et du placement est fourni. La possibilité d'utilisation des algorithmes de placement sur des graphes de précédence, après une phase de regroupement, est soulignée. Une solution originale est proposée, cette solution est interfacée avec un environnement de programmation complet. Trois types d'algorithmes (gloutons, iteratifs et exacts) ont été conçus et implémentes. Parmi ceux-ci, on retrouve plus particulièrement un recuit simule et une recherche tabu. Ces algorithmes optimisent différentes fonctions objectives (des plus simples et universelles aux plus complexes et ciblées). Les différents paramètres caractérisant le graphe de taches peuvent être affinés suite à un relevé de traces. Des outils de prise de traces permettent de valider les différentes fonctions de cout et les différents algorithmes d'optimisation. Un jeu de tests est défini et utilise. Les tests sont effectué sur le Mégapode (machine a 128 transputers), en utilisant comme routeur VCR de l'université de Southampton, les outils de génération de graphes synthétiques ANDES du projet ALPES (développé par l'équipe d'évaluation de performances du LGI-IMAG) et l'algorithme de regroupement DSC (Dominant Sequence Clustering) de PYRROS (développé par Tao Yang et Apostolos Gerasoulis). Mapping task graphs on distributed memory parallel computers