%%
%% $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]{article}

\usepackage[latin1]{inputenc}
\input{/usr/share/local/lib/tex/macroslocales/Dimensions.tex}
\newcommand{\titre}{RAPPORT D'AVANCEMENT No 1 \\
COMPILATION POUR MACHINES A MEMOIRE REPARTIE
}
\newcommand{\auteur}{
~Corinne ANCOURT \\
Fabien COELHO \\
François IRIGOIN \\
Ronan KERYELL 
 }
\newcommand{\docdate}{Juin 1994}
\newcommand{\numerocri}{E184}
\begin{document}
\sloppy
\input{/usr/share/local/lib/tex/macroslocales/PageTitre.tex}



\section*{Introduction}

L'objectif général de cette étude est de développer les techniques
nécessaires à la compilation de machines à mémoire répartie. 
Cette étude s'effectue en partie en collaboration avec l'équipe de Paul
Feautrier du Masi. Ce rapport décrit l'état d'avancement des
différentes tâches qui sont à la charge du CRI, c'est à dire:
\begin{enumerate} 
\item Interface du langage de sortie FORTRAN 77 augmenté
d'appels à une bibliothèque de communication 
\item Développement de techniques d'analyse statique de complexité en
temps;
\item  Définition des pragmas;
\item  Extension du langage d'entrée;
\item Compilation de structures de données dynamiques, comme les
indirections;
\item Compilation de structures de contrôle dynamiques, comme les 
conditionnelles, 
\item Développement de techniques de partitionnement pour des
boucles non-parfaitement imbriquées ;
\end{enumerate}

Les deux premières tâches sont achevées, les trois suivantes sont en
cours de développement et les deux dernières n'ont pas encore
débuté. Nous détaillons maintenant les résultats obtenus pour
chacune des cinq premières. La description des travaux déjà effectués
dans le cadre du projet PUMA n'a pas lieu d'être dans ce rapport. Pour
plus de détails sur ces travaux, il est conseillé de  se rapporter à
l'article \cite{AnIr92}.


\section{Définition des pragmas}

L'ensemble des techniques déjà développées en matière de
parallélisation automatique par les équipes du Masi et d'Armines
représente un support important pour l'obtention rapide d'un prototype
de compilation pour machines à mémoire distribuée. Il est important
que les deux prototypes PAF et PIPS puissent profiter des meilleurs
résultats obtenus par l'ensemble des techniques. Nous avons déterminé
les informations intéressantes qui seront échangées entre PAF et
PIPS. Plus précisément, il s'agit des {\it 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. La prochaine étape consiste à déterminer le format
d'échanges des préconditions et des régions.


