Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de

Doctorat
Equipe : Architectures parallèles

Compilation sous-polyédrique reposant sur des systèmes à deux variables par inégalité

Début le 01/01/2009
Direction : COHEN, Albert

Financement : A
Etablissement d'inscription : Université Paris-Sud
Lieu de déroulement : INRIA Alchemy & LRI Archi

Soutenue le 13/03/2013 devant le jury composé de :
Cédric Bastoul, Assistant Professor, Université Paris-Sud, Examinateur
Albert Cohen, Directeur de recherche, INRIA, École Normale Supérieure,
Directeur de Thèse
François Irigoin, Professeur, MINES ParisTech, Fontainebleau, Rapporteur
Christian Lengauer, Professor, University of Passau, Germany, Rapporteur
Antoine Miné, Chargé de Recherche, CNRS, École Normale Supérieure, Examinateur
Florent Hivert, Professor, Université Paris-Sud, Examinateur
Sanjay Rajopadhye, Associate Professor, Colorado State University,
USA, Examinateur

Activités de recherche :

Résumé :
Notre étude de la compilation sous-polyédrique est dominée par
l'introduction de la notion l'ordonnancement affine sous-polyédrique,
pour laquelle nous proposons une technique utilisant des
sous-polyèdres (U)TVPI. Dans ce cadre, nous introduisons des
algorithmes capables de construire des sous-approximations de systèmes
de contraintes résultant de problèmes d'ordonnancement affine. Cette
technique repose sur des algorithmes polynomiaux simples pour
approcher un polyèdre quelconque par un polyèdre (U)TVPI. Nos
algorithmes sont suffisamment génériques pour s'appliquer à de
nombreux problèmes d'ordonnancement, de parallélisation, et
d'optimisation de boucles, réduisant leur complexité temporelle à des
fonctions polynomiales.

Nous introduisons également une méthode pour la génération de code
utilisant des algorithmes sous-polyédriques, tirant parti de la faible
complexité des sous-polyèdres (U)TVPI. Dans ce cadre, nous montrons
comment réduire la complexité associée aux générateurs de code les
plus populaires, ramenant la complexité de plusieurs facteurs
exponentiels à des fonctions polynomiales.

Nombre de ces techniques sont évaluées expérimentalement. Pour cela,
nous avons réalisé une version modifiée du compilateur PLuTo, capable
de paralléliser et d'optimiser des nids de boucles pour des
architectures multi-cœurs à l'aide de transformations affines, et
notamment de partitionnement (tiling). Nous montrons qu'une majorité
des noyaux de calcul de la suite Polybench (2.0) peut être manipulée à
l'aide de notre technique d'ordonnancement, en préservant la
faisabilité des polyèdres lors des sous-approximations. L'utilisation
des systèmes approchés par des sous-polyèdres conduit à des gains
asymptotiques en complexité, qui se traduit par des réduction
significatives en temps de compilation, par rapport à un solveur de
programmation linéaire de référence. Nous vérifions également que le
code généré par notre prototype de parallélisation sous-polyédrique
est compétitif par rapport à la performance du code généré par Pluto.