%%
%% $Id$
%%
%% Copyright 1989-2016 MINES ParisTech
%%
%% This file is part of PIPS.
%%
%% PIPS is free software: you can redistribute it and/or modify it
%% under the terms of the GNU General Public License as published by
%% the Free Software Foundation, either version 3 of the License, or
%% any later version.
%%
%% PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
%% WARRANTY; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE.
%%
%% See the GNU General Public License for more details.
%%
%% You should have received a copy of the GNU General Public License
%% along with PIPS.  If not, see <http://www.gnu.org/licenses/>.
%%
\documentclass[12pt]{article}

\usepackage[latin1]{inputenc}
\input{/usr/share/local/lib/tex/macroslocales/Dimensions.tex}
\newcommand{\domain}[2]{\paragraph{{#1}}\paragraph{}{\em #2}}
\newcommand{\titre}{RAPPORT D'AVANCEMENT \\
                    ANALYSE SEMANTIQUE ET DETECTION DU PARALLELISME}
\newcommand{\auteur}{François IRIGOIN \\
        Pierre JOUVELOT \\
        Rémi TRIOLET}
\newcommand{\docdate}{Septembre 1989}
\newcommand{\numero}{E116}

\newcommand{\SEC}[1]{\section{#1}}
\newcommand{\SSE}[1]{\subsection{#1}}
\newcommand{\SSS}[1]{\subsubsection{#1}}
\newcommand{\PAR}[1]{\paragraph{#1}}
\newcommand{\SPA}[1]{\subparagraph{#1}}
\newcommand{\BQU}{\begin{quote}}
\newcommand{\EQU}{\end{quote}}
\newcommand{\BIT}{\begin{itemize}}
\newcommand{\EIT}{\end{itemize}}
\newcommand{\BDE}{\begin{description}}
\newcommand{\EDE}{\end{description}}
\newcommand{\BEQ}{\begin{equation}}
\newcommand{\EEQ}{\end{equation}}
\newcommand{\BAR}{\begin{array}}
\newcommand{\EAR}{\end{array}}
\newcommand{\BDO}{\begin{document}}
\newcommand{\EDO}{\end{document}}
\newcommand{\BCE}{\begin{center}}
\newcommand{\ECE}{\end{center}}
\newcommand{\BTG}{\begin{tabbing}}
\newcommand{\ETG}{\end{tabbing}}
\newcommand{\BTR}{\begin{tabular}}
\newcommand{\ETR}{\end{tabular}}
\newcommand{\BAB}{\begin{abstract}}
\newcommand{\EAB}{\end{abstract}}
\newcommand{\BEN}{\begin{enumerate}}
\newcommand{\EEN}{\end{enumerate}}
\newcommand{\BFI}{\begin{figure}}
\newcommand{\EFI}{\end{figure}}
\newcommand{\VSP}{\vspace*{\baselineskip}}

\setlength{\parindent}{0cm}

\begin{document}
\input{/usr/share/local/lib/tex/macroslocales/PageTitre.tex}
\sloppy

\SEC{Introduction}
\PAR{}
Ce rapport intermédiaire donne l'état d'avancement de nos travaux sur
l'analyse sémantique et la détection du parallélisme. Une part
importante de ces travaux est représenté par le calcul du graphe de
contrôle d'un module que nous présentons en détail dans la
section~\ref{controle}. Ce graphe de contrôle est ou sera utilisé par
plusieurs phases de PIPS, et notamment:
\BIT
\item la phase d'analyse sémantique pour construire les équations
sémantiques associées à un programme,

\item par la phase de détection de parallélisme pour déterminer
si une boucle peut être parallélisée, même dans le cas où elle
contient des instructions de branchements non structurées, 

\item par la phase de calcul des use-def chains, 

\item etc...
\EIT

Nous présentons dans la suite l'état d'avancement de la phase de
détection du parallélisme (section~\ref{kennedy}), les structures de
données et l'algorithme mis en oeuvre pour le calcul du graphe de
contrôle (section~\ref{controle}), et l'état d'avancement de la phase
d'analyse sémantique (section~\ref{semantique}).

\SEC{Détection du parallélisme}
\label{kennedy}
\PAR{}
Une phase de détection du parallélisme est en cours de développement
dans le projet PIPS. Dans un premier temps, nous nous sommes restreints
à l'algorithme de Kennedy et Allen appliqué aux boucles ne contenant
que des instructions d'affectation.

\PAR{}
Le calcul du graphe de dépendances (voir la structure de données dans
l'annexe 1) est effectuée selon les techniques de calcul linéaire
développées au CAI et qui seront présentées dans les prochains
rapports. Les programmes de calcul du graphe de dépendances font
massivement appel à la bibliothèque linéaire développée au CAI dans
le cadre d'un contrat avec le PRC $C^3$.

\PAR{}
Le calcul des composantes fortement connexes du graphe des dépendances
et le tri topologique de ces composantes sont faits en utilisant des
algorithmes classiques, présentés dans l'ouvrage {\em TYPES DE DONNEES
ET ALGORITHMES --- Recherche, Tri, Algorithmes sur les Graphes} par
Marie-Claude GAUDEL, Michèle Soria et Christine Froidevaux dans la
collection Didactique de l'INRIA.

\PAR{}
L'algorithme de Kennedy proprement dit est celui présenté dans la
revue {\em ACM TOPLAS} volume 9, numéro 4 de Octobre 1987. Nous donnons
dans l'annexe 3 quelques résultats obtenus avec la première version de
cette phase; la boucle est affichée avant et après transformation par
le pretty-printer de PIPS. Les temps d'execution indiqués sont ceux de
la phase de parallélisation uniquement, les temps du parser et du
linker ne sont pas comptés.

\SEC{Construction du graphe de contrôle}
\label{controle}
\PAR{}
Si l'arbre de syntaxe abstraite représente la structure statique d'un
programme, le graphe de contrôle en est le pendant dynamique; il
associe à chaque instruction la liste de ses prédecesseurs et
successeurs possibles dans toute exécution du programme. Cette
structure de donnée est importante pour effectuer toute analyse
sémantique {\em flow-sensitive} tels les chaines {\em use-def} ou le
calcul de prédicats. De plus, elle intervient dans la détection du
parallélisme avec la notion de {\em masquage de contrôle} qui permet
de paralléliser des boucles contenant des instructions de branchement
locaux.

\PAR{}
Nous décrivons dans la section 1 les structures de données impliquées
dans le graphe de contrôle et présentons l'idée générale de
l'algorithme dans la section 2. Le listing commenté du programme est
donné en annexe 2.

\SSE{Le graphe de contrôle}
\PAR{}
La majorité des programmes utilisateurs sont (ou devraient) être
structurés. Prenant ce fait en considération, nous avons concu le
graphe de contrôle comme une extension de l'arbre de syntaxe abstrait.
Les structures de données structurées (i.e., boucle, conditionnelle,
séquence et instruction élémentaire) sont préservées telles quelles
dans le graphe de contrôle tandis que seuls les branchements
``cassent'' cette structure hiérarchique pour créer un graphe
orienté. Ceci permettra de traiter de manière simple les parties
parallélisables d'un programme, puisque les ruptures de contrôle
empêchent généralement toute parallélisation (mais voir ci-dessous).
Un tel graphe de contrôle est appellé {\em Structured Control Graph}.

\PAR{}
Cette intégration du graphe de contrôle avec les instructions du
programme se reflète dans sa description récursive dans le fichier de
description NewGen:

\begin{verbatim}
control = statement x predecessors:control* x successors:control* ;
instruction = block:statement* + test + loop + ploop + goto:statement + 
              call + unstructured:control ;
statement = label:entity x number:int x instruction x effects:effect* ;
\end{verbatim}

\PAR{}
Dans un noeud du graphe de contrôle, le champ {\tt statement} sera toujours
structuré; cet invariant est introduit par l'algorithme de création du
graphe de contrôle. Dans la majorité des cas, les champs {\tt
predecessors} et {\tt successors} auront des listes réduites à un
élément. Seule une instruction de branchement conditionnelle (dont le
{\tt statement} est un {\tt test}) créera une liste {\tt successors}
ayant plus d'un élément, le premier correspondant au branchement dans
le cas où la condition est vérifiée. Des noeuds de jointure pourront
avoir plus d'un prédécesseur.

\PAR{}
La liste des type d'instructions possibles d'un programme a été
augmentée d'un champ {\tt unstructured} qui apparaitra après
construction du graphe de contrôle; il n'est jamais introduit par les
phases précédentes de PIPS.

\PAR{}
Ce graphe de contrôle implémente la notion importante de {\em
masquage de contrôle}. Par exemple, si une boucle utilise un corps qui
comporte des branchements locaux (ceci est vérifié au cours de la
construction du graphe), alors, vue de l'extérieur, cette boucle sera
considérée comme structurée. Dans le cas d'une implémentation
parallèle, la rupture de séquence dans une itération est en effet
indépendante des autres itérations et n'empêche en rien l'exécution
parallèle du programme. 

\SSE{Un exemple simple}
Dans le programme:
\begin{verbatim}
       do 10 i=1,n
       t(i) = i
       if ( i .le. m ) goto 20
           t(i) = i
20     continue
10     continue
\end{verbatim}
le corps de la boucle sera considéré comme un graphe composé, entre
autres, d'un noeud d'affectation et d'un noeud de contrôle qui
correspond au saut conditionnel. Ceci est visible dans le pretty-print
du graphe de contrôle donné ci-dessous:
\begin{verbatim}
Graph 60a48
           --> Node 60a48
           statement 61508
           Preds: 
           Succs: 
           Code of 60a48:
           DO @10 I = 1,N,1
               Graph 60c40
                   --> Node 60c40
                   statement 5d718
                   Preds: 
                   Succs: 60ca8 
                   Code of 60c40:
                   =(T(I),I)
                   End of code of 60c40
                   --> Node 60ca8
                   statement 5ff98
                   Preds: 60c40 
                   Succs: 60d38 60d50 
                   Code of 60ca8:
                   IF (.LE.(I,M)) THEN
                       GOTO @20
                   ELSE
                       CONTINUE()
                   ENDIF
                   End of code of 60ca8
                   --> Node 60d38
                   statement 60e70
                   Preds: 60ca8 
                   Succs: 608e0 
                   Code of 60d38:
                   End of code of 60d38
                   --> Node 608e0
                   statement 61300
                   Preds: 61180 60d38 
                   Succs: 
                   Code of 608e0:
20                 CONTINUE()
10                 CONTINUE()
                   End of code of 608e0
                   --> Node 61180
                   statement 61160
                   Preds: 60da0 
                   Succs: 608e0 
                   Code of 61180:
                   =(T(I),I)
                   End of code of 61180
                   --> Node 60da0
                   statement 60d80
                   Preds: 60d50 60e40 
                   Succs: 61180 
                   Code of 60da0:
                   End of code of 60da0
                   --> Node 60d50
                   statement 61098
                   Preds: 60ca8 
                   Succs: 60da0 
                   Code of 60d50:
                   CONTINUE()
                   End of code of 60d50
                   --> Node 60e40
                   statement 60e20
                   Preds: 
                   Succs: 60da0 
                   Code of 60e40:
                   End of code of 60e40
               End of graph 60c40
           ENDDO
00000      CONTINUE()
           End of code of 60a48
End of graph 60a48
\end{verbatim}
Ce graphe de de contrôle est construit (parsing et pretty-printing
compris) en 0.98s.

\SSE{Construction du graphe}
La routine principale de construction du graphe de contrôle prend en
entrée un {\tt statement} et retourne le graphe de contrôle
correspondant. Comme précisé précédemment, si le statement en
question est complètement structuré, le graphe de contrôle sera
limité à un noeud; cela sera le cas, par exemple, de la routine de
multiplication matrices.

\PAR{}
L'algorithme utilisé est défini par induction sur la structure d'arbre
abstrait du programme. La routine récursive principale est {\tt
controlize} qui, pour un statement {\tt st} ayant {\tt pred} pour noeud
prédecesseur et {\tt succ} pour noeud successeur, retourne dans {\tt
c\_res} le noeud de contrôle correspondant et met à jour l'argument
{\tt used\_labels} qui contient la liste des occurences des étiquettes
utilisées dans une instruction (ceci est utilisé dans
l'implémentation du masquage de contrôle).

\PAR{}
Le but essentiel de {\tt controlize} est d'éliminer les {\tt goto} et
de les remplacer par des arcs dans le graphe de contrôle. Ceci est fait
via deux structures de données (implémentées par des tables de
hachage); {\tt label\_statements} associe à tout nom d'étiquette la
liste de instructions qui la référence, tandis que {\tt
label\_control} associe à tout nom d'étiquette le noeud de contrôle
correspondant (qui est utilisé dans le cas de branchement en avant).
Ces deux structures de données sont construites lors d'un premier
parcours de {\tt st} par la routine {\tt create\_statements\_of\_labels}.

\PAR{}
Le masquage de contrôle nécessite de compactifier les graphes de
contrôle des composantes d'une instruction en vue de les remplacer par
un seul noeud. La routine de test principale est {\tt covers\_labels\_p}
qui vérifie si les occurrences des étiquettes utilisées dans
l'instruction représentent toutes les apparences possibles de ces
étiquettes, auquel cas les branchements correspondants sont locaux et
pourront être négligés dans les instructions englobantes. Une étape
de compaction importante est {\tt compact\_list} correspondant aux
séquences; elle permet de regrouper dans des sous-séquences (i.e.,
{\em basic blocs}) les instructions qui ne comportent pas de
branchement.

\PAR{}
Une conséquence de la construction du graphe de contrôle est la
possibilité de détecter les instructions du pogramme qui correspondent
à du ``code mort''. Si cette information est inutile à la
parallélisation proprement-dite, elle peut indiquer une erreur de
conception du programme d'applications et est donc reportée à
l'utilisateur.

\section{Analyse sémantique}
\label{semantique}

\paragraph{}
Le travail concernant l'analyse sémantique est présenté en deux volets,
d'une part la programmation, d'autre part, une réflexion algorithmique.

\subsection{Avancement de l'implémentation}

\paragraph{}
Le travail d'implémentation a consisté à récupérer le maximum
de code du prototype d'analyseur sémantique pour écrire l'analyseur PIPS.
Les modules existants ont été découpés en morceaux plus petits pouvant
être installés dans une de nos bibliothèques d'algèbre linéaire,
compatibles avec l'environnement PIPS.

\paragraph{}
En sus du découpage, les différentes transformations effectuées ont été:
\begin{itemize}
  \item le renommage des fonctions de base pour respecter des normes
        d'uniformisation dépendant du nom de la structure de données
        produites et de la fonctionnalité;
  \item l'ajoût de commentaires et la mise en forme de commentaires
        pré-existants;
  \item la rationalisation des fichiers {\em include}, avec une automatisation
        partielle de l'extraction des commentaires permettant d'assurer
        une meilleure cohérence entre le code C et les fichiers {\em headers};
  \item la mise au point de fichiers {\em Makefile} assurant la cohérence
        entre bibliothèques dépendant les unes des autres;
  \item la modification de codes présentant des dépendances par rapport
        à des modules ne faisant pas partie de PIPS;
  \item la mise en place de répertoires de tests permettant de vérifier
        les procédures de base dans un contexte minimum (non terminé);
\end{itemize}
Il reste encore à en améliorer les performances à l'aide des outils
UNIX {\em prof} et {\em gprof} et à développer des versions
{\em instrumentées} permettant de mieux comprendre le comportement
des algorithmes.

\paragraph{}
Ces bibliothèques sont au nombre de 7, comme les structures de données
décrites dans le rapport d'avancement de mars 1989 (rapport No~2):
\begin{itemize}
  \item vecteur,
  \item contrainte linéaire (égalité et inégalité),
  \item systeme de contraintes linéaires,
  \item rayon et droite,
  \item sommet,
  \item système générateur,
  \item polyèdre (double représentation par système de contraintes et
        système générateur).
\end{itemize}

\paragraph{}
Les routines essentielles pour l'analyse sémantique par polyèdre sont:
\begin{itemize}
  \item {\em affectation}, qui calcule l'effet d'une affectation affine
         sur un polyèdre
        (i.e. sur son système de contraintes et sur son système génerateur);
  \item {\em projection}, qui calcule l'effet d'une affectation non linéaire;
  \item {\em intersection\_demi}, qui calcule le nouveau prédicat d'une
        branche de test de la forme {\tt I.GE.J} 
        ({\em demi} signifie demi-espace);
  \item {\em intersection\_hyperplan}, qui calcule le nouveau prédicat
        d'une branche de test varie de la forme {\tt I.EQ.J};
  \item {\em enveloppe}, qui calcule l'enveloppe convexe de deux prédicats
        sur les points de jonction du graphe de contrôle (fin d'un test,
        boucle);
  \item {\em élargissement}, qui permet de calculer un polyèdre point fixe
        pour les boucles (opérateur $\nabla$ de la thèse de Halbwachs);
  \item {\em sc\_to\_sg}, qui permet de passer d'un système de contraintes
        à un système générateur;
  \item {\em normalisation}, qui permet d'éliminer les contraintes 
        et les éléments du système générateur qui sont redondants;
\end{itemize}
Ces fonctions sont construites à partir de fonctions similaires sur les
systèmes de contraintes et sur les systèmes générateurs.

\paragraph{}
Contrairement aux routines utilisées pour le calcul de dépendance qui
opèrent sur des entiers, ces routines utilisent et produisent des
polyèdres rationnels.

\subsection{Modification de l'algorithme d'Halbwachs}

\paragraph{Notion de variable}

\paragraph{}
L'algorithme présenté dans la thèse de N. Halbwachs ne prend pas en
compte ni l'aliasing implicite entre paramètres formels ou entre
paramètres formels et variables globales, ni l'aliasing explicite (i.e.
intra-procédural) créé par la déclaration {\tt EQUIVALENCE}. Nous
proposons de suivre la norme Fortran~77 qui élimine l'aliasing
implicite pour considérer que le premier problème ne se pose pas. Pour
traiter l'aliasing explicite nous prendrons aléatoirement une des
variables scalaires en alias, si plusieurs scalaires sont concernés. En
cas d'alias entre tableaux et scalaires, les instructions d'affectation
au tableau seront considérées comme des {\em kill}'s de la variable.
Cette règle pourrait être améliorée ultérieurement par un test de
dépendance si le besoin s'en fait sentir.

\paragraph{Réduction de la complexité}

Le comportement exponentiel de l'algorithme de résolution décrit
dans la thèse de Halbwachs et implémenté dans le prototype d'analyseur
sémantique est inacceptable pour des programmes scientifiques.

\paragraph{}
Nous proposons donc de découper la résolution globale du système aux
polyèdres en des résolutions partielles, dont la combinaison risque
bien sûr de donner des résultats moins précis mais dont le temps
d'exécution devrait être à peu près linéaire par rapport à
la taille du programme.

\paragraph{}
L'idée consiste à calculer pour chaque composante du graphe de
contrôle structuré (cf. section~3) une relation, appelée {\em
relation de transfert} dans la suite, entre le prédicat d'entrée
(précondition) et le prédicat de sortie (post-condition). Les
relations de transfert seront propagées de base en haut en fonction des
opérateurs de structuration du graphe de contrôle: séquence (composition),
test (enveloppe convexe), boucle (élargissement) et control (pour les
parties non structurées du programme analysé). Chaque
boucle aura une profondeur d'imbrication de 1, car les boucles internes
auront été précédemment transformées en relation de transfert.
Le placement des opérations d'élargissement nécessaires à la
convergence est trivial, ainsi que celui des opérations de fermeture
convexe.

\paragraph{}
Les instructions élémentaires (call assign, call read, call min,...)
fourniront les relations de transfert de base. L'analyse sera limitée
à l'assignation (call assign) dans un premier temps.

\paragraph{}
Pour les parties non structurées (unstructured:control), nous proposons
dans un premier temps de n'effectuer qu'une projection des variables
{\em tuées} par les statements correspondants. Si ces zones s'avèrent
trop fréquentes et parallélisables malgré un contrôle non régulier,
il serait possible d'implémenter l'algorithme d'Halbwachs pour elles.
L'analyse des parties structurées éventuellement présentes sous cette
zone control sera reprise normalement.

\paragraph{}
Une fois la relation de transfert calculée de bas en haut\footnote{Cette
approche pourrait aussi s'appliquer d'une manière interprocédurale
en ajoutant une traduction de la relation de transfert globale d'une
procédure à chacun de ses sites d'appel.}, il ne reste plus qu'à propager
les invariants de haut en bas du graphe de contrôle du module analysé.

\paragraph{}
Cette approche nous permettra éventuellement d'ajouter un peu
d'information lors de la constitution du système de dépendance entre
deux références, en profitant de la présence de la relation de
transfert entre les deux statements contenant ces références.

\paragraph{}
L'inconvénient essentiel de cet algorithme est qu'il dépend de la nature
des relations de transfert choisies. Pour obtenir les mêmes résultats
qu'avec l'algorithme d'Halbwachs, il faudrait au moins avoir des relations
de transfert {\em conditionnelles} où les conditions d'application
partielles et les relations de transfert partielles seraient définies
par des polyèdres\footnote{Ceci est plus général que les formules
conditionelles utilisées en évaluation symbolique dans le projet
VELOURS et que la généralisation de la propagation de constantes
proposée par Jean Goubault.}. Pour accélérer l'exécution,
nous proposons de réduire cette union de relations de transfert
partielles en une unique relation de transfert inconditionnelle par
fermeture convexe. Voici un exemple de programme où cette méthode
va perdre de l'information:

\begin{verbatim}
I = 4
IF(I.EQ.4) THEN
        J = 5
ENDIF
\end{verbatim}

Soit $i_{old}$ et $j_{old}$ les valeurs de \verb+I+ et \verb+J+ avant
l'exécution d'une instruction, et $i_{new}$ et $j_{new}$ leurs valeurs
après. La relation de transfert du bloc \verb+IF+ est $i_{new} = i_{old}$
et toute information sur \verb+J+ est perdue en faisant l'enveloppe
convexe de $j_{new} = 5$ et de $j_{new} = j_{old}$ (ce sont deux droites
non parallèles; elles génèrent donc tout l'espace). La composition
de l'affectation \verb+I = 4+ avec ce test va donc fournir la relation
de transfert $i_{new} = 4$ et toute information sur \verb+J+ sera encore
perdue. La relation de transfert calculée normalement pour cette
séquence serait $i_{new} = 4, j_{new} = 5$.

\paragraph{Fragilité des prédicats polyèdriques}

L'utilisation de l'enveloppe convexe fournit des résultats non intuitifs
car il est difficile aux programmeurs d'être aussi stricts qu'un
programme et de faire abstraction d'informations implicites.

\paragraph{}
Supposons par exemple que nous ayons le corps de programme:
\begin{verbatim}
T(2) = ...
DO I = 1, N
  T(I) = ...
ENDDO
\end{verbatim}
Quel est la partie de \verb+T+ qui est touchée par cette séquence
d'instructions? On aimerait pouvoir dire \verb!T(1..N+1)! mais l'enveloppe
convexe des deux régions touchées par \verb+T(2)+ et \verb+T(I)+ est 
le tableau \verb+T+ tout entier. Aucune information sur \verb+N+ n'est
disponible; cette variable peut avoir une valeur négative et ne peut pas
être utilisée pour définir la partie de \verb+T+ modifiée. Il faudrait
disposer d'une prédicat $n \ge 1$ pour pouvoir faire la déduction
souhaitée, \verb!T(1..N+1)!. Cette information est implicite pour tout
programmeur humain.

\paragraph{}
Supposons maintenant que nous recherchions des variables inductives dans le
code:
\begin{verbatim}
K = 0
DO I = 1, N
  K = K + 2
ENDDO
\end{verbatim}
et que nous soyons intéressé par la valeur de \verb+K+ en sortie de
boucle. Ici encore, nous n'aurons aucune information si nous ne savons pas
que la variable \verb+N+ a une valeur positive en entrée de boucle.

\paragraph{Augmentation des sources d'information}

Pour pallier le problème précédent, il faudrait pouvoir utiliser
des sources d'information secondaires comme les déclarations
de tableaux\footnote{Mais attention aux déclarations du genre
\verb+REAL T(1)+ que font les programmeurs Fortran dans les
sous-programmes quand ils ne voulent pas passer
la dimension en argument.}, et admettre que les boucles \verb+DO+ sont
programmées pour être exécutées au moins une fois.

\subsection{Plan de travail}

La programmation de ce nouvel algorithme d'analyse sémantique, qui
devrait résoudre les points 1 et 4 de la section 2.1 du précédent
rapport d'avancement, devrait être effectuée en priorité. Il restera
ensuite à améliorer la technique d'élargissement en fonction des
résultats obtenus sur les programmes dont nous disposons (points~2~et~3)
et, très vraisemblablement, l'efficacité des procédures utilisées.

\section{Conclusion}

La réalisation du paralléliseur PIPS progresse comme prévu. Il nous
faut maintenant aborder les problèmes interprocéduraux et les
transformations de programme.

\newpage
\SEC{ANNEXE 1 --- DETECTION DU PARALLELISME}
\PAR{}
Cette annexe contient la description des structures de données privées
du paralléliseur.

\PAR{}
La structure de données suivante implémente un graphe orienté. Cette
structure est générique, mais elle peut être adaptée aux besoins de
chacun grâce aux deux domaines externes {\tt vertex\_label} et {\tt
arc\_label} qui sont attachés respectivement aux noeuds et aux arcs du
graphe.

Cette structure est utilisée pour le graphe des dépendances et pour le
graphe de contrôle d'un module.

\domain{External vertex\_label}
{}
\domain{External arc\_label}
{}

\domain{Graph = vertices:vertex*}
{Un graphe se compose tout simplement d'un ensemble de noeuds,
représentés par le domaine {\tt vertex}.}

\domain{Vertex = vertex\_label x succs:succ*}
{Chaque noeud d'un graphe est représenté par un {\tt vertex}. Le
sous-domaine {\tt succs} donne la liste des successeurs du noeud. Le
sous-domaine {\tt vertex\_label} doit etre utilisé pour les informations
attachées à chaque noeud et dont la nature dépend de l'application
utilisant le graphe; voir par exemple le domaine {\tt dg\_vertex\_label}
dans le fichier {\tt kennedy.f.tex}.}

\domain{Succ = arc\_label x vertex}
{Chaque arc d'un graphe est représenté par un {\tt succ}. Le
sous-domaine {\tt vertex} contient le noeud vers lequel l'arc pointe. Le
sous-domaine {\tt arc\_label} doit être utilisé pour contenir les
informations attachées à chaque arc{,} et dont la nature dépend de
l'application utilisant le graphe; voir par exemple le domaine {\tt
dg\_arc\_label} dans le fichier {\tt kennedy.f.tex}.}

\newpage{}
\PAR{}
Les structures de données suivantes sont utilisées par la phase {\tt
kennedy} de PIPS.

\domain{Import statement from "ri.newgen"}
{}
\domain{Import vertex from "graph.newgen"}
{}

\domain{dg\_vertex\_label = statement x enclosing\_loops:statement* x sccflags}
{Ce domaine est utilisé pour contenir les informations qui sont
attachées à chaque noeud du graphe de dépendances (voir le domaine
{\tt graph} dans le fichier {\tt graph.f.tex}). Le sous-domaine {\tt
statement} représente l'instruction qui porte la dépendance. Le
sous-domaine {\tt enclosing\_loops} represente les boucles qui englobent
cette instruction; c'est une liste de {\tt statement} et non pas une
liste de {\tt loop} pour avoir accès aux effets de ces boucles. Le
sous-domaine {\tt sccflags} contient diverses informations utiles pour
le calcul des composantes fortement connexes.}

\domain{dg\_arc\_label = all\_levels:unit + levels:int*}
{Ce domaine est utilisé pour contenir les informations qui sont
attachées à chaque arc du graphe de dépendances (voir le domaine {\tt
graph} dans le fichier {\tt graph.f.tex}). Il s'agit des niveaux des
dépendances représentées par cet arc. Les dépendances de niveau {\tt
all\_levels} sont créées par les scalaires affectés dans les boucles.}

\domain{Sccflags = enclosing\_scc:scc x mark:int x dfnumber:int x lowlink:int}
{Ce domaine est utilisé par l'algorithme de calcul des composantes
fortement connexes d'un graphe.}

\domain{Sccs = sccs:scc*}
{Ce domaine permet de contenir le résultat de l'algorithme de calcul
des composantes fortement connexes d'un graphe. Il s'agit d'une liste de
{\tt scc}, c'est à dire de composantes fortement connexes.}
\domain{Scc = vertices:vertex* x indegree:int}
{Ce domaine permet de représenter une composante fortement connexe d'un
graphe. Une {\tt scc} se compose d'un ensemble de noeuds, et d'un
sous-domaine {\tt indegree} utilisé par l'algorithme de tri topologique.
}

\newpage
\SEC{ANNEXE 2 --- RESULTATS DU PARALLELISEUR}
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           T(I) = 0.0
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
002           T(I) = 0.0
000       ENDDO
\end{verbatim}

en 0.8 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           T(I) = 0.0
003           V(I) = T(I) ** 2.
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
002           T(I) = 0.0
000       ENDDO
000       DOALL I = 1,10,1
003           V(I) = T(I) ** 2.
000       ENDDO
\end{verbatim}

en 1.2 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           DO J = 1,10,1
003               V1(I,J) = 0.0
004               V2(I,J) = V2(I,J) + V1(I + 1,J)
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
000           DOALL J = 1,10,1
004               V2(I,J) = V2(I,J) + V1(I + 1,J)
000           ENDDO
000       ENDDO
000       DOALL I = 1,10,1
000           DOALL J = 1,10,1
003               V1(I,J) = 0.0
000           ENDDO
000       ENDDO
\end{verbatim}

en 1.5 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           MAT(I,I) = 0.0
003           DO J = 1,I - 1,1
004               MAT(I,J) = 1.0
005               MAT(J,I) = --1.0
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
000           DOALL J = 1,I - 1,1
005               MAT(J,I) = --1.0
000           ENDDO
000       ENDDO
000       DOALL I = 1,10,1
000           DOALL J = 1,I - 1,1
004               MAT(I,J) = 1.0
000           ENDDO
000       ENDDO
000       DOALL I = 1,10,1
002           MAT(I,I) = 0.0
000       ENDDO
\end{verbatim}

en 2.0 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           DO J = 1,10,1
003               MAT(I,J) = 0.0
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
000           DOALL J = 1,10,1
003               MAT(I,J) = 0.0
000           ENDDO
000       ENDDO
\end{verbatim}

en 1.0 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO L = 1,N - 1,1
002           DO J = L + 1,N,1
003               A(L,J) = A(L,J) / A(L,L)
000           ENDDO
004           DO I = L + 1,N,1
005               DO K = L + 1,N,1
006                   B(I,K) = A(I,L) * A(L,K)
007                   A(I,K) = A(I,K) - B(I,K)
000               ENDDO
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DO L = 1,N - 1,1
000           DOALL J = L + 1,N,1
003               A(L,J) = A(L,J) / A(L,L)
000           ENDDO
000           DOALL I = L + 1,N,1
000               DOALL K = L + 1,N,1
006                   B(I,K) = A(I,L) * A(L,K)
000               ENDDO
000           ENDDO
000           DOALL I = L + 1,N,1
000               DOALL K = L + 1,N,1
007                   A(I,K) = A(I,K) - B(I,K)
000               ENDDO
000           ENDDO
000       ENDDO
\end{verbatim}

en 1.5 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,L,1
002           DO J = 1,N,1
003               C(I,J) = 0.0
004               DO K = 1,M,1
005                   C(I,J) = C(I,J) + A(I,K) * B(K,J)
000               ENDDO
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,L,1
000           DOALL J = 1,N,1
003               C(I,J) = 0.0
000           ENDDO
000       ENDDO
000       DOALL I = 1,L,1
000           DOALL J = 1,N,1
000               DO K = 1,M,1
005                   C(I,J) = C(I,J) + A(I,K) * B(K,J)
000               ENDDO
000           ENDDO
000       ENDDO
\end{verbatim}

en 1.1 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           V1(I) = 0.0
003           V2(I) = V2(I) + V1(I + 1)
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
003           V2(I) = V2(I) + V1(I + 1)
000       ENDDO
000       DOALL I = 1,10,1
002           V1(I) = 0.0
000       ENDDO
\end{verbatim}

en 1.2 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           DO J = 1,10,1
003               V1(I,J) = 0.0
004               V2(I,J) = V2(I,J) + V1(I + 1,J)
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
000           DOALL J = 1,10,1
004               V2(I,J) = V2(I,J) + V1(I + 1,J)
000           ENDDO
000       ENDDO
000       DOALL I = 1,10,1
000           DOALL J = 1,10,1
003               V1(I,J) = 0.0
000           ENDDO
000       ENDDO
\end{verbatim}

en 1.7 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           DO J = 1,10,1
003               V1(I,J) = 0.0
004               V2(I,J) = V1(I,J) + V1(I,J + 1)
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
000           DO J = 1,10,1
003               V1(I,J) = 0.0
004               V2(I,J) = V1(I,J) + V1(I,J + 1)
000           ENDDO
000       ENDDO
\end{verbatim}

en 1.5 secondes.

\newpage
\paragraph{}
La boucle suivante:
\begin{verbatim}
001       DO I = 1,10,1
002           DO J = 1,10,1
003               V1(I,J) = 0.0
004               V2(I,J) = V1(I,J) + V1(I,J)
000           ENDDO
000       ENDDO
\end{verbatim}

est transformée en:

\begin{verbatim}
000       DOALL I = 1,10,1
000           DOALL J = 1,10,1
003               V1(I,J) = 0.0
000           ENDDO
000       ENDDO
000       DOALL I = 1,10,1
000           DOALL J = 1,10,1
004               V2(I,J) = V1(I,J) + V1(I,J)
000           ENDDO
000       ENDDO
\end{verbatim}

en 1.5 secondes.


\newpage
\SEC{ANNEXE 3 --- GRAPHE DE CONTROLE}
\PAR{}
Cette annexe contient le listing des programmes sources du graphe de
contrôle. 

\end{document}
\end
