Algorithmes d'allocation statique pour la planification d'applications haute performance

Abstract

De nos jours, les applications d'algèbre linéraire sont couramment utilisées pour traiter des problèmes dont la grande taille requiert une exécution parallèle distribuée par des plate-formes de calcul dédiées. De nombreuses librairies d'algèbre linéaire reposent sur l'utilisation de systèmes dynamiques utilisant un modèle d'exécution à base de tâches. De tels outils permettent d'atteindre de hauts niveaux de performance en appliquant un ordonnancement dynamique des tâches et une gestion automatique des communications pour un ensemble de ressources de calcul distribuées. Dans le même temps, ils simplifient la mise en oeuvre des opérations d'algèbre linéaire en découplant la distribution de données et les calculs et exemptent le programmeur de la gestion explicite des communications. Bien que les systèmes dynamiques à base de tâches permettent l'utilisation de virtuellement n'importe quelle distribution de données, une grande partie des librairies d'algèbre liéaire reposent toujours sur la distribution classique 2D Bloc Cyclique héritée des premiers temps du domaine du Calcul Haute Performances durant lequel la description des applications parallèles reposait essentiellement sur des primitives MPI rigides. Dans cette thèse, nous explorons les possibilités qu'offrent les systèmes dynamiques à base de tâches et cherchons à concevoir des distributions de données adaptées à l'exécution parallèle distribuée d'opérations d'algèbre linéaire particulières, plus précisément la multiplication de matrices, l'opération "symmetric rank-k update", la factorisation LU et la factorisation de Cholesky. Nous montrons qu'il est possible de concevoir des distributions de données originales mieux adaptées aux caractéristiques de chaque opération. Prenant en compte la réduction des communications et l'équilibrage de la charge de travail, les solutions développées parviennent à surpasser les distributions classiques dans de nombreuses configurations, en particulier dans les cas denses et homogènes, tant sur les performances théoriques qu'expérimentales. Ce travail illustre que d'importants gains par rapport aux solutions de l'état de l'art actuel sont atteignables grâce à une conception plus fine des distributions de données qui peuvent être facilement mises en oeuvre dans des librairies d'algèbre linéaire modernes utilisant un modèle d'exécution à base de tâches.