Study and obtention of exact, and approximation, algorithms and heuristics for a mesh partitioning problem under memory constraints

Dans de nombreux domaines scientifiques, la taille et la complexité des simulations numériques sont si importantes qu'il est souvent nécessaire d'utiliser des supercalculateurs à mémoire distribuée pour les réaliser. Les données de la simulation ainsi que les traitements sont alors répartis sur différentes unités de calculs, en tenant compte de nombreux paramètres. En effet, cette répartition est cruciale et doit minimiser le coût de calcul des traitements à effectuer tout en assurant que les données nécessaires à chaque unité de calcul puissent être stockées localement en mémoire. Pour la plupart des simulations numériques menées, les données des calculs sont attachées à un maillage, c'est-à-dire une discrétisation du domaine géométrique d'étude en éléments géométriques simples, les mailles. Les calculs à effectuer sont alors le plus souvent effectués au sein de chaque maille et la distribution des calculs correspond alors à un partitionnement du maillage. Dans un contexte de simulation numérique, où les méthodes mathématiques utilisées sont de types éléments ou volumes finis, la réalisation du calcul associé à une maille peut nécessiter des informations portées par des mailles voisines. L'approche standard est alors de disposer de ce voisinage localement à l'unité de calcul. Le problème à résoudre n'est donc pas uniquement de partitionner un maillage sur k parties en plaçant chaque maille sur une et une seule partie et en tenant compte de la charge de calcul attribuée à chaque partie. Il faut ajouter à cela le fait de prendre en compte l'occupation mémoire des cellules où les calculs sont effectués et leurs voisines. Ceci amène à partitionner les calculs tandis que le maillage est distribué avec recouvrement. Prendre explicitement ce recouvrement de données est le problème que nous proposons d'étudier.In many scientific areas, the size and the complexity of numerical simulations lead to make intensive use of massively parallel runs on High Performance Computing (HPC) architectures. Such computers consist in a set of processing units (PU) where memory is distributed. Distribution of simulation data is therefore crucial: it has to minimize the computation time of the simulation while ensuring that the data allocated to every PU can be locally stored in memory. For most of the numerical simulations, the physical and numerical data are based on a mesh. The computations are then performed at the cell level (for example within triangles and quadrilaterals in 2D, or within tetrahedrons and hexahedrons in 3D). More specifically, computing and memory cost can be associated to each cell. In our context, where the mathematical methods used are finite elements or finite volumes, the realization of the computations associated with a cell may require information carried by neighboring cells. The standard implementation relies to locally store useful data of this neighborhood on the PU, even if cells of this neighborhood are not locally computed. Such non computed but stored cells are called ghost cells, and can have a significant impact on the memory consumption of a PU. The problem to solve is thus not only to partition a mesh on several parts by affecting each cell to one and only one part while minimizing the computational load assigned to each part. It is also necessary to keep into account that the memory load of both the cells where the computations are performed and their neighbors has to fit into PU memory. This leads to partition the computations while the mesh is distributed with overlaps. Explicitly taking these data overlaps into account is the problem that we propose to study