THÈSE D'UNIVERSITÉ : Compilation de boucles dirigée par la distribution des données.

Marc Le Fur

Juillet 1995

Cette thèse concerne la compilation de programmes séquentiels impératifs pour machines parallèles à mémoire distribuée. Nous étudions plus particulièrement le problème de la compilation des boucles régulières dans le cadre de l'approche dirigée par le placement des données. Cette approche est qualifiée de semi-automatique puisque le concepteur d'application a la charge de spécifier la distribution des données de son programme dans les mémoires locales des processeurs. Le compilateur dérive ensuite un code parallèle en utilisant une règle qui lie la distribution du contrôle et le placement des données.
Nous présentons un schéma de compilation efficace pour une classe de nids de boucles appelés nids commutatifs. On désigne par là des nids de boucles parfaitement imbriquées comportant une seule affectation dont toutes les instances peuvent commuter cad s'exécuter dans n'importe quel ordre. La classe comprend les boucles parallèles comportant une affectation ainsi que les réductions. Les nids commutatifs constituent fréquemment la structure de contrôle de base dans les applications scientifiques régulières et peuvent de plus être produits par des transformations connues en parallélisation automatique.

Après avoir défini le contexte du travail, la génération de code pour les nids commutatifs est présentée. Nous montrons que les différents codes produits - codes de communication et de calcul - peuvent être caractérisés par un certain nombre de polyèdres. Les algorithmes qui servent de base à la génération de code sont ensuite décrits et concernent le calcul de structures de contrôle dont l'exécution énumère les vecteurs entiers de polyèdres. Le schéma de compilation a été mis en oeuvre au sein du compilateur Pandore ; les expérimentations effectuées montrent l'intérêt du schéma de compilation et de l'exécutif sous-jacent. Enfin, un certain nombre de perspectives sont envisagées dans le cadre du langage HPF.