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

Soutenance de thèse : Clément ROSSETTI

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

Date et heure :Jeudi 18 Décembre 2025, à 9h
Lieu : Amphi A301, Pole API, 300 bd Sébastien Brant, Illkirch-Graffenstaden

Jury :

• Directeur de thèse:
  Pr. Philippe CLAUSS, Professeur des Universités, HDR, Université de Strasbourg
• Rapporteurs :
  Pr. Isabelle PUAUT, Professeure des Universités, HDR, Université de Rennes
  Pr. Sid TOUATI, Professeur des Universités, HDR, Université Côte d'Azur
• Examinateurs:
  Dr. Fabrice Rastello, Directeur de recherche, HDR, Université Grenoble Alpes
  Dr. Christophe Alias, Chargé de recherche, HDR, ENS Lyon

Résumé

Ce manuscrit introduit une nouvelle technique d'optimisation de boucles nommée pavage algébrique. Basée sur le modèle polyédrique, cette méthode vise à améliorer l'équilibre de charge entre les threads lors de la parallélisation de boucles. En divisant l'espace d'itération en pavés définis par leur volume, c'est-à-dire le nombre d'itérations qu'ils contiennent, plutôt que par leur taille, cette méthode permet d'atteindre un équilibre de charge quasi-parfait lors d'exécutions parallèles. Les bornes des pavés sont déterminées dynamiquement à l'exécution à l'aide d'expressions algébriques appelées expressions trahrhe.  Le pavage algébrique a été étendu pour prendre en charge les calculs par stencil en introduisant le pavage algébrique trapézoïdal. Avec cette approche, les pavés prennent la forme de trapèzes afin de s'adapter aux dépendances de données des stencils, en étant toujours définis par leur volume. Cela permet de maintenir un bon équilibre de charge tout en respectant les dépendances inhérentes aux calculs par stencil. Nos contributions ont été évaluées sur divers benchmarks par rapport aux compilateurs polyédriques existant dans l'état de l'art, et ont montré des améliorations significatives en termes d'équilibre de charge et de temps d'exécution. Le pavage algébrique a été automatisé dans un nouveau compilateur source-à-source nommé Pesto, capable de générer du code C parallèle annoté avec des directives OpenMP à partir d'un code C séquentiel.