<  Back to the Polytechnique Montréal portal

Parallélisation sur processeur graphique des techniques d'adaptation de maillage basées sur la maximisation de la conformité à une métrique riemannienne

William Bussière

Master's thesis (2017)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (5MB)
Show abstract
Hide abstract

Abstract

In numerical fluid mechanics, a way to enhance the precision of an approximate solution while limiting the consumption of computer resources, is to adapt the mesh to the solution's behavior. By an iterative process of consecutive resolution-adaptation phases, the shape and size of the elements are adapted to the curvature of the approximate solution to reduce the interpolation error. With the ever increasing size of the problems studied in numerical fluid mechanics, multiple techniques of parallelization have been developed to reduce the time needed by solvers to compute a solution. However, if the adapters do not benefit from a similar parallelization effort, their computing time would dominate the overall resolutionadaptation iterative process. This study's objective is to determine if GPUs are able to accelerate the adaptation process while producing meshes whose quality matches the one produced by current methods on the CPU. By Céa's lemma, it is known that the approximation error is bounded by the interpolation error. Generated by an a posteriori error estimator, the metric function specifies to the adapter the ideal length of an edge in a given location to obtain a specific interpolation error. Topological and geometrical operations modify an initial mesh in order to uniformize the conformity of its elements to the specified metric. The present study will specifically focus on node relocation algorithms that already demonstrate, in the field of mesh optimization, an ease to be parallelized on GPUs. Although, it is predicted that the manipulation of non simplicial elements and that the precise sampling of a 3D metric function, which are necessary to the adaptation of meshes in numerical fluid mechanics, may cause certain problems for that type of processor. A mesh adaptation software was developed to verify the hypotheses of this research. The entire adaptation process is driven by the measure of metric conformity. On the CPU, the metric function is sampled in a background mesh by local search. The research also proposes to sample the metric function in a texture on the GPU side. A series of node relocation algorithms are implemented and compared on both types of processor, including the Laplacian smoothing, the gradient descent and Nelder-Mead. A new version of the Laplacian smoothing for mesh adaptation in a Riemannian metric is proposed. Furthermore, in addition to the node axis, this study proposes two new parallelization axes for node relocation algorithms: the elements and positions axes. The most important implementation details to port the node relocation algorithms on the GPU are discussed, including processors synchronization and the translation of data structures. Two technologies for the development of GPU kernels are compared: GLSL and CUDA. The results clearly show that the sampling of the metric function by local search is not practical on the GPU because the method is too heavy in terms of instruction count and thread divergence. On the contrary, sampling this function through a texture demonstrates encouraging rates of acceleration. Even though texture sampling presents some precision flaws for the most difficult metric functions, this study demonstrates that by increasing the resolution of the textures by a reasonable amount, it is possible to meet the background mesh's precision. Concerning the node relocation algorithms, the local optimization algorithms stand out from Laplacian smoothing algorithms by their efficacy, as much on tetrahedral than hexahedral meshes. Furthermore, Nelder-Mead stands out from the local optimization algorithms by its high speed on the CPU as well as on the GPU. The newly explored parallelization axes on the GPU has doubled implementations acceleration rates. For example, the gradient descent's multiaxis version is between 48 and 110 times faster than its sequential version while Nelder-Mead's multielement version is approximately 50 times faster than its sequential version. In short, the selected optimal adaptation pipeline samples the metric function in a texture. It uses Nelder-Mead's multielement version, written in CUDA, to move mesh nodes on the GPU. Despite GLSL's high portability compared to CUDA, its implementation of the optimal pipeline shows lower acceleration rates and is often unstable.

Résumé

