THÈSE D'UNIVERSITÉ : Distribution automatique de programmes séquentiels : étude structurelle et expérimentale.

Cyrille Bareau

Juillet 1995

La programmation des architectures parallèles à mémoire distribuée est un problème important mais difficile. Une des approches possibles est la distribution automatique de programmes séquentiels, dirigée par les données. Elle consiste à transformer un programme séquentiel en programme SPMD (Single Program Multiple Data), le partage du contrôle étant guidé par la distribution des données, spécifiée par l'utilisateur. Le but de cette thèse est d'étudier le comportement des programmes répartis générés par cette technique.
Nous avons modélisé le problème afin d'observer la structure de ces programmes. Nous montrons qu'ils sont caractérisés par une propriété forte : toutes leurs exécutions possibles possèdent une même relation de causalité. Ceci amène plusieurs conséquences.
Sur un plan théorique, nous prouvons en particulier la correction de cette technique de compilation, c'est-à-dire que les programmes répartis obtenus produisent le même résultat que les programmes séquentiels dont ils sont issus. Nous proposons également des fondements formels pour l'abstraction de ces programmes, point de départ pour développer des techniques sûres et efficaces d'analyse de traces. Nous définissons une classe de programmes infinis adoptant un comportement régulier, qu'il est possible d'étudier sur une représentation finie.

Sur un plan expérimental, nous montrons l'intérêt d'observer la relation de causalité dans un cadre d'évaluation de performances. En effet, la causalité peut être vue comme un dépliage du graphe de dépendances du programme, ce qui permet de voir les dépendances qui ont été ajoutées par la distribution. De même, la causalité permet de juger de la concurrence d'un programme, et donc de son degré de parallélisme ; nous proposons une mesure de concurrence pour quantifier cette information intuitive. Nous montrons enfin qu'il est possible de déterminer la causalité par simulation du programme séquentiel source. Ces principes d'analyse ont été mis en oeuvre sur des environnements de distribution de programmes, et d'exécution répartie.