%%
%% $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,A4,french,verbatim]{farticle}

\usepackage[latin1]{inputenc}
\title{ Compilation pour machines à mémoire répartie \\
	 - Rapport de synthèse finale - \\
Contrat 92/0017 BC 08}
\setlength{\parindent}{0mm}
\newcommand{\PIPS}{\mbox{PIPS}}
\newcommand{\CRI}{\mbox{CRI}}
\newcommand{\ARMINES}{\mbox{ARMINES}}
\newcommand{\IN}{\mbox{IN}}
\newcommand{\PRISM}{\mbox{PRISM}}
\newcommand{\OUT}{\mbox{OUT}}
\newcommand{\PVM}{\mbox{PVM}}
\author{Corinne Ancourt}
\begin{document}

\maketitle 

\section{Objet de l'étude}

L'objectif général de cette étude est le développement de techniques
de compilation associées aux machines à mémoire répartie et leur
intégration dans une chaîne de compilation opérationnelle.

Basée sur une collaboration entre le \PRISM{} de l'Université de
Versailles-St Quentin et \ARMINES{}, la partie commune aux deux équipes
a pour but  la définition d'un format général de directives
permettant l'intégration des résultats déjà fournis par l'un ou
l'autre des  outils de parallélisation automatique de programmes
scientifiques FORTRAN développés par le \PRISM{} et \ARMINES{}.

La partie en charge d'\ARMINES{} représente l'extension et la
consolidation des travaux menés dans le cadre du projet ESPRIT PUMA.
Une maquette a été développée. Elle 
génère à partir d'un programme FORTRAN 77 séquentiel,  un programme FORTRAN 77 distribué comportant des appels à une
librairie de communications, permettant d'effectuer facilement des
tests sur un réseau de stations de travail.

Plusieurs membres du CRI ont contribué au bon déroulement de ce
projet: Corinne Ancourt (Chargée de recherche),  Fabien Coelho
(Scientifique du contingent en 94),  Béatrice Creusillet (Elève
chercheur), François Irigoin (Directeur de recherche), et Ronan Keryell
(Chargé de recherche). 

\section{Intérêt de l'étude}

Les multiprocesseurs à mémoire distribuée ont été introduits sur le
marché depuis de nombreuses années mais leur programmation reste
néanmoins toujours difficile. Les données d'une application doivent
être divisées et placées sur les mémoires locales du
multiprocesseur. Les allocations des éléments de tableaux ainsi
distribués et des éléments temporaires utilisés lors des calculs
doivent être effectuées. Des instructions {\em receive} doivent être
ajoutées à chaque processus pour récupérer les données résidant
dans d'autres processeurs et, de même, des instructions {\em send}
doivent être introduites dans ceux des processus qui peuvent accéder
localement ces mêmes éléments.

Des outils de distribution automatique des données d'une application
commencent à faire leur apparition mais restent, pour le moment, dans
le domaine de la recherche \cite{Dart93,Feau93,GuPr93}.  Ecrire et
mettre au point des processus 
distribués est beaucoup plus difficile que de déclarer une boucle
parallèle. Il faut tenir compte à la fois de l'ordonnancement des
calculs et de la distribution des données afin de minimiser les
communications et conserver un bon taux de parallélisme.

La majorité des études de compilation associées aux multiprocesseurs
à mémoire répartie utilise la règle d'exécution, {\em owner
computes rule}.  Le code de transposition d'une matrice est simple, et
permet de montrer les limites de ce modèle.

\begin{center}
\begin{figure}[htp]
\begin{verbatim}
DO I = 1, SIZE-1
   DO J = I+1, SIZE
      T = M(I,J)
      M(I,J) = M(J,I)
      M(J,I) = T
   ENDDO
ENDDO
\end{verbatim}
\label{code-transposition}
\caption{Transposition de matrice}
\end{figure}
\end{center}

\input{access-pattern.tex}

En effet, il est  difficile de distribuer les
itérations du corps de boucles de telle sorte qu'un processeur
possède tous les éléments qu'il doit mettre à jour:
\verb+M(I,J)+ et \verb+M(J,I)+ sont dans la majorité du temps sur des
processeurs différents.  La technique définie par Gerndt dans
\cite{Gerndt89} trouverait que l'ensemble de la matrice \verb+M+ doit
être stockée sur tous les processeurs (car elle correspond à la
{\em zone de recouvrement} existant entre deux itérations
différentes). Il est de même impossible de recourir aux techniques
de {\em distribution} de boucles car la variable \verb+T+ est locale
au corps de boucles. Il faudrait
pour utiliser cette technique expanser la variable, ce qui reviendrait
à allouer  une nouvelle matrice \verb+T+ aussi grande que la matrice
\verb+M+. 

 L'approche que nous avons choisie dans le cadre du projet PUMA (projet
ESPRIT 2701) est d'abandonner la {\em owner computes rule} et
de la remplacer par une mémoire partagée émulée par logiciel. Les
avantages potentiels sont:
\begin{enumerate}
\item la suppression du problème de la distribution des données;
\item la prise en compte efficace de plus de constructions que ne le
permet la {\em owner computes rule};
\item la possibilité de servir les requêtes mémoire sur des
processeurs dédiés n'effectuant aucun calcul;
\item l'obtention plus aisée d'un bon équilibre de charge puisque
n'importe quel processus peut être exécuté sur n'importe quel
processeur;
\item le contrôle plus fin de la granularité du parallélisme qui
n'est plus implicitement liée à la distribution des données; ceci
peut aussi améliorer l'équilibre de charge.
\end{enumerate}

La seconde idée est d'utiliser des serveurs mémoire spécifiques à
l'application, connaissant les requêtes mémoire devant être
effectuées au cours de l'exécution. Aucune requête mémoire explicite
n'est alors nécessaire, ce qui augmente la bande passante globale utile
du réseau d'interconnexion.

Compte tenu des restrictions du type d'applications que nous
traitions dans le cadre du projet PUMA (nids de boucles parallèles et
parfaitement imbriquées), cette étude a permis l'extension du
prototype vers des applications petites ou moyennes beaucoup plus
générales, dont les caractéristiques sont décrites dans la section
suivante. 

Les appels à communication sont traduits en appels à une librairie de
communications, \PVM{}, disponibles sur de nombreux multiprocesseurs.  Ce
choix  nous a permis d'effectuer des tests et de  commencer à valider 
nos options  sur un réseau de stations de travail.

\subsection{Objectifs précis de la recherche}

L'objectif de cette étude est de développer un prototype de compilation pour
machines à mémoire distribuée permettant de tester plusieurs
approches dans un contexte de {\em mémoire partagée émulée} sur diverses  machines à mémoire répartie possédant des
possibilités de connexion processeur à processeur: 
\begin{itemize}
\item diverses applications (diverses tailles de noyaux de calcul,
calculs creux), 
\item diverses distributions (dans un premier temps par colonne ou ligne)
\item divers  partitionnements (dans un premier temps selon la taille,
puis selon la forme)
\end{itemize}


 Le langage d'entrée utilisé est le FORTRAN 77 et le langage de sortie
est le FORTRAN 77 augmenté d'appels à une bibliothèque de
communication portable \PVM{}.  Les points principaux de développement et
d'extension du langage étaient les suivants:

