Abstract FR:

Dans le cadre de la parallelisation automatique des programmes sequentiels, et plus particulierement des nids de boucles, ce travail propose une methode de generation de code pour machines paralleles a memoire distribuee. On considere que le programme initial est exprime sous la forme d'un systeme d'equations recurrentes affines. Le modele look forwards caracterise: pour une valeur, l'ensemble des points de calcul qui l'utilisent. C'est l'ensemble d'utilisation, pour un domaine de calcul, l'ensemble des points qui emettent une valeur vers d'autres points. C'est l'ensemble d'emission. On definit un ordonnancement et un placement des calculs sous la forme de fonctions affines, ce qui revient a definir une transformation permettant de representer l'ensemble des points de calcul dans une base temps-espace. Dans ce cadre, pour generer le code parallele du probleme donne, et selon la transformation donnee, il suffit de parcourir dans la nouvelle base les domaines de calcul, et les ensembles d'utilisation et d'emission. Cette these expose le processus complet de parallelisation d'un systeme d'equations recurrentes, mais s'interesse en particulier a la generation des communications dans le cadre de dependances affines. C'est dans ce cadre qu'un nouvel algorithme est propose. Il genere le nid de boucles parcourant l'image d'un convexe par une application singuliere. Il permet, a l'interieur de la methode globale proposee, de definir le parcours des ensembles d'emission dans la base temps-espace. Dans le cas de l'utilisation multiple d'une valeur, on propose la transmission de cette valeur vers l'ensemble des processeurs utilisateurs sous deux formes possibles: une diffusion totale de l'emetteur vers les processeurs utilisateurs ou une diffusion partielle vers une partie de ces processeurs, suivie d'une propagation. Deux exemples significatifs illustrent les resultats obtenus