PEI et les langages data-parallèles

Le formalisme PEI présente de nombreuses similitudes avec le modèle de programmation à parllélisme de données :
• les objets maniuplés sont des ensembles de valeurs (champs de données),
• et leur manipulation se fait par l'application d'opérations de trois types:
• modification des valeurs (opération fonctionnelle),
• réarrangement des valeurs (routage),
• placement d'un objet par rapport à un autre (changement de base).
 
Il devient alors naturel de vérifier et préciser ces similitudes, notamment en étudiant le passage d'un énoncé PEI à un langage de programmation data-parallèle. Dans cette optique a été créé un premier prototype de traducteur pour générer du code HPF à partir de programmes PEI.

Schéma d'ensemble du mécanisme de traduction

Malgré les similitudes observées entre le formalisme PEI et le modèle de programmation à parallélisme de données, il n'est en général pas possible de traduire directement un énoncé PEI en un programme data-parallèle. En effet, l'aspect équationnel des énoncés et l'abscence d'ordonnancement opérationnel pour évaluer la solution d'une équation, caractéristiques de PEI, s'y opposent.

Il est donc nécessaire d'opérer certaines transformations sémantiques des énoncés PEI pour obtenir un programme raffiné ayant une forme traduisible. Une fois l'énoncé transformé de manière à respecter les principes exposés ci-dessous, il est possible d'entamer un processus de transformation de nature syntaxique.

Equations

Seules les équations assimilables à des affectations sont traduisibles. Ces équations doivent ainsi ne faire apparaître qu'un seul identificateur de champ sur au moins un des membres de l'équation.

Ainsi, l'équation f :: X = g :: Y n'est-elle pas directement traduisible. Il faut auparavant rendre explicite X ou Y. Dans ce cas particulier, les règles de raffinement autorise à écrire, si f est inversible, X = (f^-1 o g) :: Y.

Il n'est cependant pas toujours possible de trouver une stratégie permettant de rendre traduisible une équation. Il n'existe par exemple aucun moyen de raffiner de façon satisfaisante les équations du type X  f = Y  g lorsque f et g sont des fonctions non inversibles. Il faut alors admettre que l'énoncé contenant une telle équation ne pourra pas être traduit.

Cadencement des équations récurrentes

Il s'agit là d'un problème classique de la parallélisation automatique : seules sont traduisibles les équations récurrentes pour lesquelles il est possible de déterminer un cadencemnt des calculs dans le temps. La solution consiste à trouver des fonctions de cadencement et de placement. En PEI, cette transformation se fait par un changement de base appliqué à l'énoncé.
 

...voir exemple
 

Le traducteur pei2hpf

L'objectif premier de ce traducteur est de produire des codes data-parallèles exploitables par un compilateur commercial et d'observer les conséquences des transformations PEI sur un code data-parallèle. On obtient ainsi un moyen indirect de faire de la transformation de programmes data-parallèles.

Cependant, un énoncé PEI n'est en général pas directement traduisible et on a même mis en évidence des énoncés qui ne pourront pas être traduits, tout cela pour des raisons sémantiques. D'autres complications font que même un énoncé PEI transformé de manière à être sémantiquement traduisible, en procédant comme décrit au chapitre précédent, n'est en général pas directement traduisible et il faut encore lui appliquer quelques transformations.

Fome traduisible

Le traducteur accepte en entrée le sous-ensemble des programmes PEI constitués des équations ayant la forme suivante :
 

• opération de routage : Y = X  g
• opération fonctionnelle : Y = f  (X₁ /&/ ... /&/ X_n)
• opération de changement de base : Y = h :: X
• propriété de champ de données : Y = h :: Y
• réduction géométrique : Y = fr  (gr ; X), où fr est de la forme fr = id # (a;b).(a @ fr(b)), où @ est un opérateur associatif, commutatif avec élément neutre. Seul + et * sont acceptés pour l'instant.
• définition récursive : Y = fc  (X /&/ (Y  g1) /&/ ... /&/ (Y  gn)), où fc est de la forme fc = id # (a;b;...;z).(a ¤₁ b ¤₂ ... ¤_n z), où les ¤_i sont des opérateurs quelconques sur des scalaires.

Cet ensemble d'expressions restreint a été choisi pour le prototype d'une part parce qu'il est possible d'associer à chacune d'elle un ensemble d'instructions HPF, sans avoir besoin d'informations contextuelles supplémentaires, et, d'autre part, la traduction d'expression de champs de données plus complexes n'est de toute façon pas toujours possible.

Synopsis du fonctionnement du traducteur

