Algorithmes parallèles de manipulation de maillages

Les simulations numériques constituent aujourd’hui l’un des piliers de la recherche scientifique et de certains domaine de l’ingénierie, permettant d’une part une réduction drastique des coûts de fabrication, en évitant la construction de nombreuses maquettes et prototypes, et d’autre part une meilleure observation et compréhension de phénomènes se déroulant à des échelles trop grandes ou trop petites pour pouvoir être réalisées en pratique.

C’est au cœur de ces simulations que se situe le maillage, une discrétisation la plus juste possible de la géométrie du problème, permettant une estimation suffisamment précise des quantités continues de la physique. Les équations aux dérivées partielles régissant l’évolution des variables du problème peuvent alors, sous leur forme discrète, révéler le mouvement des particules, les changements de températures ou les variations de pression.

Mais pour garantir la justesse de cette discrétisation, le maillage doit répondre à des de critères de qualité, dépendant des méthodes numériques de résolution utilisées. Ces critères impliquent un certain agencement spatial et topologique des différents éléments du maillage, ainsi que, par exemple, leur nombre. De ce fait, une géométrie complexe, sur laquelle un calcul de haute précision doit être effectué, requerrait un très grand nombre de sommets, faces et cellules.

Or, un maillage de grande taille implique de longs temps de calcul, et demande un espace de stockage important en mémoire, et il arrive que l’un de ces paramètres soit une limitation pour la simulation. Il est donc nécessaire d’optimiser le maillage en vue de la simulation, et de nombreux algorithmes de lissage, remaillages, raffinement abordent cette problématique.

La solution la plus classique pour réduire le temps d’exécution d’une tâche est de la paralléliser : si deux opérations n’ont aucun lien entre elles, alors elles peuvent être effectuées en même temps. En suivant cette logique, la parallélisation de la mémoire, ou mémoire distribuée, permet aussi (et surtout) de traiter de grands volumes de données en séparant spatialement le problème sur différents processeurs.

Afin de repousser encore les limites des possibilités de calcul qui s’offrent à nous, il est intéressant de chercher à combiner les deux types d’optimisation, autrement dit : comment optimiser le maillage lorsque celui-ci se trouve dans une architecture parallèle ?

Dans la suite de cette introduction, nous proposons une vue d’ensemble sur le traitement de maillages, et sur la parallélisation. Nous commencerons par décrire brièvement le processus d’une simulation numérique (1.2), avant d’aborder la définition d’un maillage (1.3), puis les grandes familles de traitement de maillage, et enfin les objectifs recherchés. Nous décrirons ensuite (1.4) le calcul parallèle, au travers de quelques exemples. Nous clôturerons ce chapitre avec une présentation des grandes lignes de ce manuscrit (1.6).

La réalisation complète d’une simulation numérique est en général constituée des éléments suivants :
– Conception du modèle
– Maillage de la géométrie
– Application du code de calcul .

Les trois étapes de la simulation sont parfaitement indépendantes et il est de fait tou à fait possible d’utiliser un premier logiciel pour définir le modèle, un second pour mailler celui-ci, et enfin un code de calcul pour effectuer la simulation. En pratique, cette indépendance est rapidement limitée par les différents formats de fichiers et les informations transmises d’un logiciel au suivant.

Ainsi, en regroupant deux ou trois de ces étapes au sein d’un même logiciel, on accroît d’une part les capacités intrinsèques de chaque étape, mais également leur inter-opérabilité. En combinant par exemple la conception du modèle et son maillage, il est possible pour la méthode de maillage de s’appuyer sur les définitions géométriques du modèle, sans avoir à détecter les arêtes vives ou autres caractéristiques du maillage.

De même, si les deux dernières étapes sont regroupées, il est possible d’imaginer un maillage initial qui serait modifié (raffiné, par exemple) en fonction de la sortie du code de calcul, et ainsi optimiser le maillage à l’utilisation qui en est faite.

Géométrie et topologie
Un maillage polygonal surfacique est la donnée d’un ensemble de polygones qui approximent une surface. Ils peuvent être représentés par une série de d’éléments désorganisées (soupes de polygones), ou bien être donnés sous la forme de maillage indexé, représentation basée sur des graphes. Nous n’allons, pour la suite de ce document, considérer que des maillages indexés, dont la structure permet bien plus aisément d’en manipuler les éléments.

Ainsi, une maillage porte essentiellement deux informations. D’une part, une information géométrique, avec, le plus souvent, la liste des positions dans l’espace des sommets, en général sous forme d’un triplet de coordonnées (x, y, z) pour chaque sommet (entrelacées), mais peuvent aussi être données sous la forme de trois listes des coordonnées dans chaque dimension (toutes les abscisses, puis toutes les ordonnées, …). D’autre part, l’information topologique, faisant intervenir des simplexes de dimension supérieure : arête (1-simplexe), face (2-simplexe) et cellule (3-simplexe) dans le cas d’un maillage volumique.

La topologie d’un maillage va ainsi être constituée de tableaux n-uplets reliant les simplexes de deux ordres différents. On parlera de connectivité ascendante lorsque un k-simplexe est décrit par les j-simplexes auxquels il appartient, avec j > k. À l’inverse, la connectivité est dite descendante lorsque un k-simplexe est décrit par les j-simplexes qui le constituent, avec j < k. Il existe également les représentations nodales, dans lesquel chaque simplexe est décrit à l’aide des sommets qui le compose.