Rééquilibrage de charge dans les solveurs hiérarchiques pour machines massivement parallèles

Abstract

Dans le cadre de la résolution des équations de Maxwell sur des maillages 3D surfaciques, il est nécessaire de faire intervenir des solveurs algébriques coûteux en temps et en mémoire. Pour réduire ces coûts, une amélioration a été de compresser les matrices manipulées, à l'aide de matrices hiérarchiques. L'utilisation de ce type de matrice permet de diminuer drastiquement les ressources nécessaires, mais induit un déséquilibre important dans la charge des différents processus impliqués dans le calcul. Ce déséquilibre peut limiter le passage à l'échelle des codes de simulation exploitant un grand nombre de nœuds de calculs.Dans cette thèse nous nous sommes intéressés à réduire ce déséquilibre, en utilisant des méthodes de rééquilibrage statique et dynamique.Les méthodes de rééquilibrage statique nous ont permis de changer la distribution des différents blocs de la matrice parmi les processus impliqués dans le calcul. Pour cela nous avons utilisé la notion de processus virtuels, qui nous a permis de redistribuer les matrices hiérarchiques parmi les différents processus. Nous avons également développé des modèles pouvant prédire le temps d'exécution des différentes parties du calcul, ainsi que son temps d'exécution total.Nous avons ensuite étudié la faisabilité de différentes méthodes de rééquilibrage dynamique, toujours dans le contexte des matrices hiérarchiques. Nous avons analysé plusieurs techniques différentes, nous permettant de mettre en évidence les limites de plusieurs d'entre elles dans le cadre de systèmes de tâches généralistes. Nous avons également mis en évidence plusieurs difficultés d'implémentation de ces méthodes, et nous avons proposé plusieurs possibilités pour les résoudre.La première contribution principale de cette thèse est une méthode de redistribution statique des blocs d'une matrice hiérarchique permettant un gain de 15% dans la durée de la factorisation de ce type de matrices.La seconde contribution principale de cette thèse est une suite d'algorithmes permettant d'effectuer des vols de tâches en mémoire distribuée sur l'étape d'assemblage de matrices hiérarchiques, ce qui permet un rééquilibrage de cette partie, permettant de gagner jusqu'à 50% de temps d'exécution dans les cas les plus extrêmes. Ces algorithmes permettent également d'effectuer un vol de tâche sur un runtime généraliste, en respectant les dépendances entre les différentes parties des calculs.