La première partie de la thèse décrit les techniques à
employer pour détecter les scans et les réductions dans un
programme impératif à contrôle statique. Seule la moitié
du travail est effectuée. Il faut maintenant, à partir des
systèmes d'équations dans lesquels les scans sont explicités
à l'aide de l'opérateur Scan, générer un programme
parallèle efficace. La méthode de génération de code
choisie est la méthode la plus efficace à l'heure actuelle,
c'est-à-dire la méthode géométrique présentée en
5.5. Rappelons que le principe de cette méthode est
d'associer une date à chaque opération. Le programme
parallèle comporte alors une boucle externe sur le temps
(ou un nid de boucles si les dates sont cherchées sous
la forme de vecteurs). Le corps de cette boucle est constitué
de nids de boucles parallèles énumérant les opérations
pouvant s'effectuer au temps t.
La méthode géométrique est conçue pour des opérations
atomiques, c'est-à-dire des opérations d'affectations. Nos
systèmes d'équations contiennent des opérations complexes :
les scans. Une adaptation de la méthode est donc nécessaire.
La première adaptation concerne le calcul des dates d'exécution
des opérations. Le modèle que nous avons retenu est de
considérer un scan comme un ensemble d'opérations atomiques.
Une opération atomique calcule un résultat partiel du scan.
Cette vision des scans permet d'utiliser, avec des modifications
mineures, les algorithmes classiques de calcul de base de temps.
Les modifications à apporter sont présentées dans le premier
chapitre de cette partie. Le seconde chapitre montre que deux
types de code parallèle peuvent être générés. Il est
difficile de déterminer lequel des deux est le plus efficace.
Une heuristique de choix basée sur le type de la machine cible
et sur les possibilités du langage de programmation cible
est présentée.
Enfin, un code parallèle a été généré manuellement
pour deux exemples, dans le but de valider la méthode de
détection de scans (i.e. montrer que des accélérations
sont possibles) et pour recenser les problèmes
pratiques qui peuvent se poser lors d'une génération de
code pour des scans.