Pavage algébrique : pavage de boucles parallèles guidé par le volume pour un équilibre de charge quasi-parfait

Dans cette thèse, nous présentons le pavage algébrique, une nouvelle technique d’optimisation de boucles fondée sur le modèle polyédrique. Contrairement au pavage rectangulaire classique basé sur une taille fixe de pavés, cette approche divise l’espace d’itération en pavés définis par leur volume (nombre d’itérations), permettant un équilibre de charge quasi parfait lors de la parallélisation. Les bornes des pavés sont calculées dynamiquement à l’exécution grâce à des expressions algébriques appelées expressions trahrhe. Une extension de cette technique, le pavage algébrique trapézoïdal, adapte les pavés aux dépendances des calculs stencil tout en conservant un volume contrôlé. Les résultats expérimentaux montrent des gains significatifs face aux compilateurs polyédriques existants. Ces méthodes ont été implémentée sdans le compilateur source-à-source Pesto, générant du code C parallèle avec OpenMP.