La première partie de cette thèse introduit la notion
de parallélisation automatique (voir chapitre 4).
Les concepts fondamentaux sont présentés, puis l'architecture
d'un compilateur parallèle particulier est étudiée dans le
chapitre 5. Il s'agit du compilateur PAF de l'équipe du
Professeur P. Feautrier. Nous profitons de l'occasion pour
montrer, sur un exemple, les différentes techniques utilisées
par les compilateurs modernes pour paralléliser un programme.
La façon dont les récurrences sont traitées par ces
compilateurs est alors évoquée dans le chapitre 6.
Il est montré qu'un paralléliseur efficace doit détecter ces
récurrences pour exploiter le parallélisme implicite de certaines
d'entre elles : les scans et les réductions. Un état de l'art sur
la détection des récurrences est donné en fin de partie.
La seconde partie décrit une nouvelle méthode de détection
de scans et de réductions basée sur les systèmes d'équations
récurrentes. Le chapitre 7 montre comment il est
possible de transformer un programme impératif en système
d'équations récurrentes. Ensuite, les grandes lignes de la
méthode sont expliquées, en particulier la technique de
normalisation du système par des substitutions. Cette normalisation
est très importante puisqu'elle permet d'accélérer la détection
des réductions et des scans. C'est pourquoi un chapitre entier (le
chapitre 8) est consacré aux algorithmes de
normalisation d'un système. Il est intéressant de constater
que ces algorithmes sont très proches d'algorithmes classiques
de la théorie des graphes. Le chapitre suivant (chapitre 9)
présente une forme condensée (l'opérateur Scan) pour exprimer les
scans. Cette forme facilite la détection de récurrences spéciales :
les récurrences multi-directionnelles. Une analyse des formes
d'expression des récurrences déjà existantes montre que
l'opérateur Scan est plus adapté à nos besoins.
Enfin le dernier chapitre de cette partie, le chapitre
10, montre que les réductions et les scans peuvent
être détectés simplement dans un système normalisé.
Les expressions des équations sont analysées, lorsqu'elles
correspondent à des réductions ou des scans un opérateur
Scan est introduit dans le système d'équations.
Une fois les réductions et les scans détectés, il faut encore
savoir comment utiliser l'information pour produire un code parallèle
efficace. C'est la problématique de la dernière partie.
Le chapitre 11 explique comment calculer une base de temps
pour un système d'équations contenant des réductions ou des
scans explicites. Le chapitre 12 montre que, pour chaque
scan, deux codes différents peuvent être générés. Il n'est
pas facile de déterminer lequel des deux codes est le plus performant.
Une heuristique en fonction de la base de temps du scan et de celle des
données du scan peut tout de même être établie.
Ce chapitre montre aussi
quelles techniques doivent être utilisées pour générer
automatiquement du code. Le dernier chapitre (chapitre 13)
détaille deux
exemples de génération de code pour un processeur vectoriel d'un
Cray Y-MP. Les résultats des tests montrent que les codes générés
par notre méthode sont plus efficaces que ceux générés par le
Cray-Fortran qui, pourtant, détecte déjà quelques réductions.
