Static Allocation Algorithms for Scheduling High-Performance Applications
Algorithmes d'allocation statique pour la planification d'applications haute performance
Résumé
Linear algebra applications are commonly used nowadays to solve large scale problems whose size requires the use of distributed and parallel execution on dedicated computation platforms. Many modern linear algebra libraries rely on runtime systems that implement task-based model for their parallel execution. Such tools allow to achieve high performance by performing dynamic scheduling and automatic handling of communications on a set of distributed resources. At the same time, they simplify the implementation of linear algebra operations by decoupling the data distribution from the computations and relieve the programmer from explicit management of communications. Although runtime systems enable the use of virtually any data distribution, most linear algebra applications still rely on the traditional 2D Block Cyclic distribution inherited from the early years of High Performance Computing, when parallel applications were essentially described using basic MPI primitives. In this work we explore the possibilities offered by runtime systems and we design data distributions adapted to the parallel distributed execution of specific linear algebra operations, namely matrix multiplication, symmetric rank-k update, LU and Cholesky factorization. We show that it is possible to design original data distribution schemes that are best fitted to the characteristics of each operation. By taking into account communications reduction and load balancing, the newly developed solutions manage to outperform classic distributions in many configurations, including dense homogeneous cases, both in terms of theoretical and actual parallel performance. This work illustrates that significant improvements over state-of-the-art solutions are achievable by a more careful design of sophisticated data distributions which can in turn be easily implemented using modern task-based linear algebra libraries.
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.
Origine : Version validée par le jury (STAR)