Soutenance mémoire
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.
La simulation numérique
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.
Le traitement de maillages
Maillage polygonal
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.
Exemple
Voici un exemple de représentation permettant de stocker les informations d’un maillage polygonal volumique. Les positions des sommets sont donnés par l’ensemble P, les faces par l’ensemble F et les cellules par C, décrits ci-dessous :
P = x1, y1, z1,…,xN , yN , zN (1.1)
FP = (p1,p4,p5),…,(p3,p7,p9,p2) (1.2)
FC = (c3,c1,c7,c8),…,(c2,c4,c3) (1.3)
On note ici que les coordonnées sont fournies de façon entrelacées, que la connectivité faces-sommets est descendante nodale, tandis que la connectivité facescellules est ascendante. Les arêtes ne sont a priori pas présentes, sauf si le tableau FP est conçu de telle sorte que les n-uplets soient ordonnées, le triplet (4,8,9) indiquant les trois arêtes (4,8), (8,9) et (9,4).
Attributs
Ces informations sont suffisantes pour décrire les propriétés élémentaires du maillage, mais il est parfois utile de stocker d’autres données sur les simplexes. Dans le cas du rendu, par exemple, on pourra stocker les normales des sommets, ou les couleurs des faces. Si l’on souhaite appliquer une texture, on stockera les coordonnées (u, v) de paramétrisation en chaque sommet.
Tous ces attributs vont se présenter sous forme de tableaux de données, et viennent enrichir le maillage. Il est parfois utile de se baser sur ces attributs pour des processus de filtrage. Par exemple, un utilisateur peut avoir colorié le maillage en vue de distinguer des ensembles sur les lesquels il souhaite voir certaines opérations effectuées (raffinement) sans affecter le reste du maillage.
Vocabulaire
– Voisinage : le k-voisinage d’un sommet v0 est défini comme l’ensemble v1,…, vn de points tels que ∀ i ∈ [1;n] v0, vi sont reliés par au moins k arêtes.
– Valence : le nombre de 1−voisins d’un sommet.
– Elément de bord : un élément de bord est un élément ont le voisinage est homéomorphe à une demi-boule.
– Sommet régulier ou extraordinaire : un sommet à l’intérieur d’un maillage est dit regulier lorsqu’il a une valence de 6 pour un maillage triangulaire, 4 pour un maillage quadrangulaire (4 et 3 respectivement pour un sommet de bord). Tous les autres sommets sont dits extraordinaires.
– Maillage régulier : un maillage est dit regulier lorsque tous les sommets de ce maillage sont réguliers. Un maillage est semi-régulier si la majorité de ses sommets sont réguliers.
– Maillage isotrope ou anisotrope : un maillage est dit isotrope si la forme des polygones est uniforme sur le maillage. Au contraire, un maillage dont la distribution de la forme des faces est variable dans l’espace est dit anisotrope.
– Maillage structuré : un maillage est dit structuré si tous les éléments ont la même valence (hors éléments de bord).
– Maillage conforme : un maillage est conforme si aucun de ses sommets ne se trouve au milieu d’un arête.
Méthodes de traitement
Plusieurs types d’opérations peuvent être réalisée sur un maillage, selon les besoins de l’utilisateur.
Filtrage/Lissage
Une opération de filtrage, ou de lissage d’un maillage consiste à modifier la géométrie de celui-ci sans en altérer la topologie. Ainsi, dans le cadre d’un maillage indexé, seuls les attributs de position et/ou de normale verront leurs valeurs affectées, les ensembles topologiques conservant leurs propriétés. On parle en général de filtrage lorsque le but de l’opération est la suppression de bruit ou d’artefacts, tandis que le terme de lissage s’applique à la régularisation d’une surface.
Raffinement/Simplification
On peut souhaiter, pour des besoins de précision par exemple, augmenter la résolution de certaines zones du maillage, en ajoutant des points sur la surface, et en modifiant la topologie de manière adéquate. Ce processus est appelé raffinement. L’opération inverse, dite simplification, a pour but d’alléger la taille du maillage, en simplifiant la topologie dans des zones où la géométrie varie très peu.
Remaillage
Cette dernière famille d’algorithme regroupe les modifications topologiques qui ne sont ni des raffinements, ni des simplifications. Le but n’est pas de modifier la précision du maillage, mais d’optimiser la topologie de celui-ci, par exemple en essayant de régulariser le nombre de sommet de chaque face, le nombre de voisins de chaque sommet.
Le calcul parallèle
Les algorithmes de calculs ont tout d’abord été élaborés en vue d’une application séquentielle. Exécuté sur un ordinateur possédant un seul cœur, le problème est découpé en une série d’instructions discrètes, qui seront exécutées l’une après l’autre, sans chevauchement temporel. Dans son approche la plus simple, le calcul parallèle implique seulement l’utilisation simultanée de ressources pour résoudre le problème. Celui-ci est d’abord découpé en parties indépendantes, pouvant être résolues de façon indépendante, puis chacune de ces parties est exécutée sur un cœur comme un problème séquentiel. La parallélisation peut se faire sur une machine possédant plusieurs cœurs, ou bien sur plusieurs machines en réseau, ou bien encore grâce à une combinaison de ces deux méthodes. Le problème doit pouvoir être découpé en parties indépendantes et pouvant être exécutée simultanément. De fait, tous les algorithmes ne peuvent être parallélisés. Le calcul parallèle permet de résoudre plusieurs défis. Le gain de temps, bien sûr, mais également la possibilité de traiter des problèmes de dimensions supérieures, très gourmands en ressources. La parallélisation permet également de faire collaborer à travers le monde de nombreux ordinateurs sur le même projet.
Définitions
On peut classifier les systèmes de calcul en quatre grands types, selon la taxinomie de Flynn [Fly72], présentant les architectures selon le nombre d’instructions (une ou plusieurs) et le nombre de mémoires (une ou plusieurs).
– SISD : Single Instruction, Single Data. C’est l’architecture séquentielle simple, un seul processeur éxécutant les tâches à partir d’une seule mémoire.
– SIMD : Single Instruction, Multiple Data. Tous les processeurs effectuent exactement la même opération, mais sur des zones de mémoire différente.
– MISD : Multiple Instructions, Single Data. Dans ce cas, une même zone de mémoire est utilisée par plusieurs processeurs, qui effectuent des opérations différentes.
– MIMD : Multiple Instructions, Multiple Data. Cette configuration est la plus courante dans le cadre du calcul parallèle. La mémoire peut être partagée, c’est-àdire que chacune des unités de calcul a accès aux mêmes zones mémoire, ou bien distribuée, autrement dit chaque processeur n’a accès qu’à sa zone de mémoire propre, et la synchronisation et la communication doivent être prise en charge.
Exemples
Prenons par exemple le problème du calcul des termes de la suite de Fibonacci. La définition de cette suite est la suivante : les deux premiers termes sont u0 = 1 et u1=1. Les termes suivants sont définis comme un = un−1 + un−2. À partir de ces définitions, il apapraît que chaque nouveau terme de la série dépend des deux précédents et, par conséquent, la seule solution pour obtenir le n-ième terme de la série est de calculer un à un les précédents. Ce problème ne peut pas être paralléliser, il est de type SISD.
Imaginons à présent le problème de la somme de deux vecteurs de Rn, w = u + v. La i-ème composante de w est alors donnée par wi = ui + vi , et est donc totalement indépendante des autres composantes de u ou v. Il est par conséquent possible de séparer le calcul de chaque composante sur un processeur différent, et l’architecture obtenue ici est SIMD. C’est le mode de fonctionnement principal des GPUs.
Le traitement du signal peut nous fournir un exemple d’architecture MISD, dans le cas où un même signal serait filtré avec des paramètres différents par les processeurs. Il est à noter que cet agencement est toutefois plutôt rare.
|
Table des matières
1 Introduction
1.1 Contexte
1.2 La simulation numérique
1.3 Le traitement de maillages
1.3.1 Maillage polygonal
1.3.2 Méthodes de traitement
1.3.3 Objectifs
1.4 Le calcul parallèle
1.4.1 Introduction
1.4.2 Définitions
1.4.3 Exemples
1.4.4 Parallélisation avec OpenMP
1.4.5 Parallélisation avec MPI
1.4.6 Déterminisme
1.6 Contributions de la thèse
1.6.1 Vue d’ensemble
1.6.2 Publications
2 Vers la parallélisation
2.1 Voisinage distribué
2.1.1 Problématique
2.1.2 Moyennes locales
2.1.3 Adaptation parallèle
2.2 Approximation
2.2.1 Matrice jacobienne
2.2.2 Adaptation parallèle
2.2.3 Résultats
2.3 Discussion
3 Filtrage surfacique
3.1 Contexte
3.1.1 Bruit et filtres passe-bas
3.1.2 Travaux précédents
3.2 Filtre bilatéral séparable
3.2.1 Accélérations
3.2.2 Notre approche
3.2.3 Résultats
3.2.4 Discussion
3.3 Histogrammes locaux lissés
3.3.1 Présentation
3.3.2 Médiane géométrique
3.3.3 Extension aux maillages
3.3.4 Résultats
4 Lissage volumique
4.1 Contexte
4.1.1 Maillages volumiques
4.1.2 Notion de dual
4.1.3 Travaux existants
4.2 Dégauchissement
4.2.1 Problématique
4.2.2 Notre approche
4.2.3 Résultats
4.3 Filtre bilatéral volumique
4.3.1 Problématique
4.3.2 Qualité de maillage
4.3.3 Notre approche
4.3.4 Résultats
5 Remaillage : Prismes
5.1 Introduction
5.2 Création de la couche limite
5.2.1 Partition de la surface
5.2.2 Suppression
5.2.3 Projections
5.2.4 Cas d’un plan
5.2.5 Arêtes vives
5.2.6 Concavités
5.2.7 Relaxation
5.2.8 Découpe en couches limites
5.3 Résultats
6 Conclusion
Télécharger le rapport complet
