Transformations de programmes

Le formalisme étant défini, il est alors possible de traiter les énoncés PEI comme de véritables systèmes d'équations mathématiques, c'est-à-dire les modifier pour obtenir de nouveaux énoncés satisfaisant encore les propriétés des énoncés initiaux. Lorsqu'on agit par équivalence, on transforme véritablement les programmes de façon certifiée, dans le but d'obtenir un nouveau programme dont on peut espérer qu'il soit meilleur.

Raffinement

Le raffinement est un procédé de construction ou de transformation de programmes qui consiste à obtenir un programme obéissant à toute spécification que satisfait un programme initial.

Parmi les équations du système d'un énoncé PEI, on distingue deux types d'équations :

• les pré-équations : celles qui portent uniquement sur des entrées,
• les post-équations : celles qui comportent des champs de données intermédiaires ou des sorties.

On associe alors à un énoncé P une propriété sat(P), dont nous dirons qu'elle est satisfaite par P, et qui précise que pour tout champ de données d'entrée D vérifiant les pré-équations S₁, la solution est formée d'un champ de données de sortie R vérifiant les post-équations S₂.

P : D R

S1  S2

 
Définition
 
En PEI, on dit qu'un énoncé P est raffiné par un énoncé P' si et seulement si sat(P') implique sat(P) modulo l'équivalence, i.e. si et seulement si sat(P') implique sat(P'') avec :
• ou bien P'' est le programme P où toutes les occurences de chaque champ de données X sont remplacées par une expression e(X) fortement équivalente à X.
• ou bien P'' est le programme P où une expression E est remplacée par une expression e(E) faiblement équivalente à E.

Ainsi, on peut raffiner un programme en substituant un champ par un autre champ qui lui est équivalent.

 
...voir exemple
Propriétés

On peut raffiner un programme en procédant comme suit, en veillant à ce que les domaines de définition et image des fonctions impliquées le permettent :

• toutes les occurences d'un champ de données X peuvent être remplacées par h :: X et réciproquement.
• une expression E peut être remplacée par h :: (E  g^-1) où h est une inverse gauche de g.
• une expression E peut être remplacée par (h :: E)  g^-1 où h est une inverse droite de g.

 
...voir exemples
Calcul de raffinement

Le calcul de raffinement permet de construire un programme raffinant un programme donné sans utiliser l'implication modulo l'équivalence. Il stipule que le raffinement d'un énoncé peut se faire par la substitution d'une équation de cet énoncé par une autre. On est ainsi amené à introduire des règles de substitution du type E E' où E est l'expression initiale et E' celle qu'on peut lui substituer :
 

Règles de raffinement
 
Y = X  h :: Y = h :: X
h :: Y = h :: X  Y = X

Y = f1  (f2 :: X)  Y = f2 :: (f1  X)
Y = f2 :: (f1  X)  Y = f1  (f2 :: X)
Y = (f1  X)  f2  Y = f1  (X  f2)
Y = f1  (X  f2)  Y = (f1  X)  f2
Y = (f2 :: X)  f1  Y = f2 :: (X  f2^-1 o f1 o f2)
Y = f2 :: (X  f1)  Y = (f2 :: X)  f2 o f1 o f2^-1
Y = f1 ; (f2 :: X)  Y = f2 :: (f2^-1 o f1 o f2 ; X)
Y = f2 :: (f1 ; X)  Y = f2 o f1 o f2^-1 ; (f2 :: X)

Y = (f1 o f2)  X  Y = f1  (f2  X)
Y = f1  (f2  X)  Y = (f1 o f2)  X
Y = X  (f1 o f2)  Y = (X  f1)  f2
Y = (X  f1)  f2  Y = X  (f1 o f2)
Y = (f1 o f2) ; X  Y = f1 ; (f2 ; X)
Y = (f1 o f2) :: X  Y = f1 :: (f2 :: X)
Y = f1 :: (f2 :: X)  Y = (f1 o f2) :: X

Y = (X1 /&/ X2)  f  Y = (X1  f) /&/ (X2  f)
Y = (X1  f) /&/ (X2  f)  Y = (X1 /&/ X2)  f
Y = X  (f1 # f2)  Y = (X  f1) /&/ (X  f2)
Y = (X  f1) /&/ (X  f2)  Y = X  (f1 # f2)
Y = (f1 # f2) ; X  Y = (f1 ; X) /&/ (f2 ; X)
Y = (f :: X1) /&/ (f :: X2)  Y = f :: (X1 /&/ X2)
Y = f :: (X1 /&/ X2)  Y = (f :: X1) /&/ (f :: X2)

 

Outils de transformation

Outil visuel pour la conception de programmes : VPEI

En PEI comme dans la plupart des langages data-parallèles (C*, CM_Fortran, MPL, Hyper-C, etc...) le placement géométrique des données est l'élément déterminant de la conception d'un programme. Si cela doit avoir une influence favorable sur la performance des programmes, l'utilisateur doit cependant fournir un effort supplémentaire pour y parvenir.

VPEI est un prototype d'outil de conception de programmes PEI par simple manipulations graphiques. L'utilisateur peut créer des champs de données dans Z, Z² ou Z³ puis leur appliquer une opération en entrant la fonction au clavier et, selon l'opération choisie, le logiciel permet de visualiser schématiquement les effets ainsi produits. VPEI autorise également certaines définitions récursives de champs de données.
 

...voir exemple
 
VPEI possède un certain nombre de limitations parmi lesquelles l'obligation de construire des définitions explicites, c'est-à-dire assimilables à des affectations. On ne peut appliquer une opération que sur un champ précédemment défini, ce qui se révèle génant dans les définitions récursives. De plus, VPEI ne permet de concevoir que de petits programmes PEI, les manipulations étant vite alourdies par les champs intermédiaires.

Un outil pour le raffinement de programmes

L'outil PEI a été développé par E. Violard, dans le cadre de sa thèse, et permet la manipulation de programmes. Les règles de raffinement y sont implantées et l'utilisateur s'en sert pour transformer un programme préexistant, éventuellement écrit avec VPEI. Cet outil ne permet pour l'instant pas des transformations complètement automatisées.

Certaines fonctions ont été ajoutées depuis, parmi lesquels un traducteur permettant d'associer une interprétation fonctionnelle (sous la forme d'un programme CAML) à un programme PEI. Le programme CAML ainsi généré permet notamment de vérifier l'exactitude des résultats obtenus sur un jeu d'essai. Un autre outil, utilisant le calculateur OMEGA, type chacune des expressions de champs de données pour contrôler la cohérence des expressions vis à vis des opérations.

Stratégies de transformations

Les stratégies sont constituées de l'application successive de plusieurs règles de raffinement en vue de transformer une forme de programme en une autre. En effet, selon l'architecture de la machine parallèle, les primitives implantées sur le matériel ou dans le langage visé, certaines solutions sont connues pour être plus efficaces que d'autres. Les stratégies permettent de passer d'une solution à une autre. Nous en présentons ici quelques unes.

Transformation par changement de base

Certains programmes utilisent des opérations géométriques de type diffusion, ce qui implique un type de communication que n'autorisent pas certaines machines, comme c'est le cas par exemple pour les réseaux systoliques où, par hypothèse, seules les communications d'un processeur vers un de ses voisins sont permises. Cette contrainte de communication influe sur l'ordonnancement du programme, et il est nécessaire de trouver une nouvelle écriture du programme pour en tenir compte.
 

...voir exemple

Une autre stratégie, utilisant le changement de base par équivalence faible, permet de modifier le placement initial des données. On sait en effet que le placement des données revêt une importance primordiale dans le domaine du parallélisme, étant donné le coût élevé des communications.

 Simplification des communications

Simplifier les opérations de routage présente au moins deux intérêts :

• diminuer le volume des communications à effectuer
• conclure sur l'équivalence de plusieurs programmes différant par leurs communications.

La simplification est possible lorsque les routages sont uniformes avec la forme générale f(i₁,...,i_m-1,i_m) = (i₁+a₁,...i_m-1+a_m-1,i_m-1). Bien que ces conditions semblent contraignantes, de nombreux algorithmes systoliques utilisent de tels routages.
 
Le principe de la simplification repose sur l'expression de la fonction utilisée par un routage, sous la forme d'une composition de fonctions. Dans un programme où un champ de données est défini par Y = X  f, on cherche à réécrire la fonction f sous la forme f = g o f', où f' est une fonction plus "simple" que f. On cherche ensuite une définition équivalente à celle de Y qui utilise uniquement le routage f'. Il faut trouver pour cela le changement de base bijectif h tel que h :: Y = X  f'. Il s'agit donc de trouver une représentation différente des champs ne nécessitant plus le routage des valeurs par la fonction g.

On s'intéresse plus particulièrement aux champs de données définis récursivement à l'aide de ces opérations de routage, de la forme X = X0 /&/ (X  f).
 

...voir exemple
Introduction d'une diffusion

Certains algorithmes sont qualifiés de systoliques car ils font appels à des communications point à point. Si on dispose d'une primitive de diffusion, caractéristique du modèle de programmation data-parallèle, ces communications peuvent être remplacées par cet opérateur de diffusion. Dès lors, une définition récursive de champ de données devient simple, faisant intervenir une opération de routage, qui décrit une nouvelle stratégie de transformation de routage :

Si g est une fonction définie récursivement par g = i # (g o s), où i est l'identité définie sur un sous-domaine, et s une fonction. L'équation Y = X  g se réécrit alors en Y = X  i /&/ Y  s.
 

...voir exemple