\begin{itemize}
\item définition des pragmas;
\item développement de techniques de partitionnement pour des boucles non
parfaitement imbriquées;
\item compilation de structures de contrôle dynamiques, comme les
conditionnelles;
\item compilation de structures de données dynamiques, comme les
indirections;
\item développement de techniques d'analyse statique de complexité en
temps.
\end{itemize}

Ces différents points ont été traités. Ils sont présentés brièvement en
Section \ref{etapes} et/ou  détaillés en Section \ref {annexe}.
\subsection{Historique des études antérieures}

 Dès les années 70, la DRET a soutenu un certain nombre de projets de
recherche en parallélisation. Le projet VESTA, développé au sein du
Centre de Recherches de CII-Honeywell Bull avec la collaboration du
Pr.~Feautrier, prévoit la conception d'un compilateur vectoriseur pour
Fortran. Ecrit en PL1, ce prototype n'a pas connu de suites immédiates,
en partie du fait de l'absence de machines cibles françaises.
Le projet VATIL, développé à l'INRIA par l'équipe
du Pr.~Lichnewsky, a poursuivi dans cette voie de recherche par la
réalisation d'un vectoriseur écrit en Le-Lisp. Ce vectoriseur a été
progressivement enrichi et transformé en un paralléliseur.

Le \CRI{}/\ARMINES{} a développé, avec un financement DRET, de 1988 à
1991 le prototype \PIPS{} de parallélisation automatique de programmes
destiné aux machines à mémoire partagée (projet
DRET~87/017~bc~01). Les résultats les plus significatifs de cette
étude se résument par (1) la qualité de la précision des phases
d'analyse sémantique utilisées pour la détection automatique du
parallélisme implicite, (2) leur caractère inter-procédural ainsi que
(3) par la classe d'applications réelles traitées.

Cette étude s'est prolongée de 1992 à 1993 par le contrat \PIPS{}-2
(DRET~87/017~bc~18) qui avait pour objectif l'évaluation des travaux
précédemment effectués et l'ajout d'une phase de génération de code
vectoriel approprié au CRAY, incluant des primitives de
micro-tasking.

Parallèlement à ces deux projets (1991-1992), et sur un financement
ESPRIT, le \CRI{}/\ARMINES{} a débuté une étude de génération de code
distribué, dédié aux machines à mémoire répartie possédant des
possibilités de connexion processeur à processeur. Cette étude a
permis le développement d'un prototype de compilation/distribution pour
des applications restreintes à des nids de boucles parallèles et
parfaitement imbriquées.

\subsection{Résultats acquis antérieurement}

 \PIPS{} dispose d'un ensemble de phases
d'analyse (syntaxiques, sémantiques,...), de transformations de
programme (distribution, parallélisation,...) et d'outils de
manipulation de structures de bases (polyèdres, graphes,...) qui, grâce
à sa structure modulaire, peuvent
être utilisées et appliquées indépendamment. Les développements
effectués au cours de cette année ont grandement profité de cette
modularité.

D'une part, les résultats des phases d'analyse des dépendances, de
calcul des préconditions et de détection des {\em variables privées}
ont été directement utilisées. L'algorithme de distribution de nids
de boucles a été amélioré pour mieux cibler les caractéristiques de
notre approche. L'algorithme utilisé par l'{\em atomizer} pour
transformer un programme en une suite d'affectations de variables
scalaires ou/et de références directes à un tableau, a aussi été
amélioré.

D'autre part, les phases de partitionnement de programmes, de
génération du code {\em distribué/partitionné}, de génération des
communications et des déclarations associées aux allocations mémoire
ont été réalisées ou adaptées aux nouveaux besoins.  Ces phases
représentent un module indépendant de \PIPS{} nommée {\em distribution}.
 


