Résumé
La parallélisation de structures de données dynamiques et
irrégulières peut être un problème plutô difficile. Une
solution efficace demande souvent que le travail sur la structure
soit distribué parmi les différents processeurs. En dépit du
nombre croissant de telles applications, peu de recherche a été
menée sur les approches générales à utiliser dans de tels
cas. C'est dû en partie à l'extrême difficulté d'assurer
assez de généralité en tenant conte de l'utilité et en
s'assurant que chaque problème est traité d'une façon
efficace. Les problèmes irréguliers et dynamiques varient
énormément, et les solutions directes et efficaces n'existent
tout simplement pas. La plupart des tentatives par conséquent,
se sont concentrées sur les champs spécifiques à un problème
particulier où de bons résultats peuvent être obtenus en
sacrifiant la généralité, ou bien sont retombées sur les
méthodes heuristiques qui s'appliquent à plus ou moins n'importe
quelle situation.
Cette thèse présente une méthode hybride qui combine une
approche axée sur le problème et un système assez général
pour être applicable dans la majorité des cas. Notre méthode se
base sur les transformations locales de graphes; si la structure de
données ne change pas de façon majeure, la parallélisation ne
devrait pas non plus. En représentant les manipulations de la
structure de données par un formalisme de grammaire de graphe
particulier, nous pouvons montrer des bornes déterministes sur la
qualité de la division du travail qui en résulte. Cependant,
parce que notre formalisme est raisonnablement général et peut
accommoder plusieurs des structures de données communes (et permet
une variation considérable), nous avons une stratégie
générale pour attaquer les problèmes nécessitant des
structures dynamiques et basées sur des pointeurs (pointer-based).
L'utilité de notre technique est établie par son application
non-triviale à un problème vraisemblable: la génération de
grilles pour les domaines irréguliers dans la méthode ``Control
Volume Finite Element'' qui est utilisée dans la dynamique de
fluides de calcul (computational fluid dynamics). D'abord nous
démontrons un algorithme qui trouve la solution au problème, et
ensuite nous démontrons notre approche. Les bornes théoriques
pour les issues concernant la division pertinente à la
parallélisation sont ensuite données, et appuyées par les
mesures expérimentales. Nous comparons notre méthode aux
méthodes heuristiques qui existent déjà pour assurer que nos
résultats soient compétitifs. Notre méthode nous donne des
résultats de bonne qualité avec un nombre d'avantages à
comparer avec autres techniques, particulièrement quand elle
s'applique aux situations dynamiques.
(Merci beaucoup à Carrol Dufault pour la traduction. Any
mistakes are undoubtedly mine -- c.v.)