Algorithmique parallèle hétérogène et techniques d'ordonnancement : approches statiques et dynamiques
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
The results summarized in this document deal with the algorithmic difficulties raised by the heterogeneity of modern parallel and distributed computing platforms. The contributions of this work are divided in three parts: 1) Parallel algorithms: efficient heterogeneous distributions for most dense linear algebra kernels (matrix product, LU decomposition), lightweight redistribution techniques to cope with load variations; 2) Simulation and modeling: the genuine instability of wide-area distributed computing platforms forbids the use of real experiments to to test the behavior of an algorithm or of a scheduling policy. Therefore we have proposed simple models and have developed a realistic simulator to cope with this problem; 3) Scheduling: lots of applications are constituted of a very large number of independent identical tasks. We have established some complexity results and have proposed some approximations for different models of this situation.
Abstract FR:
Les travaux présentés dans cette thèse portent sur les difficultés algorithmiques soulevées par l'introduction de l'hétérogénéité des plates-formes modernes dans le calcul parallèle et distribué. Les contributions de cette thèse se situent à trois niveaux : 1) Algorithmique Parallèle : distributions hétérogènes pour les noyaux d'algèbre linéaire denses (produit de matrice, décomposition LU), technique de rééquilibrage, légère et efficace en cas de petites variations de charge des processeurs ; 2) Modélisation et simulation : l'instabilité latente des plates-formes de calcul distribuées à grande échelle interdit toute validation expérimentale grandeur nature d'un algorithme ou d'une politique d'ordonnancement. Nous avons proposé des modèles simples et un simulateur réaliste pour palier ce problème; 3) Ordonnancement : un certain nombre d'applications sont constituées d'un grand nombre de tâches indépendantes et de caractéristiques identiques. Nous avons établi des résultats de complexité et proposé des approximations pour différentes modélisation de ce problème.