Note ABES Algebraic tiling : volume-guided tiling of parallel loops for near-perfect load balancing Pavage algébrique : pavage de boucles parallèles guidé par le volume pour un équilibre de charge quasi-parfait Calcul haute performance Compilation polyédrique Optimisation de boucles Parallélisme Parallélisation Automatique Pavage Stencils High-performance computing Polyhedral compilation Loop optimization Parallelization Automatic Parallelization Tiling Stencils 004 Calcul intensif (informatique) 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. In this thesis, we propose a novel loop optimization entitled algebraic tiling. Based on the polyhedral model, this method improves load balancing among threads when parallelizing loops. By dividing the iteration space into tiles defined by their volume (number of iterations) instead of their size, this method achieves near-perfect load balancing across parallel executions. Bounds of tiles are determined dynamically at execution time by using algebraic expressions called trahrhe expressions. Algebraic tiling was extended to support stencil computations by introducing trapezoidal algebraic tiling. With this approach, tiles are shaped as trapezoids to better fit the data dependencies of stencils, while still being defined by their volume. Our contributions have been evaluated against state-of-the-art polyhedral compilers and showed significant improvements. Algebraic tiling has been automated in a new source-to-source compiler named Pesto that generates parallel C using OpenMP. Electronic Thesis or Dissertation Text en PDF 1237378 https://publication-theses.unistra.fr/public/theses_doctorat/2025/ROSSETTI_Clement_2025_ED269.pdf http://www.theses.fr/2025STRAD055/abes https://theses.hal.science/tel-05514733 https://theses.hal.science/tel-05514733 https://theses.hal.science/tel-05514733 Rossetti Clément 1999-04-21 FR 293918597 0210040610L 21920749 4200018 http://www.theses.fr/2025STRAD055 2025STRAD055 2025-12-18 Informatique Strasbourg 131056549 Doctorat Docteur es non oui Clauss Philippe MADS_DIRECTEUR_DE_THESE_1 2700 098478389 Rastello Fabrice MADS_PRESIDENT_DU_JURY 149155727 Alias Christophe MADS_MEMBRE_DU_JURY_1 195246446 195246446 Puaut Isabelle MADS_RAPPORTEUR_1 071169733 Touati Sid-Ahmed-Ali MADS_RAPPORTEUR_2 078662931 École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....) MADS_ECOLE_DOCTORALE_1 269 156504863 Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (Strasbourg ; 2013-....) MADS_PARTENAIRE_DE_RECHERCHE_1 260728 176969721 ddc:004 Clauss Philippe Rastello Fabrice Alias Christophe Puaut Isabelle Touati Sid-Ahmed-Ali École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....) Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (Strasbourg ; 2013-....) PDF 1237378