Load Balancing for Parallel Coupled Simulations
Equilibrage de la charge de codes couplés massivement parallèles
Résumé
Load balancing is an important step conditioning the performance of parallel
applications. The goal is to distribute roughly equal amounts of computational
load across a number of processors, while minimising interprocessor communi-
cation. A common approach to model the problem is based on graph structures
and graph partitioning algorithms.
Moreover, new challenges involve the simulation of more complex physical
phenomena, where different parts of the computational domain exhibit differ-
ent physical behavior. Such simulations follow the paradigm of multi-physics
or multi-scale modeling approaches. Combining such different models in mas-
sively parallel computations is still a challenge to reach high performance.
Additionally, traditional load balancing algorithms are often inadequate, and
more sophisticated solutions should be explored.
In this thesis, we propose new graph partitioning algorithms that balance
the load of such simulations, refered to as co-partitioning. We formulate
this problem with the use of graph partitioning with initially fixed vertices
which we believe represents efficiently the additional constraints of coupled
simulations. We have therefore developed a direct algorithm for graph parti-
tioning that manages successfully problems with fixed vertices. The algorithm
is implemented inside Scotch partitioner and a series of experiments were car-
ried out on the DIMACS graph collection. Moreover we proposed three co-
partitioning algorithms that respect the constraints of the respective coupled
codes. We finally validated our algorithms by an experimental study com-
paring our methods with current strategies on artificial cases and on real-life
coupled simulations.
Dans le contexte du calcul scientifique, l'équilibrage de la charge est un problème crucial qui conditionne la
performance des simulations numériques parallèles. L'objectif est de répartir la charge de travail entre un nombre de processeurs donné,
afin de minimiser le temps global d'exécution.
Une stratégie populaire pour résoudre ce problème consiste à modéliser la simulation à l'aide d'un graphe et à appliquer des algorithme de partitionnement.
En outre, les simulations numériques tendent à se complexifier, notamment en mixant plusieurs codes représentant des physiques
différentes ou des échelles différentes. On parle alors de couplage de codes multi-physiques ou multi-échelles.
Dans ce contexte, le problème de l'équilibrage de charge devient également plus
difficile, car il ne s'agit plus d'équilibrer chacun des codes séparément, mais l'ensemble de ces codes pris dans leur globalité.
Dans ce travail, on propose de resoudre ce problème en
utilisant le modèle de partitionnement à sommets fixes qui pourrait représenter efficacement
les contraintes supplémentaires imposées par les codes couplés (co-partitionnement).
Nous avons donc développé un algorithme direct
de partitionnement de graphe qui gère des sommets fixes. L'algorithme a été implémenté dans
le partitionneur Scotch et une série d'expériences ont été menées sur la collection des graphes DIMACS.
Ensuite nous avons proposé trois algorithmes de co-partitionnement qui respectent les contraintes issues
des codes couplés respectifs. Nous avons egalement validé nos algorithmes par une étude expérimentale en
comparant nos méthodes aux strategies actuelles sur des cas artificiels ainsi que sur des codes
réels couplés.
Loading...