Détection de parallélisme dans les boucles imbriquées.
Date: Décembre 1997
Résumé :
Nombre d'utilisateurs de l'informatique aimeraient pouvoir exécuter sur des ordinateurs
parallèles leurs programmes « séquentiels » (écrits pour être exécutés sur des ordinateurs
classiques). Il est donc devenu nécessaire de savoir « paralléliser » les programmes séquentiels en
programmes exécutables sur machines parallèles. Cette parallélisation doit être automatique
puisqu'elle s'adresse le plus souvent à de simples utilisateurs. Avant d'initier toute
transformation du programme originel, il faut détecter et quantifier le parallélisme qu'il contient
implicitement, ce qui requiert la connaissance des dépendances existant entre les différents
calculs. Ultérieurement, il sera nécessaire de réordonner les calculs en explicitant le
parallélisme découvert. Cette thèse a pour objet la détection automatique du parallélisme implicite
et la recherche d'ordonnancements l'explicitant pour des structures de programmes particulières :
les ensembles de boucles imbriquées. Nos travaux ont eu principalement pour but la compréhension
des techniques existantes de détection de parallélisme, de leur points forts et de leurs
limitations. D'un côté, nous avons étudié les principaux algorithmes préexistant à ces travaux. De
l'autre, nous sommes partis du modèle théorique fourni par les systèmes d'équations récurrentes
uniformes pour proposer un algorithme optimal de parallélisation des graphes de dépendance réduits
polyédriques, représentation approchée des dépendances qui généralise les deux modes classiques
d'approximation. Nous avons comparé ce nouvel algorithme aux algorithmes classiques et obtenu une
classification des principaux algorithmes. Le problème de la détection du parallélisme et de son
expression n'étant qu'une des multiples composantes de la parallélisation automatique, nous nous
sommes intéressés aux interactions entre les problèmes de placement et d'ordonnancement, et entre
les problèmes de détection de parallélisme et d'élimination de « fausses » dépendances.