\section{Déroulement de l'étude}
\label{etapes}

Le projet {\em Compilation pour machines à mémoire répartie} s'est
déroulé sur une période d'un an. Son objectif était principalement
l'extension du langage d'entrée restreint, dans le cadre du projet
ESPRIT PUMA, aux nids de boucles parallèles et parfaitement
imbriquées. Après un rappel des caractéristiques de l'approche
retenue, et des différentes étapes utiles à la génération d'un code
distribué que nous avons étudiées, les sections suivantes retracent les
états d'avancement  du projet.

\subsection{Rappel des différentes étapes}

Avant de présenter les différentes étapes de cette étude, nous
rappelons les caractéristiques de l'approche retenue dans le cadre
de PUMA. 

\subsubsection{Caractéristiques de notre approche}

Les processus sont divisés en deux catégories. Les processus de
calculs exécutent les instructions du programme ainsi que les
communications nécessaires à leur exécution. Seules les données
utiles aux calculs associés au processus seront allouées dans la 
mémoire locale du processeur associé. Les processus qui émulent
la mémoire partagée (bancs mémoire) n'effectuent que les
communications et le stockage.

\paragraph{\bf Distribution des données}
La distribution des données est implicite.  Les éléments de tableaux
sont cycliquement alloués dans les bancs de la mémoire partagée.
La figure 3 illustre cette distribution. Comme il s'agit de tableaux
ForTran, ils sont alloués cycliquement par blocs d'éléments
appartenant consécutivement à une même colonne.  La taille des blocs
est donnée par l'utilisateur dans le fichier de configuration
(model.rc) qui contient également le nombre de processeurs et de bancs
mémoire.

\input{matrix-mapping.tex}

\paragraph{\bf Distribution des calculs}
La distribution des calculs est basée sur le partitionnement des
itérations des nids de boucles \cite{IrTr88}. Pour le moment, ce
partitionnement s'effectue par blocs réguliers, parallèles aux
directions des boucles initiales \\(Figure \ref{control-distribution}). La taille des partitions peut être
aisément ajustée de manière à réduire les surcoûts de
communication et de contrôle dûs au démarrage des tâches
parallèles, et à équilibre les temps de communication et de calcul.
La granularité du parallélisme peut être aussi ajustée, car elle
n'est pas directement liée à la distribution des données mais
uniquement au graphe de contrôle du programme.

\begin{figure}
\setlength{\unitlength}{1.0pt}
\begin{picture}(180,90)(0,0)

% partitioning

\thicklines
\put(0,90){\line(1,0){90}}
\put(30,60){\line(1,0){90}}
\put(90,30){\line(1,0){60}}
\put(150,0){\line(1,0){30}}

\put(0,90){\line(1,-1){30}}
\put(30,90){\line(1,-1){60}}
\put(60,90){\line(1,-1){90}}
\put(90,90){\line(1,-1){90}}

% iteration domain

\thinlines
\put(10,85){\line(1,0){70}}
\put(10,85){\line(2,-1){140}}
\put(80,85){\line(1,-1){70}}

% iterations

\multiput(10,85)(10,0){8}{\circle{2}}
\multiput(30,75)(10,0){7}{\circle{2}}
\multiput(50,65)(10,0){6}{\circle{2}}
\multiput(70,55)(10,0){5}{\circle{2}}
\multiput(90,45)(10,0){4}{\circle{2}}
\multiput(110,35)(10,0){3}{\circle{2}}
\multiput(130,25)(10,0){2}{\circle{2}}
\multiput(150,15)(10,0){1}{\circle{2}}

\end{picture}

\caption{Distribution des calculs}
\label{control-distribution}
\end{figure}

Les dépendences entre
instructions sont analysées de manière à trouver les
contraintes d'ordonnancement entre les itérations des boucles.  Si cet
ordonnancement est un ordre total, les boucles devront s'exécuter
séquentiellement et il ne sera pas possible d'effectuer un
partitionnement intéressant des instructions permettant de réduire
le temps d'exécution.  Des techniques de partitionnement peuvent
toutefois être utilisées pour pallier aux contraintes de taille des
mémoires locales (réduction des données devant être stockées
au cours de l'exécution).

Chaque bloc est vu comme une tâche indépendante. Chaque tâche
est constituée de trois parties: la première correspond aux
transferts des données utiles à l'exécution de la tâche de la
mémoire globale vers la mémoire locale du processeur, la seconde
correspond aux calculs et la dernière aux transferts des données,
modifiées au cours de l'exécution, dans la mémoire partagée.

Les tâches parallèles sont distribuées sur les processeurs
 de calcul. Les calculs ne font plus référence aux éléments de tableaux
via les indices de  boucles initiaux, mais utilisent les indices locaux à 
chacun des blocs (partitions). Tous les calculs qui dépendent des
indices de boucles initiaux sont remplacés par une série
d'instructions relatives aux indices locaux.

D'une part, pour respecter le modèle SPMD et, d'autre part, pour limiter les
synchronisations et communications éventuelles internes à un nid de
boucles, l'ensemble des exécutions séquentielles est effectué par tous
les processeurs. Ce choix limite les diffusions de données qui seraient
calculées séquentiellement et utilisées au cours de calculs
parallèles distribués internes au nid de boucles séquentiel.

Un bon équilibre de charge est plus facile à obtenir que dans le cas
de la {\em owner computes rule} car n'importe quel processus
peut être exécuté sur n'importe quel processeur. La taille des
processus peut même être ajustée dynamiquement.

\paragraph{\bf Transferts de données}

Lorsque le partitionnement des instructions en processus
est déterminé, les transferts de données entre la mémoire 
partagée émulée et les mémoires locales des processeurs de calcul 
peuvent être calculés.

Les transferts, de la mémoire partagée vers les mémoires locales des
processeurs de calcul, des données utilisées au cours de l'exécution
doivent être exécutés avant le début de chaque processus.  Ceux de
la mémoire locale des processeurs de calcul vers la mémoire partagée
doivent l'être à la fin de chaque exécution.  Ils nécessitent la
caractérisation de l'ensemble des données {\em utilisées} et {\it
modifiées} pendant les phases de calculs.

La caractérisation de ces données est problématique quand il
s'agit de tableaux, car c'est l'ensemble des éléments
référencés par le tableau dans le corps de boucle de la tâche
parallèle qui doit être calculé. Cet ensemble correspond à un
ensemble de points entiers.  C'est la cause de la plupart des
problèmes rencontrés.  Cet ensemble ne correspond pas toujours à un
ensemble convexe de points entiers ce qui rend difficile son parcours
par un corps de boucles {\em simples}. Les techniques utilisées pour
générer automatiquement ces codes de transfert sont détaillées
dans~\cite{Ancourt90}.

\paragraph{\bf Chargement des données.}
Pour transférer les données {\em utilisées} de la mémoire partagée vers 
les mémoires locales, il n'est pas nécessaire de copier l'ensemble exact des 
données utilisées par la tâche. Un ensemble de données légèrement 
plus grand peut être copié car ces données ne seront utilisées que 
localement. Aucun conflit entre les différentes mémoires locales ne peut se 
produire. 

Si l'ensemble des éléments à transférer est non convexe, son
enveloppe convexe sera transférée.  Dans le cas de plusieurs
références au même tableau en dépendance dans le corps de boucles, un
seul code de transfert des données sera généré pour l'ensemble de
ces références.

\paragraph{\bf Rangement des résultats.}
Pour transférer les données de la mémoire locale des processeurs de
calcul vers la mémoire partagée, il ne serait pas correct de copier un
élément qui n'a pas été modifié par la tâche. En effet, cet
élément peut avoir été modifié par une tâche s'exécutant en
parallèle, et deux valeurs d'une même donnée ne peuvent coexister
dans une mémoire partagée cohérente. Il faut donc recopier l'ensemble
exact des données {\em modifiées} par la tâche.

\input{bank-access-pattern.tex}

Si cet ensemble n'est pas un ensemble convexe, des divisions entières sont
introduites dans les expressions des bornes de boucles de manière à
traduire cette non convexité. Un test linéaire est aussi parfois
nécessaire. Pour éviter ce test, qui conduit à une augmentation du
coût du contrôle, les codes de transfert pourraient être décomposés:
un code de transfert par ensemble convexe constituant l'ensemble non
convexe des données modifiées serait alors généré.


La figure \ref{data-movements} illustre l'ensemble des éléments
référencés par l'un des blocs de calculs lors d'une transposition de
matrice. L'ensemble des éléments du bloc inférieur gauche et
supérieur droit doivent être transférés pour mettre à jour les
éléments de tableaux symétriques correspondants. La distribution de
ces éléments référencés sur les bancs de la mémoire partagée
illustre bien la non convexité des ensembles d'éléments à
transférer. Cette non convexité explique  la complexité du
code généré. 


\paragraph{\bf Déclaration des variables locales et partagées}
En ce qui concerne les problèmes d'allocation mémoire et de
déclarations des données partagées et locales associées, on
remarque que : 
\begin{itemize}
\item Il est important de pouvoir détecter les variables locales à un
corps de boucles, telle que $T$ dans l'exemple de la transposition de
matrice, parce qu'elles peuvent être allouées directement dans les
mémoires locales des processeurs de calcul. Elles n'ont pas besoin
d'être transférées entre la mémoire partagée et les mémoires
locales durant les exécutions.  Les variables scalaires {\it
privées} sont détectées par \PIPS{}\cite{IrJoTr91}. Elles sont
déclarées dans les mémoires locales mais pas dans la mémoire
partagée émulée.

\item Il est aussi indispensable de prendre en compte les {\em input
dependences} qui existent entre des lectures de la même variable pour
savoir combien de copies locales il faut associer à chaque variable initiale.

Dans le cas de la transposition de matrice, les deux références
\verb+M(I,J)+ et \verb+M(J,I)+ sont totalement indépendantes. Il faut donc
prévoir la déclaration de {\em deux} zones de copies locales pour
\verb+M+, qui sont appelées \verb+L_M_0+ et \verb+L_M_1+(\verb+L+ comme
local). 
Par contre, dans le cas d'un calcul de convolution, on trouverait que
toutes les références à un voisinage sont en dépendance et donc
qu'il ne faut allouer qu'une seule copie locale.
\end{itemize}

\subsubsection{Premier trimestre}

Les développements réalisés au cours du premier trimestre avaient
pour but essentiel d'installer une procédure de validation complète
des codes distribués générés par notre prototype. Ces développements
se sont concrétisés par  

\begin{itemize}

\item l'installation d'une procédure de validation du code généré 
 qui comporte des  programmes contenant, actuellement, en fin de projet:
\begin{itemize}
\item plusieurs nids de boucles parfaitement et non parfaitement
imbriqués, séquentiels, partiellement ou totalement parallèles
englobant une séquence d'affectations,
\item d'éventuelles indirections,
\item mais pas de conditionnelles,
\item  des références à des éléments de tableaux qui  sont  disjointes ou  se recouvrent.
\end{itemize}

\item l'ajout d'une interface avec \PVM{} et de sa validation sur réseau de stations de
travail,   présentées dans
le rapport intermédiaire.

\end{itemize} 

\paragraph{\bf Les indirections}

Simultanément, nous avons commencé l'extension du langage d'entrée
considéré. 
La présence des indirections dans les programmes soulèvent les mêmes
problèmes que ceux exposés pour les affectations conditionnelles: on
ne connaît pas à la compilation les éléments référencés au cours
des calculs. 

 L'{\em atomizer} est une transformation de programme qui simplifie les
phases d'analyse et de génération des communications dans les cas où
il y a des indirections (et des entrées/sorties), puisque les variables
temporaires créées par l'atomizer représentent les différentes
opérations ou communications qui devront être effectuées pour
finaliser l'envoi ou la réception d'un accès indirect aux éléments
d'un tableau.

\begin{center}
\begin{figure}[hpt]
\begin{verbatim}
                                      ITMP1 = I             
                                      ITMP2 = J
                                      ITMP3 = A(ITMP1, ITMP2)
                                      ITMP4 = ITMP1 -1
                                      ITMP5= ITMP2 +1
       B(I-1,J+1)=A(I,J)              B(ITMP4,ITMP5) = ITMP3
       C(A(I,J),J) = I                C(ITMP3,ITMP2) = ITMP1
\end{verbatim}
\caption{Atomizer}
\label{prog3}
\end{figure}
\end{center}

Cette transformation de programme a été intégrée à \PIPS{}. Si
l'optimiseur d'un compilateur sait optimiser le code généré,
notre prototype n'effectue pas d'optimisations. Afin de minimiser les
allocations de temporaires, une passe simplifiée de cette
transformation, permettant de préciser que l'on ne désire appliquer la
transformation qu'aux références aux éléments de tableaux
indirectes, a aussi été intégrée à \PIPS.


\subsubsection{Deuxième trimestre}
Cette deuxième partie du projet  a été consacrée, d'une part, à la
définition des pragmas et, d'autre part, à la définition du schéma
de calcul et de 
communications adapté aux nouvelles structures de données et de
contrôle introduites.


\paragraph{\bf Définition des pragmas.} En collaboration avec le
\PRISM{}, nous avons
déterminé les informations intéressantes qui seront échangées entre
PAF et PIPS. Plus précisément, il s'agit des {\em préconditions} et
des {\it régions}, calculées par PIPS et disponibles sous forme de
commentaire dans les programmes, qui seront utilisées par PAF et des
{\it réductions}, détectées par PAF, qui seront utilisées par
PIPS. Le format d'échanges des réductions choisi est celui décrit
dans le premier rapport d'avancement rédigé par M. Barreteau,
P. Feautrier et X. Redon.


\paragraph{\bf Schéma de calcul et communications adapté aux nouvelles structures.}
Dans le cadre du projet PUMA, seule la génération de code distribué
pour les nids de  boucles parfaitement imbriquées et parallèles était
proposée et optimisée. L'extension du type d'applications traitées
nécessitait la définition d'un nouveau schéma de calcul et de
communications. Une ébauche de cette étude a été présentée dans
le rapport intermédiaire. Nous en donnons une version  plus
détaillée dans l'annexe~\ref{annexe}.
 
\paragraph{\bf Complexité statique}

Le calcul de la complexité des tâches parallèles  à exécuter sur
les différents processeurs est utile, en autres, pour évaluer  le bon 
équilibrage ``coûts des communications'' et ``coûts des calculs''.

Cette phase de calcul, qui est intégrée à \PIPS{}, a été
présentée brièvement dans le rapport intermédiaire et détaillée
dans~\cite{Zhou94}. Pour des raisons de temps (réduction de la durée
du projet de 3 à 1 an), les résultats de cette phase d'analyse ne sont
pas encore exploités par l'algorithme de partitionnement. Cette
optimisation fait, cependant, partie des perspectives intéressantes de
recherche et d'expérimentation.



\subsubsection{Troisième trimestre}

Cette période a été consacrée à l'implantation du schéma de calcul
et communications, présenté en section~\ref{annexe} , à l'implantation 
et  l'amélioration des régions \IN{} et \OUT{}. 

\paragraph{\bf Régions \IN{} et \OUT{}}

Les techniques de compilation, utilisées actuellement par le prototype,
traitent successivement les nids de boucles. Elles génèrent pour
chacun d'entre eux, une tâche parallèle composée des communications
de la mémoire partagée vers les mémoires locales, du code de calcul,
puis des communications des mémoires locales vers la mémoire
partagée. Etant donné que les parties de programme séquentielles sont
exécutées par l'ensemble des processeurs, lorsque plusieurs nids de
boucles successifs totalement séquentiels référencent le même
ensemble de données, ces techniques générent des communications
inutiles qui ne tiennent pas compte de l'héritage de données
cohérentes provenant de tâches séquentielles précédentes. Pour
palier ce surcoût de communications, il ne faut effectuer (si les
capacités mémoire le permettent) les communications qu'au début et à
la fin de la partie séquentielle du programme. L'ensemble des données
à transférer est, dans ce cas, donné par les régions \IN{} et \OUT{}
\cite{Creu95} de la section de programme considérée. 



\subsubsection{Dernier trimestre}


La dernière partie du projet a permis de réaliser une phase de
transformation adaptée aux nids de boucles mal imbriqués et
d'améliorer les déclarations associées aux allocations mémoire,
aussi bien pour les processeurs de calcul que pour les processeurs
mémoire. 


\paragraph{\bf Déclaration des tableaux locaux}

Les processeurs de calcul exécutent les parties de calcul correspondant
aux itérations séquentielles et aux itérations parallèles
qui leur sont attribuées. L'espace nécessaire au stockage des éléments
de tableaux référencés au cours de ces itérations doit être alloué
en {\em local}.

Plusieurs références à un même tableau caractérisant des sections
de tableau disjointes sont allouées de manière indépendante.  Comme
l'illustre le code de la transposition de matrice en Annexe, les
sections symétriques du tableau \verb+M+ : \verb+L_M_0+ et \verb+L_M_1+
(Local variable \verb+M+)
référencées au sein du même nid de boucles parallèles sont
allouées indépendamment .  Si les références caractérisent des
sections non disjointes, un même espace leur est alloué. Sa dimension
correspond à l'enveloppe convexe des différentes sections.  L'espace
alloué aux tableaux locaux dépend directement de la taille des blocs
définie par le partitionnement.


\paragraph{\bf Déclaration des variables globales}

Les processeurs mémoire émulent une mémoire globale sur laquelle est
alloué l'ensemble des tableaux de l'application. Les tableaux sont
stockés cycliquement sur les bancs (processeurs mémoires) par blocs,
de taille égale à celle des lignes de bancs définies dans le fichier
de configuration.  La position d'un élément de tableau \verb+M+ est
définie par le numéro de banc auquel il appartient, le numéro de la
ligne sur le banc et sa position dans la ligne.  La taille des tableaux
en mémoire globale est identique à celle des tableaux initiaux.  Une
matrice  \verb+M(100x100)+ distribuée sur 4 bancs mémoire par lignes de 100
éléments sera déclarée sur chacun des bancs sous la forme
\verb+ES_M(0:24,0:99)+ (Emulated Shared variable  \verb+M+).

\paragraph{\bf  Traitement des nids de boucles mal imbriquées}

Afin d'augmenter le taux de parallélisme exploitable et les
possibilités d'appliquer efficacement le partitionnement, le code est
tout d'abord transformé~; une distribution partielle est
appliquée. Après distribution en composantes fortement connexes des
différentes instructions d'un nid de boucles, les instructions
indépendantes (non liées par des dépendances) sont regroupées au
sein d'un même nid de boucles qui sera au moins partiellement (pour
l'indice de boucle considéré) parallélisé. Plutôt qu'une
distribution totale, cette transformation permet, dans le cadre de notre
étude, de diminuer l'overhead de contrôle et d'améliorer
l'équilibrage de charge.  Les instructions liées par des dépendances
cycliques, qui ne peuvent pas être {\em cassées} par simple
distribution des instructions, sont aussi regroupées au sein d'un même
nid de boucles, dans le même but.  Les instructions qui appartiennent
à une même composante connexe sont effectivement distribuées de
façon à permettre la parallélisation.

L'application de cette transformation génère des nids de boucles
parfaitement bien imbriquées parallèles ou séquentiels et des nids de
boucles mal imbriqués dont la boucle externe  est
séquentielle. 

\subsection{Difficultés, faits significatifs et résultats}

La réalisation de cette étude n'a pas soulevé de problème technique
particulier. La difficulté que nous avons rencontré est temporelle et
s'explique par la réduction de trois à un an de la période allouée
initialement au projet . Les différentes étapes du projet ont été
abordées et la majorité d'entre elles a été implantée dans le
prototype de parallélisation \PIPS{}.


Avec ces nouvelles phases d'analyse, de transformation et
génération de code distribué, \PIPS{} dispose d'une plateforme de
recherche et d'expérimentation, très modulaire, qui devrait permettre
d'effectuer des comparaisons intéressantes avec les approches basées
sur la  {\em owner computes rule} et plus particulièrement l'approche
\verb+HPF+ . 

Cette étude a permis l'introduction de nouvelles phases indépendantes
dans \PIPS{} qui pourront être utilisées dans un autre contexte. 
Notamment, la transformation de distribution partielle sera utile à
tout type d'architecture ou stratégie de compilation nécessitant un
grain moyen de parallélisme.


\section{Récapitulation des résultats}

Le développement de ce prototype a montré que PIPS possédait les
phases d'analyses et de transformations nécessaires au développement
rapide d'algorithmes de génération de code distribué. Les étapes
 intégrées à \PIPS{} sont les suivantes:
\begin{itemize}
\item définition des pragmas permettant aux deux équipes \PRISM{} et
\CRI{} de profiter rapidement des résultats des techniques avancées
développées par l'un et  l'autre des prototypes,
\item compilation des structures de contrôle séquentielles,
\item compilation des structures de données dynamiques, comme les
indirections
\item développement de techniques de partitionnement pour des boucles non
parfaitement imbriquées
\item génération de code faisant appel à une bibliothèque de
communications \PVM{},
\item développement d'une phase de validation permettant de conserver
au cours  des améliorations des algorithmes de génération de code, les résultats antérieurs acquis sans
possibilités de régression. 
\end{itemize}

Les phases qu'il reste à intégrer en vue d'optimiser le code généré
sont:

\begin{itemize}
\item compilation de structures de contrôle dynamiques, comme les
conditionnelles 
\item intégration des techniques d'analyse statique de complexité en
temps 
\item intégration des régions \IN{} et \OUT{}
\end{itemize}


\section{Conclusion}

Après quelques mois de retard, dû en grande partie au fait que l'on
désirait, malgré la réduction de temps imparti au projet, développer
et intégrer la majeure partie des phases de l'étude dans la chaine de
compilation opérationelle \PIPS{}, en vue d'obtenir une maquette du
prototype de génération de code distribué avancée, ce projet s'est
bien déroulé et a fournit un ensemble de  résultats techniques
cohérents en un an.


\section{Perspectives ultérieures}

Comme nous l'avons déjà signalé au cours de la présentation des
différentes étapes de réalisation de cette étude, par manque de
temps, certaines optimisations ne sont pas intégrées dans les étapes
de génération de code distribué. La phase de calcul de la complexité
statique d'une application devrait permettre d'améliorer le {\em load
balancing} des applications parallèles (partitionnement selon une
dimension plutôt qu'une autre). La phase d'analyse des {\em régions
\IN{} et \OUT{}} devrait aussi, une fois intégrée aux algorithmes de
génération des comunications, conduire à une diminution significative
du coût des communications.

Une autre perspective importante est l'utilisation des différentes
phases de {\em distribution} pour valider et tester les choix retenus
dans notre approche. Les premiers résultats expérimentaux, menés sur
un réseau de stations de travail, sont ceux que l'on attendait. Notre
approche offre des possibilités d'exécution d'applications gourmandes
en mémoire et (2) obtiennent de meilleurs temps d'exécution sur les
tâches parallèles comportant de nombreux calculs.

\section{Annexe Technique - Schéma de communication adapté aux nouvelles
structures}
\label{annexe} 

La première étape de distribution/parallélisation d'un programme,
composé uniquement d'un ensemble de boucles parallèles et parfaitement
imbriquées, consiste à regrouper les calculs en tâches parallèles de
taille raisonnable (relativement à la taille des caches ou aux lignes de
bancs mémoire, par exemple). Une fois les calculs regroupés en tâches
parallèles, l'étape suivante est la génération des communications
nécessaires à l'exécution des tâches sur les différents
processeurs. Pour ce type de code, la stratégie choisie consistait à
transférer l'ensemble des éléments référencés en lecture
(respectivement en écriture) avant (respectivement après) l'exécution
de chacune des tâches parallèles. Cependant, l'extension de notre
langage d'entrée impose un schéma de communication plus complet.

\paragraph{\bf Recouvrement des calculs et communications}

Les expériences réalisées ont été effectuées sur un réseau de
stations de travail. Le gain que l'on peut attendre de ce type
d'expérience se situe sur la granularité des applications qui peuvent
être exécutées comparées à une exécution sur un seul
processeur. Dans ce contexte, un pipeline de séquences d'instructions
effectuant les communications et d'autres les calculs n'a pas
d'intérêt.  En fait, il induirait même un surcroît d'allocations
mémoire, nécessaire au stockage des tableaux locaux pour les
différents niveaux de pipeline. Nous n'avons donc pas implanté de
techniques permettant de recouvrir calculs et communications, et
l'ensemble des communications nécessaires aux calculs d'une tâche sont
effectuées immédiatement avant l'exécution des calculs.


     
\subsection{Stratégies de communication} 

Différentes stratégies de communication peuvent être utilisées pour
transférer les éléments utiles à l'exécution des tâches sur les
processeurs selon les différentes structures du programme.  Celle que
nous avons choisie est la suivante:

\subsubsection{Affectation simple}
 \begin{itemize}
\item les éléments   référencés en lecture
sont transférés avant l'exécution de cette instruction, pas
nécessairement juste avant, mais le plus souvent regroupés avec ceux de
structures plus englobantes, de manière à favoriser des possibilités
d'effectuer des  communications groupées.
\item Les  éléments  scalaires référencés en écriture sont
transférés juste après l'exécution, tandis que les éléments de
tableaux modifiés sont regroupés avec ceux d'une structure plus
englobante pour favoriser les possibilités de transferts d'éléments
contigus, moins coûteux. 
\end{itemize}

\subsubsection{Séquence d'affectations}

\begin{itemize}
\item l'ensemble des éléments référencés en lecture est transféré
avant l'exécution de cette séquence, si aucun des termes des indices
des fonctions d'accès aux éléments d'un tableau ne dépend d'une
variable scalaire qui est modifiée dans cette séquence linéaire (voir
Figure \ref{prog1}).  Sinon, une communication en réception est
générée juste avant l'instruction référençant le tableau.

\begin{center}

\begin{figure}[hpt]
\begin{verbatim}
                                 A = ...
                                 C = T(A)
\end{verbatim}
\caption{Séquence d'affectations - référence indirecte}
\label{prog1}
\end{figure}
\end{center}


\item  Les  éléments  scalaires référencés en écriture sont
transférés juste après l'exécution, tandis que les éléments de
tableaux modifiés sont regroupés au niveau de la séquence
d'instructions.
\end{itemize}

\subsubsection{Séquence d'affectations- références indirectes}
Les scalaires étant distribués sur tous les bancs mémoire, tous les 
processeurs émulant la mémoire partagée disposent de la valeur de ces
scalaires.  Les éléments de tableaux référencés par des fonctions
d'accès numériques ou paramétriques, sous la condition que ce
paramètre soit connue au début de l'exécution de la boucle, sont
traités identiquement aux autres éléments de tableaux dont la
fonction d'accès est linéaire. Ils représentent un cas particulier
pour lequel la valeur des indices est nulle.
Par contre, les éléments de tableaux dont la fonction d'accès est 
paramétrique et pour lesquelles la valeur du paramètre n'est connue que
lors de l'exécution, doivent être traités différemment. On distingue
aussi, pour des raisons d'optimisation, le cas où le nid de boucle est
totalement séquentiel des autres cas:


\paragraph{\bf Le nid de boucles est totalement séquentiel}

Chaque processeur de calcul déduit des équations de linéarisation,
dérivant de l'allocation cyclique sur les bancs mémoire des éléments
de tableaux, la position mémoire (numéro de banc, numéro de la ligne
sur le banc et l'offset sur la ligne) de l'élément a
transférer. Cette position est ensuite communiquée au banc mémoire
correspondant au numéro du processeur de calcul. Après réception, le
banc mémoire qui possède la mémoire (simple test sur les valeurs
recues) envoie à chacun des processeurs la valeur de l'élément.

\paragraph{\bf Le nid de boucles est partiellement ou totalement parallèle}

Chaque processeur effectue des calculs qui peuvent être différents de
ceux exécutés sur les autres processeurs de calcul. La valeur du
paramètre peut donc être différente pour chacun des
processeurs. Chaque processeur doit diffuser la position de l'élément
dont il a besoin à l'ensemble des bancs mémoire. Le banc mémoire
correspondant renvoie en retour l'élément au processeur exécutant le
bloc correspondant.

\begin{verbatim} 
C   PROGRAMME d'ENTREE
C   programme comportant 
C      - des iterateurs i et j dans les calculs 
C      - des acces aux elements de tableaux parametres
C
C
      do 100 i = 1, size
         do 200 j = 1, size
            b(i,j) = (i-1)*size+(j-1)
            p = 1
            m = b(p,j)
            c(i,j) = b(i,j)/(size*size)
 200     continue
 100  continue
\end{verbatim}

\begin{verbatim} 
C   PROGRAME GENERE PAR LE PROTOTYPE
C   code distribue utilisant les iterateurs locaux L_I et L_J
C
         DO 99978 L_I = 0, 0
          DO 99979 L_J = 0, 1
          X3 = 1+I_0+L_I
          X4 = 1+2*J_0+L_J
          L_B_0_0(L_I,L_J) = (X3-1)*SIZE+X4-1
          P = 1
          L = (-1+20*J_0+10*L_J+P)/20
          X1 = (-1+20*J_0+10*L_J+P-20*L)/10
          O = -1+20*J_0+10*L_J+P-20*L-10*X1
          DOALL X2 = 0, 1
             CALL WP65_SEND_4(X2, X1, 1)
             CALL WP65_SEND_4(X2, L, 1)
             CALL WP65_SEND_4(X2, O, 1)
          ENDDO
          CALL WP65_RECEIVE_4(X1, L_B_0_0(P,L_J), 1)
          M = L_B_0_0(P,L_J)  
          L_C_0_0(L_I,L_J) = L_B_0_0(L_I,L_J)/(SIZE*SIZE)
99979 CONTINUE
99978 CONTINUE
\end{verbatim}

 Il faut noter que les variables qui sont {\em privées}\footnote{Une
variable est privée à un nid de boucles, si sa valeur en entrée de
boucle et sa valeur en sortie ne sont pas utilisées dans le nid de
boucles en dehors de cette boucle; c'est le cas des variables
temporaires.}  à une séquence d'instructions n'impose une
communication qu'après exécution de la séquence d'instructions et pas
avant.


\subsubsection{Les nids de boucles totalement parallèles}
 Les éléments de tableaux ou scalaires référencés en lecture
(respectivement en écriture) sont transférés globalement
avant (respectivement après) l'exécution. Il n'y a pas de conflits
mémoire entre les accès aux données référencées puisque les
exécutions sont parallèles.


\subsubsection{Les nids de boucles  séquentielles} 

Les calculs séquentiels sont exécutés sur un seul processeur. Tous
les éléments référencés en lecture (respectivement en écriture)
peuvent être transférées globalement avant (respectivement après)
l'exécution du nid de boucles, car les dépendances sont respectées
par la séquentialité de l'exécution.


\paragraph{\bf Taille des blocs d'itérations séquentielles}
D'une part pour respecter le modèle SPMD et d'autre part pour limiter
les synchronisations et communications éventuelles internes à un nid
de boucles, l'ensemble des exécutions séquentielles sont effectuées
par tous les processeurs. Deux solutions permettent de distribuer les
itérations séquentielles sur l'ensemble des processeurs de calcul:
soit 1) on considère des blocs de taille égale à la section de
tableau correspondant aux itérations de l'espace initial, soit 2) on
considère des blocs de taille unitaire. Dans le premier cas, le volume
des données à communiquer et à allouer est important et correspond à
l'ensemble des éléments du tableau auxquels la fonction d'accès fait
référence. Dans le second cas, seuls les éléments de tableaux
référencés par une valeur de l'indice sont communiqués et alloués.

Actuellement, le prototype  dimensionne les "blocs
séquentiels" selon 2) pour les boucles
séquentielles externes (éventuelles) aux boucles parallèles et selon
1) pour les boucles séquentielles internes
(éventuelles) aux boucles parallèles.  Dans le cas de nid de
boucles totalement séquentielles, un compromis mixte devra être
introduit pour conserver des possibilités de communications
vectorielles ou regroupées et limiter les transferts toujours coûteux
de données uniques.
    


\subsubsection{Les conditionnelles (pas encore intégrées)}
Par défaut, les deux branches de la
conditionnelle sont traitées de manière indépendante selon les
structures précédemment décrites auxquelles elles appartiennent. 
Toutefois, il est possible d'effectuer quelques optimisations pour les
deux cas suivants:
\begin{itemize}
\item La conditionnelle est une inéquation linéaire dépendante d'un
indice de boucle. Dans ce cas il est possible d'introduire cette
contrainte dans le domaine d'itérations et de générer un ou deux
nouveaux nids de boucles et leurs communications sans
conditionnelle. Les nids de boucles traduiront respectivement la branche
vraie et la branche fausse de la contrainte.

\item La conditionnelle est une fonction linéaire indépendante des
termes contenus  dans les deux branches du test. Cette contrainte est
alors extraite du nid de boucles et placée à l'extérieur. Les
communications sont générées pour chacune des branches
indépendamment. Toutefois, le  test est effectué en dehors du nid de
boucles et pas une fois pour chacune des valeurs du domaine
d'itérations. 
\end{itemize}

\subsection{Code généré pour la transposition d'une matrice M}
{\scriptsize
\begin{verbatim}
      SUBROUTINE WP65(PROC_ID)
      INTEGER*4 idiv
      EXTERNAL idiv
      INTEGER PROC_ID,BANK_ID,L,O,I_0,L_I,J_0,L_J,L_I_1,L_I_2,L_J_1,
     &L_J_2
      REAL*4 L_M_0_0(0:24,0:24),L_M_1_0(0:24,0:24),T

C     WP65 DISTRIBUTED CODE FOR TRANSP

C     To scan the tile set for WP65
      DO 99973 I_0 = PROC_ID, 3, 4
         DO 99974 J_0 = I_0, 3
            DOALL BANK_ID = 0, 3
               DO 99995 L_J = MAX(0, 1+25*I_0-25*J_0), 24
                  DO 99996 L = MAX(idiv(I_0+100*J_0, 16), idiv(4+101*
     &            I_0, 16)), idiv(96+I_0+100*J_0, 16)
                     L_I_1 = MAX(0, 100*BANK_ID-25*I_0-2500*J_0+400*L
     &               -100*L_J)
                     L_I_2 = MIN(24, 23-25*I_0+25*J_0, idiv(-1+100*
     &               BANK_ID-2525*I_0+400*L, 101), 99+100*BANK_ID-25*
     &               I_0-2500*J_0+400*L-100*L_J)
                     IF (L_I_1.LE.L_I_2) THEN
                        CALL WP65_RECEIVE_4(BANK_ID, L_M_0_0(L_I_1,
     &                  L_J), L_I_2-L_I_1+1)
                     ENDIF
99996                CONTINUE
99995             CONTINUE
99994          CONTINUE
            ENDDO
            DOALL BANK_ID = 0, 3
               DO 99990 L_I = 0, MIN(24, 23-25*I_0+25*J_0)
                  DO 99991 L = MAX(idiv(100*I_0+J_0, 16), idiv(301-
     &            100*BANK_ID+2525*I_0+101*L_I, 400)), MIN(idiv(96+
     &            100*I_0+J_0, 16), idiv(92+101*J_0, 16), idiv(-1*
     &            BANK_ID+25*I_0+L_I, 4))
                     L_J_1 = MAX(0, 1+25*I_0-25*J_0, 1+25*I_0-25*J_0+
     &               L_I, -9800+100*BANK_ID-25*J_0+400*L, 100*BANK_ID
     &               -2500*I_0-25*J_0+400*L-100*L_I)
                     L_J_2 = MIN(24, 99+100*BANK_ID-2500*I_0-25*J_0+
     &               400*L-100*L_I, 99+100*BANK_ID-25*J_0+400*L)
                     IF (L_J_1.LE.L_J_2) THEN
                        CALL WP65_RECEIVE_4(BANK_ID, L_M_1_0(L_J_1,
     &                  L_I), L_J_2-L_J_1+1)
                     ENDIF
99991                CONTINUE
99990             CONTINUE
99989          CONTINUE
            ENDDO
C           To scan each iteration of the current tile
            DO 99975 L_I = 0, 24
               DO 99976 L_J = MAX(1+25*I_0-25*J_0+L_I, 0), 24
                  T = L_M_0_0(L_I,L_J)
                  L_M_0_0(L_I,L_J) = L_M_1_0(L_J,L_I)
                  L_M_1_0(L_J,L_I) = T
200               CONTINUE
99976             CONTINUE
99975          CONTINUE
            DOALL BANK_ID = 0, 3
               DO 99984 L_J = MAX(0, 1+25*I_0-25*J_0), 24
                  DO 99985 L = MAX(idiv(I_0+100*J_0, 16), idiv(4+101*
     &            I_0, 16), idiv(3-BANK_ID+25*J_0+L_J, 4)), MIN(idiv(
     &            96+I_0+100*J_0, 16), idiv(99-BANK_ID, 4), idiv(-1-
     &            100*BANK_ID+2525*J_0+101*L_J, 400))
                     L_I_1 = MAX(0, 100*BANK_ID-25*I_0-2500*J_0+400*L
     &               -100*L_J)
                     L_I_2 = MIN(24, 23-25*I_0+25*J_0, idiv(-1+100*
     &               BANK_ID-2525*I_0+400*L, 101))
                     IF (L_I_1.LE.L_I_2) THEN
                        CALL WP65_SEND_4(BANK_ID, L_M_0_0(L_I_1,L_J)
     &                  , L_I_2-L_I_1+1)
                     ENDIF
99985                CONTINUE
99984             CONTINUE
99983          CONTINUE
            ENDDO
            DOALL BANK_ID = 0, 3
               DO 99978 L_I = 0, MIN(24, 23-25*I_0+25*J_0)
                  DO 99979 L = MAX(idiv(100*I_0+J_0, 16), idiv(301-
     &            100*BANK_ID+2525*I_0+101*L_I, 400)), MIN(idiv(96+
     &            100*I_0+J_0, 16), idiv(92+101*J_0, 16), idiv(-1*
     &            BANK_ID+25*I_0+L_I, 4))
                     L_J_1 = MAX(0, 1+25*I_0-25*J_0, 1+25*I_0-25*J_0+
     &               L_I)
                     L_J_2 = MIN(24, 99+100*BANK_ID-25*J_0+400*L, 99+
     &               100*BANK_ID-2500*I_0-25*J_0+400*L-100*L_I)
                     IF (L_J_1.LE.L_J_2) THEN
                        CALL WP65_SEND_4(BANK_ID, L_M_1_0(L_J_1,L_I)
     &                  , L_J_2-L_J_1+1)
                     ENDIF
99979                CONTINUE
99978             CONTINUE
99977          CONTINUE
            ENDDO
99974       CONTINUE
99973    CONTINUE
      RETURN
      END
\end{verbatim}
}
\newpage
{\scriptsize
\begin{verbatim}
      SUBROUTINE BANK(BANK_ID)
      INTEGER*4 idiv
      EXTERNAL idiv
      INTEGER PROC_ID,BANK_ID,L,O,I_0,L_I,J_0,L_J,O_1,O_2
      REAL*4 ES_M(0:99,0:25)

C     BANK DISTRIBUTED CODE FOR TRANSP

C     To scan the tile set for BANK
      DO 99971 I_0 = 0, 3
         PROC_ID = MOD(I_0, 4)
         DO 99972 J_0 = I_0, 3
            DO 99997 L_J = MAX(0, BANK_ID-25*J_0, 1+25*I_0-25*J_0), 
     &      24
               DO 99998 L = MAX(idiv(3-BANK_ID+25*J_0, 4), idiv(4-
     &         BANK_ID+25*I_0, 4)), idiv(24-BANK_ID+25*J_0, 4)
                  O_1 = MAX(0, -100*BANK_ID+2500*J_0-400*L+100*L_J, 
     &            -100*BANK_ID+25*I_0+2500*J_0-400*L+100*L_J)
                  O_2 = MIN(99, 9998-100*BANK_ID-400*L, 9924-100*
     &            BANK_ID+25*I_0-400*L, -1-100*BANK_ID+2525*J_0-400*L
     &            +101*L_J, 24-100*BANK_ID+25*I_0+2500*J_0-400*L+100*
     &            L_J)
                  IF (O_1.LE.O_2) THEN
                     CALL BANK_SEND_4(PROC_ID, ES_M(O_1,L), O_2-O_1+1
     &               )
                  ENDIF
99998             CONTINUE
99997          CONTINUE
            DO 99992 L_I = MAX(0, idiv(3+4*BANK_ID-100*I_0-J_0, 4)), 
     &      MIN(24, 23-25*I_0+25*J_0)
               DO 99993 L = MAX(0, idiv(12-4*BANK_ID+100*I_0+J_0, 16)
     &         ), MIN(idiv(96-4*BANK_ID+100*I_0+J_0, 16), idiv(92-4*
     &         BANK_ID+101*J_0, 16))
                  O_1 = MAX(0, 1-100*BANK_ID-400*L, 1-100*BANK_ID+
     &            2525*I_0-400*L+101*L_I, -100*BANK_ID+25*J_0-400*L, 
     &            -100*BANK_ID+2500*I_0+25*J_0-400*L+100*L_I)
                  O_2 = MIN(99, 2399-100*BANK_ID+2500*J_0, 24-100*
     &            BANK_ID+2500*I_0+25*J_0-400*L+100*L_I)
                  IF (O_1.LE.O_2) THEN
                     CALL BANK_SEND_4(PROC_ID, ES_M(O_1,L), O_2-O_1+1
     &               )
                  ENDIF
99993             CONTINUE
99992          CONTINUE
            DO 99986 L_J = MAX(0, BANK_ID-25*J_0, 1+25*I_0-25*J_0), 
     &      24
               DO 99987 L = MAX(idiv(3-BANK_ID+25*J_0, 4), idiv(4-
     &         BANK_ID+25*I_0, 4)), idiv(24-BANK_ID+25*J_0, 4)
                  DO 99988 O = MAX(0, -100*BANK_ID+25*I_0+2500*J_0-
     &            400*L+100*L_J), MIN(99, 24-100*BANK_ID+25*I_0+2500*
     &            J_0-400*L+100*L_J, 98-100*BANK_ID+2500*J_0-400*L+
     &            100*L_J, -1-100*BANK_ID+2525*J_0-400*L+101*L_J)
                     IF (idiv(202+100*BANK_ID+400*L+O, 101).LE.idiv(
     &               100+100*BANK_ID-25*I_0+400*L+O, 100).AND.idiv(
     &               101+100*BANK_ID+400*L+O, 100).LE.idiv(100+100*
     &               BANK_ID-25*I_0+400*L+O, 100).AND.idiv(175+100*
     &               BANK_ID-25*I_0+400*L+O, 100).LE.idiv(100+100*
     &               BANK_ID-25*I_0+400*L+O, 100)) THEN
                        CALL BANK_RECEIVE_4(PROC_ID, ES_M(O,L), 1)
                     ENDIF
99988                CONTINUE
99987             CONTINUE
99986          CONTINUE
            DO 99980 L_I = MAX(0, idiv(3+4*BANK_ID-100*I_0-J_0, 4)), 
     &      MIN(24, 23-25*I_0+25*J_0)
               DO 99981 L = MAX(0, idiv(12-4*BANK_ID+100*I_0+J_0, 16)
     &         ), MIN(idiv(96-4*BANK_ID+100*I_0+J_0, 16), idiv(92-4*
     &         BANK_ID+101*J_0, 16))
                  DO 99982 O = MAX(0, -100*BANK_ID+2500*I_0+25*J_0-
     &            400*L+100*L_I, 1-100*BANK_ID+2525*I_0-400*L+101*L_I
     &            ), MIN(99, 2399-100*BANK_ID+2500*J_0, 24-100*
     &            BANK_ID+2500*I_0+25*J_0-400*L+100*L_I)
                     IF (idiv(175+100*BANK_ID-25*J_0+400*L+O, 100)
     &               .LE.idiv(100+100*BANK_ID+400*L+O, 101).AND.idiv(
     &               175+100*BANK_ID-25*J_0+400*L+O, 100).LE.idiv(100
     &               +100*BANK_ID-25*J_0+400*L+O, 100)) THEN
                        CALL BANK_RECEIVE_4(PROC_ID, ES_M(O,L), 1)
                     ENDIF
99982                CONTINUE
99981             CONTINUE
99980          CONTINUE
99972       CONTINUE
99971    CONTINUE
      RETURN
      END
\end{verbatim}
}

\begin{thebibliography}{99}

\bibitem{Ancourt90} C. Ancourt,
{\em Génération automatique de codes de transfert pour multiprocesseurs
à mémoires locales},
Thèse de doctorat, Université Paris~6, 1990


\bibitem{Creu95} 
Béatrice Creusillet,
{\em Analyse de Flot de donnees: REGIONS de tableaux IN et OUT},
Conférence RenPar'7, Mons, Belgique, 30 mai-2 Juin 1995.

\bibitem{Dart93}  
Darte Alain and Robert Yves,
{\em Mapping Uniform Loop Nests onto Distributed
		Memory Architectures},Report jan. 93, LIP, ENS-Lyon.
	

\bibitem{Feau93}
Feautrier Paul,
{\em Toward Automatic Partitioning of Arrays on Distributed Memory
		Computers}, ICS'93, pages 175--184,
	

\bibitem{Gerndt89} 
H.M. Gerndt,
{\em Automatic parallelization for distributed-memory multiprocessing systems},
PhD, Bonn University, 1989

\bibitem{GuPr93}
Gupta Manish and Banerjee Prithviraj,
{\em Paradigme: A Compiler for Automatic Data Distribution on
		  Multicomputers}, 
	ICS'93, jul,pages 87--96

\bibitem{IrTr88} F. Irigoin, R. Triolet,
{\em Supernode Partitioning},
ACM Symposium on Principles of Programming Languages, San-Diego, 1988

\bibitem{IrJoTr91} F. Irigoin, P. Jouvelot, R. Triolet,
{\em Semantical Interprocedural Parallelization: An Overview of the PIPS Project},
ACM International Conference on Supercomputing (ICS'91), Cologne, 1991

\bibitem{Zhou94}
Lei Zhou,
``Static Evaluation of Fortran Program Complexity ``,
{\it Thèse de l'Université Pierre et Marie Curie },
1994.



\end{thebibliography}
\end{document}