Lorsqu'un énoncé PEI a atteind une forme traduisible, sa structure est semblable à celle d'un programme parallèle. Il ne reste alors plus qu'à traduire les équations une à une et à inférer les dimensions des variables parallèles utilisées.

Le mécanisme de la traduction peut être résumé de la manière suivante :
 

1. Analyse lexicale et syntaxique du programme PEI et construction d'un arbre de syntaxe abstraite.
2. Parcours de l'arbre de syntaxe abstraite pour stocker les informations présentes dans l'équation dans un format de données intermédiaire. On vérifie à ce moment que les relations retirées des équations pourront être exploitées pour la production de code.
3. Passe supplémentaire sur l'ensemble des équations pour inférer des informations globales concernant les domaines des champs de données. On complète alors les informations du format intermédiaire.
4. Passage des informations à un formateur de texte qui exploite les informations du format intermédiaire pour produire le code HPF.

Traduction HPF des équations PEI
 

Opération de routage

L'équation PEI :

Y = X  g
se traduit directement par l'instruction HPF :
forall (z décrivant dom(g)) Y(z) = X(g(z)).
 
Opération fonctionnelle

L'équation PEI :

Y = f  (X₁ /&/ ... /&/ X_n)
se traduit directement par l'instruction HPF :
forall (z décrivant dom(_X), z décrivant dom(f)) Y(z) = f(X₁(z),...,X_n(z)).
 
Opération de changement de base

L'équation X = h :: X exprime que l'application de la fonction identité sur le domaine des valeurs de référence de X ne modifie pas X, h ne pouvant être ici que la fonction identité. On peut déduire de cette équation les dimensions de la variable X utilisée dans le programme HPF. Cette forme d'équation n'est donc pas directement traduite en HPF mais est utilisée pour dimensionner le tableau utilisée en HPF pour la traduction du champ X.

Pour les équations de la forme Y = h :: X, qui indiquent que toute valeur placée au point z dans le champ Y est aussi la valeur placée au point h(z) dans le champ X. Pour traduire cela, on peut soit determiner quel tableau est calculé le premier lors de l'exécution du programme puis recopier les valeurs, soit considérer que l'équation indique comment sont placés les deux tableaux sont placés l'un par rapport à l'autre sur la machine virtuelle. La première méthode implique des communications lors de l'exécution, mais est l'unique possibilité de traduction pour les langages data-parallèles n'offrant pas la possibilité d'alignement. La deuxième méthode est par contre bien adaptée à HPF, la directive align étant tout à fait adaptée à cela. L'équation se traduit donc ainsi :
 

align X(z) with T(z)
align Y(z) with T(h(z))
 
...voir exemple

Réduction géométrique combinée avec une opération fonctionnelle

Seules les fonctions XXX_SCATTER de réduction des tableaux d'HPF permettent d'exprimer les réductions PEI en toute généralité. Soit l'équation PEI :
 

Y = fr  (gr ; X)
fr = id # (a;b).(a @ fr(b))
 
et soit e_@ l'élément neutre de @. Pour traduire cette équation, il faut d'abord construire les tableaux d'indirections x₁ à x_n utilisés par HPF. On définit pour cela la fonction index qui sélectionne la k^ième dimension d'un m-uplet :
 

index :

Nm x [1...m]   ((i1,...,im),k)

N  ik

 
Les tableaux x₁,..., x_n sont construits par : x_k (i₁,...,i_m) = index(gr(i₁,...,i_m),k)
La traduction de l'énoncé PEI est alors :
 
Y = @_SCATTER (X, e_@, x₁,..., x_n)
 
...voir exemple
Définition récursive

On rencontre souvent dans les énoncés PEI une définition récursive d'un champ de données sous la forme :
 

Y = fc  (X /&/ (Y  g₁) /&/ ... /&/ (Y  g_n)))
 
La traduction est constituée de deux blocs d'instructions. Le premier effectue l'initialisation de Y avec les valeurs de X utilisées au premier instant de calcul, tandis que le deuxième est  une boucle séquentielle énumérant les différents instants de calcul. Rappelons qu'une telle équation n'est traduisible que si elle définit un cadencement des calculs.

En outre, la difficulté de traduction de cette équation repose sur le fait que la dimension des données sur lesquelles sont effectuées les fonctions n'est pas explicite, alors qu'en HPF , on doit distinguer les cas pour lesquels l'opérateur a un nombre différent d'arguments. Cela revient à décomposer l'union des domaines de valeurs utilisés en sous-domaines sur lesquels le nombre de valeurs superposées est constant.
 

...voir exemple