Algorithmes sur GPU de visualisation et de calcul pour des maillages non-structurés, Algorithms on the GPU for visualization and computations on unstructured grids

Luc Buatois

Description

Sous la direction de Jean-Claude Paul, Bruno Levy
Thèse soutenue le 16 mai 2008: INPL
De nombreux domaines utilisent à présent de nouveaux types de grilles composées de polyèdres arbitraires, autrement dit des grilles fortement non-structurées. 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 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
-Maillages non-structurés
-Extraction d'isosurfaces
-Solveurs numériques creux
-GPU
This thesis proposes new tools for visualization and computation on strongly unstructured grids. Visualization of such grids that have variable geometry and topology, poses the problem of how to store data and how algorithms could handle such variability. Doing computations on such grids poses the problem of solving large sparse unstructured linear systems. The ever-growing parallel power of GPUs makes them more and more valuable for handling theses tasks. However, using GPUs calls for defining new algorithms highly adapted to their specific programming model. Most recent algorithms for Geometry Processing or Computational Fluid Dynamics (CFD) are using new types of grids made of arbitrary polyhedra, in other words strongly unstructured grids. In case of CFD simulations, these grids can be mapped with scalar or vector fields representing physical properties (for example : density, porosity, permeability). Our contributions are: (1) An efficient generic visualization method that uses GPU's power to accelerate isosurface extraction for large unstructured grids. (2) An adaptative cell classification method that accelerates isosurface extraction by pre-selecting only intersected cells. (3) An efficient algorithm for temporal interpolation of isosurfaces. This algrithm helps to visualize in a continuous maner the evolution of isosurfaces through time. (4) A massively parallel algorithm for solving large sparse unstructured linear systems on the GPU. Its originality comes from its adaptation to sparse matrices with random pattern, which enables to solve any sparse linear system, thus the ones that come from strongly unstructured grids
-Unstructured grids
-Sparse numerical solvers
-Isosurface extraction
-GPU
Source: http://www.theses.fr/2008INPL020N/document

Sujets

• GPU

Informations

• Publié par: Thesee
• Nombre de lectures: 36
• Langue: Français
• Poids de l'ouvrage: 6 Mo

Extrait

AVERTISSEMENT



Ce document est le fruit d’un long travail approuvé par le jury de
soutenance et mis à disposition de l’ensemble de la communauté
universitaire élargie.
Il est soumis à la propriété intellectuelle de l’auteur au même titre que sa
version papier. Ceci implique une obligation de citation et de
référencement lors de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction illicite entraîne une
poursuite pénale.

Contact SCD INPL : [e-mail]




LIENS




