Load balancing in hierarchical solvers on manycore architectures

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.In the context of the resolution of Maxwell's equation on 3D surface meshes, it is necessary to use algebraic solvers that are costly in time and memory. To reduce these costs, an improvement has been to apply hierarchical compression techniques on matrices. This kind of matrix allows the required ressources to be drastically reduced, but induce an important imbalance between the load of the different processes involved in the computation. This imbalance is a limiting factor for the scalability of simulation codes with a large number of computational nodes.In this thesis, we have been looking for reducing this imbalance, by using both static and dynamic load balancing methods.The static load balancing methods have allowed us to change the distribution of the different blocks of the matrix among the processes involved in the computation. For this purpose we used the notion of virtual processes, which allowed us to redistribute the hierarchical matrices among the different processes. We also developed models that could predict the execution time of the different parts of the computation, as well as its total execution time in order to dispatch computation accordingly.Then, we studied the feasibility of different dynamic load balancing methods, again in the context of hierarchical matrix. We have analyzed different techniques, allowing us to highlight the limitations of several of them in the context of general purpose task programming environnements. We have also highlighted several implementations difficulties and have proposed several possibilities to solve them.The first major contribution of this thesis is a static redistribution methods of the matrix's blocks, which allows a gain up to 15% in the duration of the factorization of this kind of hierarchically compressed matrices.The second major contribution of this thesis is the introduction of a a set of algorithms which provide a work stealing mechanism into our task-based environment over distributed memory. This not only completely balances the load of the assembly phase, but also allow to steal tasks within a task graph while properly respecting the dependencies between the differents parts of the computation