Prénom : William
Nom de famille : Bussière
Biographie : L'ingénierie du logiciel en tant qu'art
Intérets : I = {jonglerie, monocycle, clarinette, littérature}
Travail : Maîtrise en Génie Informatique
Résidence : Montréal, Qc
Je termine présentement ma maîtrise en génie informatique à l'École Polytechnique de Montréal. Mon sujet de recherche porte sur la parallélisation d'algorithmes d'adaptation et d'optimisation de maillage sur GPU. Parallèlement à mes études, j'ai aussi exécuté quelques projets personnels. Ces expérimentations tournent toujours autour de problèmes géométriques et de techniques de rendu. Le meilleur exemple est The Fruit - A Moving Picture, une courte animation dessinée par tracé de chemin (path tracing) dont la géométrie est composée uniquement de surfaces analytiques combinées par opérations booléennes. L'engin de rendu, l'éditeur/animateur et le compositeur qui ont permis sa production ont été codés de zéro.
Les maillages non structurés, en mécanique des fluides numérique, comportent généralement plusieurs millions de noeuds et doivent être adaptés à la géométrie du problème ainsi qu'à la distribution spatiale des propriétés du fluide (vitesse, pression, température, etc.). Présentement, la résolution itérative des problèmes par alternance d'étapes de résolution et d'adaptation représente l'état de l'art. En amorçant le processus avec un maillage grossier, il est possible d'obtenir des solutions de plus en plus précises et des maillages de mieux en mieux adaptés plus le nombre d'itérations est élevé. Ces dernières années, beaucoup d'efforts ont été investis dans la parallélisation des méthodes de résolution, que ce soit pour la méthode des Éléments Finis (FEM), des Volumes Finis (FVM) ou des différences finies (FDM). Cependant, l'adaptation de maillage représente une part importante du temps de calcul sur l'ensemble du processus itératif. Si un effort comparable de parallélisation ne lui est pas accordé, on verra bientôt cette étape déterminer fortement le temps de calcul total pour obtenir une solution précise en mécanique des fluides numérique.
L'adaptation de maillage se divise en deux types d'opérations : opérations topologiques et déplacement de noeuds. L'intérêt pour le GPU vient de son étonnante puissance de calcul en arithmétique flottante (de l'ordre de quelques téraFLOPS pour une unique carte graphique), délivrée sous forme de milliers de coeurs. Contrairement aux opérations topologiques, le déplacement de noeuds présente un certain potentiel à être parallélisé sur GPU. L'introduction d'une métrique riemannienne complique toutefois les choses. Une simple transposition des algorithmes développés pour le CPU vers le GPU offre des performances désastreuses. Essentiellement, trois causes sont à l'origine de cette décélération. Premièrement, les coeurs d'un GPU ont une cadence d'exécution plus lente que ceux d'un CPU. Deuxièmement, les algorithmes les plus sophistiqués ont tendance à faire diverger les threads d'un même bloque à cause des branchements conditionnels. Finalement, la technique qui consiste à échantillonner la métrique sur un maillage de fond n'est pas du tout adaptée au GPU et fait elle aussi diverger les threads. La divergence est nuisible parce qu'elle force le GPU à exécuter des séries d'instructions séquentiellement, nous privant ainsi d'une portion de sa puissance de calcul.
Ces problèmes de divergence semblent toutefois contournables. Cela passe d'abord par la conception de nouveaux algorithmes de déplacement de noeuds. Il faut tirer parti de l'architecture matérielle du GPU de manière à réduire au maximum les branchements conditionnels, ou du moins en uniformisant l'exécution des threads. Puis, il faut trouver une solution de rechange à l'échantillonnage de la métrique. Localiser l'élément contenant notre échantillon dans le maillage de fond non structuré semble être une opération trop imprévisible. L'utilisation d'une structure de données différente, comme une grille uniforme stockée sous forme de texture, semble être la voie à suivre.
First Name: William
Second Name: Bussière
Biography: Software Engeering as an Art
Interests: I = {jugglery, unicycle, clarinet, literature}
Occupation: Master of Computer Science
Location: Montreal, Qc
I'm currently completing my master degree of computer science at l'École Polytechnique de Montréal. My research focuses on implementing parallel algorithms for mesh optimization and adaptation on the GPU. I have also completed a number of projects alongside my studies. These experiments always involve geometric problems and rendering techniques. The best example might be The Fruit - A Moving Picture, a short animation film rendered by path tracing analytical surfaces combined with Boolean operators. The rendering engine, editor/animator and compositor used to produce this animation where coded from scratch.
Translation is coming soon ...