En mécanique des fluides numérique, une manière d'accroitre la précision d'une solution approchée tout en évitant une consommation excessive de ressources informatiques consiste à adapter le maillage au comportement de la solution. Par un processus itératif de résolution-adaptation, la forme et la taille des éléments sont adaptées à la courbure de la solution approchée afin de réduire l'erreur d'interpolation. Avec la croissance en taille des problèmes étudiés en mécanique des fluides, des techniques de parallélisation ont dû être développées pour réduire le temps de calcul des solveurs. Toutefois, si les adaptateurs ne bénéficient pas d'un effort similaire de parallélisation, leur temps de calcul dominera le processus itératif de résolution-adaptation. L'objectif de la présente recherche est de déterminer si les GPU sont en mesure d'accélérer le processus d'adaptation tout en produisant des maillages d'une qualité équivalente aux méthodes actuellement exécutées par le CPU. Par le lemme de Céa, on sait que l'erreur d'approximation est bornée par l'erreur d'interpolation. Produite par un estimateur de l'erreur a posteriori, la fonction métrique spécifie à l'adaptateur la longueur idéale d'une arête en un endroit donné pour une erreur d'interpolation donnée. Des opérations topologiques et géométriques permettent de modifier un maillage initial afin d'uniformiser la conformité de ses éléments à la métrique spécifiée. La présente recherche s'attardera particulièrement aux algorithmes de déplacement de noeuds qui démontrent déjà, en optimisation de maillage, une certaine facilité à être parallélisés sur le GPU. Toutefois, il est attendu que la manipulation des éléments non simpliciaux et que l'échantillonnage précis d'une fonction métrique 3D, caractéristiques nécessaires pour l'adaptation de maillages en mécanique des fluides numérique, causent certains problèmes sur ce type de processeur. Un logiciel d'adaptation de maillage a été développé pour vérifier les hypothèses de cette recherche. Tout le processus d'adaptation est dirigé par la mesure de conformité à la métrique. Sur le CPU, la fonction métrique est échantillonnée par recherche locale dans un maillage de fond. On propose également une nouvelle technique d'échantillonnage pour la métrique sur le GPU sous forme de texture. Une série d'algorithmes de déplacement de noeuds sont implémentés et comparés sur les deux types de processeurs, dont le lissage laplacien, la descente du gradient et Nelder-Mead. Une nouvelle version du lissage laplacien pour l'adaptation de maillage dans une métrique riemannienne est proposée. Également, en plus de l'axe des noeuds, on propose deux nouveaux axes de parallélisation pour les algorithmes de déplacement de noeuds : l'axe des éléments et l'axe des positions. Les détails d'implémentation les plus importants pour porter les algorithmes de déplacement de noeuds sur GPU sont abordés, tels que la traduction des structures de données et la synchronisation des processeurs. Deux technologies pour le développement de noyau de calcul seront comparées : GLSL et CUDA. Les résultats montrent clairement que l'échantillonnage de la fonction métrique par recherche locale n'est pas praticable sur GPU à cause de son grand volume d'instructions et de la divergence qu'elle induit sur les fils d'exécution, contrairement à l'échantillonnage par texture qui démontre d'encourageants taux d'accélération. Bien que l'échantillonnage par texture présente de petits défauts de précision pour les fonctions métriques les plus difficiles, on démontre qu'en augmentant la résolution des textures dans une mesure raisonnable, il est possible de rejoindre la précision du maillage de fond. Quant aux algorithmes de déplacement de noeuds, les algorithmes d'optimisation locale se démarquent du lissage laplacien par leur efficacité, autant pour les maillages tétraédriques qu'hexaédriques. De plus, Nelder-Mead se démarque des algorithmes d'optimisation locale par sa rapidité sur le CPU et le GPU. Les nouveaux espaces de parallélisation explorés sur le GPU ont permis de doubler le taux d'accélération des algorithmes. Par exemple, la version multiaxe de la descente du gradient est 48 à 110 fois plus rapide que sa version séquentielle et la version multiélément de Nelder-Mead est environ 50 fois plus rapide que sa version séquentielle. En somme, le pipeline d'adaptation de maillage optimal retenu échantillonne la métrique dans une texture et déplace les noeuds à l'aide de la version multiélément de Nelder-Mead écrite en CUDA sur le GPU. Malgré la grande portabilité des implémentations GLSL face aux implémentations CUDA, elles présentent de moins bonnes accélérations pour le pipeline optimal et sont souvent instables.

Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: François Guibault
PolyPublie URL: https://publications.polymtl.ca/2702/
Institution: École Polytechnique de Montréal
Date Deposited: 30 Oct 2017 13:54
Last Modified: 28 Sep 2024 03:46
Cite in APA 7: Bussière, W. (2017). Parallélisation sur processeur graphique des techniques d'adaptation de maillage basées sur la maximisation de la conformité à une métrique riemannienne [Master's thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/2702/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item