Titre: Algorithmes sur GPU de visualisation et de calcul pour des maillages non-structurés

Auteurs: Luc BUATOIS

Ecole/Université: Institut National Polytechnique de Lorraine

Résumé: Les algorithmes les plus récents de traitement numérique de la géométrie ou bien encore de simulation numérique de type CFD (Computational Fluid Dynamics) utilisent à présent de nouveaux types de grilles composées de polyèdres arbitraires, autrement dit des grilles fortement non-structurées. Dans le cas de simulations de type CFD, ces grilles peuvent servir de support à des champs scalaires ou vectoriels qui représentent des grandeurs physiques (par exemple : densité, porosité, perméabilité).

La problématique de cette thèse concerne la définition de nouveaux outils de visualisation et de calcul sur de telles grilles. Pour la visualisation, cela pose à la fois le problème du stockage et de l’adaptativité des algorithmes à une géométrie et une topologie variables. Pour le calcul, cela pose le problème de la résolution de grands systèmes linéaires creux non-structurés. Pour aborder ces problèmes, l’augmentation incessante ces dernières années de la puissance de calcul parallèle des processeurs graphiques nous fournit de nouveaux outils. Toutefois, l’utilisation de ces GPU nécessite de définir de nouveaux algorithmes adaptés aux modèles de programmation parallèle qui leur sont spécifiques.

Nos contributions sont les suivantes : (1) Une méthode générique de visualisation tirant partie de la puissance de calcul des GPU pour extraire des isosurfaces à partir de grandes grilles fortement non structurées. (2) Une méthode de classification de cellules qui permet d’accélérer l’extraction d’isosurfaces grâce à une présélection des seules cellules intersectées. (3) Un algorithme d’interpolation temporelle d’isosurfaces. Celui-ci permet de visualiser de manière continue dans le temps l’évolution d’isosurfaces. (4) Un algorithme massivement parallèle de résolution de grands systèmes linéaires non-structurés creux sur le GPU. L’originalité de celui-ci concerne son adaptation à des matrices de motif arbitraire, ce qui le rend applicable à n’importe quel système creux, dont ceux issus de maillages fortement non-structurés.

Extrait du sommaire:

Introduction
1 Contexte pratique de la thèse 1
2 Thème d’étude 1
3 Supports de modélisation et problématiques idoines 2
4 Problématiques générales, contributions et organisation du mémoire 4
Visualisation volumique de maillages non-structurés
1.1 Introduction 6
1.2 Extraction d’isosurfaces sur GPU pour des maillages fortement non-structurés 7
1.2.1 Matériel graphique standard 7
1.2.2 Définitions et état de l’art 10
1.2.3 Contributions 21
1.2.4 Notre nouvelle approche générique : Le Marching Cells 22
1.2.5 Applications et performances comparatives 36
1.2.6 Évolutions actuelles et futures 43
1.2.7 Bilan et perspectives 44
1.3 Méthodes d’accélération par classification de cellules 46
1.3.1 Formalisme mathématique 47
1.3.2 Méthodes utilisant un partitionnement 47
1.3.3 Méthodes utilisant une propagation 54
1.3.4 Les Bucket Search adaptatifs 60
1.3.5 Étude comparative théorique et pratique des principales méthodes de classification 63
Table des matières
1.3.6 Bilan 71
1.4 Visualisation avancée : extraction d’isosurfaces 4D continues dans le temps ou
Morphing 4D 72
1.4.1 État de l’art 72
1.4.2 Algorithme général 72
1.4.3 Performances 74
1.4.4 Application à un réservoir pétrolier 76
1.4.5 Bilan et perspectives 78
1.5 Conclusion et perspectives 80
Calculs massivement parallèles sur GPU pour des maillages non-structurés
2.1 Introduction 84
2.2 Problématiques 85
2.2.1 Lissage de surfaces discrètes 85
2.2.2 Paramétrisation de surfaces triangulées 88
2.2.3 Simulation d’écoulement fluide biphasique sur lignes de courant 91
2.3 Les solveurs numériques et leur implantation sur GPU : état de l’art 95
2.3.1 Solveurs itératifs 95
2.3.2 Solveurs directs 100
2.3.3 Bilan sur les méthodes de résolution de systèmes linéaires 101
2.3.4 Nouvelles API, nouvelles possibilités : CUDA et CTM 101
2.3.5 Contributions 102
2.4 Algèbre linéaire sur GPU et matrices creuses génériques : Le Concurrent Number Cruncher 103
2.4.1 Structures de matrices creuses usuelles en calcul haute-performance et produit matrice creuse/vecteur (SpMV) 103
2.4.2 Optimisations pour les GPU 106
2.4.3 Points techniques 110
2.5 Applications et performances 116
2.5.1 Opérations sur des vecteurs 118
2.5.2 Application à la paramétrisation et au lissage de surface 119
2.5.3 Application à la simulation d’écoulement fluide : résolution de l’équation de pression 123
2.5.4 Surcoût, efficacité et précision 127
2.6 Bilan 129
2.6.1 Conclusion 129
2.6.2 Perspectives 129
Conclusion
Table des figures 137
Liste des tableaux 145
Bibliographie 147

Cours accélération matérielle (20)
Télécharger le fichier PDF: Algorithmes sur GPU de visualisation et de calcul pour des maillages non-structurés