\section{Extension du langage d'entrée}
Dans le cadre du projet PUMA, le langage d'entrée était très
restreint. L'étude portait uniquement sur la génération de code
distribué pour les nids de boucles {\em parallèles} et parfaitement
imbriquées englobant une séquence d'affectations. L'extension de ce
langage d'entrée aux structures de données dynamiques, telles que les
indirections, ou aux structures de contrôle dynamiques, telles que les
conditionnelles n'avait pas été abordée. De même, aucune stratégie
de distribution des parties séquentielles du code n'avait été
développée. Cette étude est maintenant en cours. Les premières
étapes ont été la définition d'un schéma de communication adapté
aux nouvelles structures ainsi que le développement et l'intégration
d'une transformation de programme nommée {\it atomizer} nécessaire,
plus particulièrement, au traitement des indirections.


\subsection{Schéma de communication adapté aux nouvelles
structures} 

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 (relative à 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, dans le cadre du projet PUMA, à
 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.

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 choisi est la suivante:

\begin{description}
\item [Affectation simple:]
~\newline
 \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 concurremment communications et calculs.
\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}

\item [Une séquence d'affectations:]

 ~\newline
\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 1).  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 1}
\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}

 Il faut noter que les variables qui sont {\it 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.  L'exemple \ref{prog2} présente le type de communications
générées pour une séquence d'affectations.

\begin{center}
\begin{figure}[hpt]
\begin{verbatim}
                                        CALL RECEIVE_4(A)
                                        CALL RECEIVE_4(B)
          F=A                           F = A
                                        CALL SEND_4(F)
          D=B                           D = B 
                                        CALL SEND_4(D)
                                        CALL RECEIVE_4(M(F,F))
          E=M(F,F)                      E = M(F,F)            
                                        CALL SEND_4(E)
\end{verbatim}
\caption{Communications - Séquence d'affectations}
\label{prog2}
\end{figure}
\end{center}

\item [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.


\item [Les nids de boucles totalement 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.

\item [Les nids de boucles totalement séquentielles - Pipelinées:] Si
le volume des données est trop important pour la mémoire locale des
processeurs, une division du domaine de
calculs en blocs d'itérations plus petits s'impose. Ces blocs seront
exécutés sur différents processeurs. Les communications et les
calculs sont alors pipelinés, dans tous les cas où cela est possible,
de manière à minimiser le temps global d'exécution. Les références
qui ne causent pas de dépendances correspondent aux données qui
pourront être communiquées de manière concurrente avec des calculs.

\item [Les nids de boucles mixtes:] On impose un seul niveau de
concurrence: on ne générera pas à la fois du code parallèle et
pipeliné au sein d'un même nid de boucles.

Toutes les références internes au nid de boucles parallèles ou
pipelinées sont communiquées avant (respectivement après) pour les
références en lecture (respectivement en écriture).  Les références
externes seront communiquées selon le schéma de communication des
boucles séquentielles non pipelinées. Comme les séquences
séquentielles ne sont exécutées que sur un seul processeur, ces
parties de code sont traitées comme des parties indépendantes des
boucles parallèles et des communications conservant la cohérence de la
mémoire globale doivent être générées à la fin et au début des
parties qui sont parallèles.

\item [les conditionnelles:] 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}

\end{description}


\section{Structures de données dynamiques: les indirections}

 L'{\it atomizer} est une transformation de programme qui {\it atomise}
toutes les références d'un programme, c'est à dire caractérise
l'accès de chacune des variables du programme par une suite
d'opérations trois adresses, similaires à celles qui sont utilisées
dans le langage intermédiaire d'un compilateur.
 

\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 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.

L'exemple \ref{prog3} présente les différentes variables temporaires
obtenues lorsqu'on applique cette transformation. Toutes les
opérations faisant intervenir des variables  non temporaires
représentent l'ensemble des communications à effectuer.

Cette transformation de programme  a été intégrée à Pips et sera
utilisée pour la génération des communications dans les cas où il y a
des indirections.



\section{ Interface du langage de sortie FORTRAN 77 avec  une bibliothèque de communication }

Afin de pouvoir tester notre approche sur différents types
d'architecture, nous avons choisi PVM comme  bibliothèque de communication. 

PVM est à l'heure actuelle la bibliothèque de communication la plus
utilisée pour les réseaux de stations de travail. Elle est surtout
utilisée dans le domaine de la recherche mais est aussi adoptée par
les industriels. Citons quelques industriels qui l'ont implantée sur
leur multiprocesseur respectif: CRAY sur le T3D, IBM pour leurs réseaux
de RS6000 et Fujitsu sur l'AP1000.

Une fois le code distribué (Fortran 77 + Primitives de communications),
une interface permet de traduire 
les appels aux communications en primitives PVM. Une validation du code
ainsi généré avec l'interface PVM peut ensuite être effectuée sur
un réseau de stations de travail.

La dernière partie de l'annexe présente cette interface. Les primitives de 
communication présentes dans le code généré par PUMA sont traduites
par des appels à des primitives de la bibliothèque de communications
PVM. Les fonctions utiles au lancement des différentes
tâches en parallèle sur les processeurs sont aussi données et
commentées. 


\section{Développement de techniques d'analyse statique de complexité en
temps}

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''.


L'estimation statique de la complexité des programmes séquentiels a
déjà fait l'objet de nombreuses recherches. L'originalité des travaux
du CRI est due à l'utilisation de préconditions et au traitement des
appels de procédures. Ils sont maintenant intégrés à Pips. Du point
de vue théorique, cette étude 

\begin{itemize}
\item  a étendu l'ensemble des cas traités aux cas où le programme
contient des tests, 

\item introduit des paramètres symboliques utiles à l'expression des
paramètres que l'on ne peut (ou veut) pas évaluer dans le programme, 

\item et  tient compte des
préconditions interprocédurales fournies par les phases d'analyses de
Pips.
\end{itemize}

Des expériences ont été menées sur des machines séquentielles et
parallèles pour valider l'approche choisie.

L'exemple \ref{prog5} détaille le calcul de la complexité d'une
sous-routine de calcul par Cholesky. Le coût de chacune des opérations
élémentaires est supposée ici unitaire, mais d'autres tables
appropriées à différents processeurs peuvent être choisies. Le
résultat global est ici dépendant de la variable $N$ puisque cette
constante n'est pas fixée par le programme.

\begin{figure}[hpt]
\verbatiminput{complexity.tex}
\caption{Complexité statique}
\label{prog5}
\end{figure}


\section{Validation}

Une  procédure de validation du code généré a été installée. Elle
teste (1) la correction du code généré en la comparant avec  une version
de référence, ainsi que (2) la cohérence 
des nouvelles versions qui doivent préserver les résultats des
versions antérieures. Les programmes de test sur lesquels sont
appliqués cette procédure ont un  langage d'entrée relatif  aux différentes
versions de notre prototype. Actuellement,  nous générons un code
distribué pour les programmes contenant:
\begin{itemize}
\item  un ou plusieurs nids de boucles parfaitement imbriqués englobant une
séquence d'affectations,
\item  des séquences d'affectations (partie à exécution séquentielle) et de nids de
boucles parfaitement imbriqués (englobant  une séquence d'affectations),
\end{itemize}

Les déclarations des tableaux locaux sont vérifiées par une
validation portant sur des programmes dont les sous-ensembles
d'éléments référencés sont  disjoints ou  se recouvrent. Le
deuxième exemple de l'annexe illustre le cas où ils sont disjoints.

\section*{Conclusion}

N'ayant pas rencontrés  de difficultés majeures lors de l'étude
des différentes tâches décrites précédemment, la réalisation de
notre contrat  progresse comme prévu. Il nous
faut maintenant terminer ou aborder les différents points suivants:
\begin{itemize}
\item  Extension du langage d'entrée (implémentation du schéma de communications);
\item Compilation de structures de données dynamiques, comme les
indirections (utilisation de l'atomizer);
\item Compilation de structures de contrôle dynamiques, comme les 
conditionnelles, 
\item Développement de techniques de partitionnement pour des
boucles non-parfaitement imbriquées ;
\end{itemize}

L'annexe donne deux exemples de code distribué générés par notre
prototype: l'addition de matrices et la transposition. Pour chacun de
ces exemples, la sous-routine exécutée par les processeurs de calcul
précède celle exécutée par les processeurs émulant la mémoire
partagée.

\newpage
\section*{Annexe}
\subsection*{Premier exemple: L'addition de matrices }
\verbatiminput{add.tex}
\newpage
\subsection*{Deuxième exemple: La transposition de matrice}

\verbatiminput{transp.tex}

\newpage
\subsection*{Interface avec la bibliothèque de communications PVM}
\verbatiminput{pvm-interface.tex}
\begin{thebibliography}{99}
\bibitem[AnIr92]{AnIr92}
C. Ancourt, F. Irigoin,
`` Automatic Code Distribution '',
{\it The Third Workshop on Compilers for Parallel Computers (CPC'92) },
Vienna, Austria, July 6-9, 1992
\end{thebibliography}

\end{document}