Code de la propriété intellectuelle. Articles L 122.4
Code de la propriété intellectuelle. Articles L 335.2 – L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
Laboratoire LIAD/LORIA
Institut National
Ecole doctorale IAEM
Polytechnique de Lorraine
Algorithmes sur GPU de visualisation
et de calcul pour des maillages
non-structures
THESE
presentee et soutenue publiquement le 16 mai 2008
pour l’obtention du
Doctorat de l’Institut National Polytechnique de Lorraine
Specialite Informatique
par
Luc BUATOIS
Composition du jury
Rapporteurs : Georges-Pierre BONNEAU
Jean-Michel DISCHLER
Examinateurs : Sylvain LEFEBVRE
Jean-Laurent MALLET
Guillaume CAUMON
Directeurs : Jean-Claude PAUL
Bruno LEVY
Centre de Recherches Petrographiques et Geochimiques
Laboratoire d’Infographie et d’Analyse de Donnees
Rue du Doyen Marcel Roubault - 54500 Vand uvreRemerciements
Je tiens a remercier M. Bruno Levy pour m’avoir oriente a la n de mon DEA vers le
consortium Gocad, pour avoir dynamiquement co-encadre ma these et plus particulierement
pour toutes les discussions piquantes et passionnantes que nous avons pu avoir. Je remercie
egalement vivement M. Jean-Laurent Mallet pour m’avoir donne la chance de realiser cette
these. Je tiens a remercier tout particulierement Guillaume Caumon, nouveau jeune directeur
du consortium Gocad, pour avoir co-encadrer ma these avec autant d’energie et d’enthousiasme,
pour avoir su me guider quand j’en avais besoin dans ma petite parcelle d’etude perdue dans
l’immensite du monde fascinant qu’est celui de la recherche, ainsi que pour avoir pris le temps
de relire et corriger la quasi totalite des drafts des papiers que nous avons co-ecrit. Je souhaite
bien evidemment remercier les membres de mon jury et plus particulierement mes rapporteurs.
Je remercie egalement tous les membres du consortium Gocad pour avoir nance ma these, et
touslesmembresdel’administrationpourleurbonnehumeuretleurdynamisme.Enparticulier,
je souhaiterais remercier Monique, Fatima et Isabelle pour l’aide precieuse qu’elles apportent au
LIAD et au LORIA.
Cˆote LIAD, je souhaite remercier Sarah (la gentille ragoteuse, toujours souriante et parfois
piquante), Manu (une creme, consensuel est son deuxieme prenom et Calimero son troisieme),
Pimu(labonnehumeurincarnee),Laetitia(lasudistequin’agardequelesbonscˆotesdesgensdu
sud!AquandleprochaintheaSF?Tuvois,jenesuispasqu’unelanguedevipere),Anne-Laure
(notre Geekette preferee, et de loin! Et vive Rhapsody!), Remi (le plus sympa des amateurs de
bonne biere), Laurent C. (LE sportif du labo a la voix qui chante), Tobias (pour qui le mot
performance n’est pas qu’un argument marketing), Bruno Le on (camarade ou adversaire sur
les champs de bataille), Thomas (calme et sympa, il a invente le egme a la francai se), Vincent
(notre belge prefere, bien meilleur que Daerden), Marco (le seul a ˆetre capable de manger des
sauterelles grillees avec du caman tout en gardant le sourire!), Pauline C. (un concentre de
sourire, de bonne humeur, et de ragotages, bref tout ce qui manquait a ce labo depuis quelques
mois... la releve de Sarah semble assuree...), et tant d’autres : Lise, Christophe, Pauline D.,
Pierre K., Sophie et bien suˆr Christian qui nous manque a tous.
Cˆote LORIA, je souhaite grandement remercier un ami de longue date, Sylvain, pour avoir
supporte sans rien dire mes long discours sur pourquoi les cartes graphiques c’est plus plus
mieux, si on remonte un peu dans le temps, pourquoi le FX7 etait plus plus mieux que les Ixus,
et si l’on remonte encore plus loin pourquoi un Thunderbird etait plus plus mieux qu’un PIV
a 1.4GHz. Je remercie egalement Cedric (qui voit toujours la vie en Rose!), Jamal (-itude),
Arnaud (le backstab est une seconde nature chez lui) et Matthieu (le skin-surface man!).
Jesouhaiteremerciertousceuxsansquijen’auraispaseulecouraged’allerjusqu’auboutde
mes travaux, tous ceux qui m’ont soutenu durant ces annees d’etudes et, plus particulierement,
mongrand-pere,monpere,monfrereetmaCelinepourcequiestdemafamille,etValetAnne-
C, Pat et Chris, Gilles, David et Alexandra, Thibaud, et enn Dorte pour mes amis (pardon si
j’oublie des noms).
Plus serieusement, je souhaite remercier J-C, Chk, Bruce, Steven, Sly, Arnold, ainsi que
Tobias,Tarja,Tuomas,Bruceettantd’autrespourdisonsleursoutienpassif maisinconditionnel.
iPour nir, je souhaite remercier une personne qui se reconnaˆtra :
iiA ma famille, mes amis, et mon soleil...
iii