Exemples

• addition d'une matrice et de sa transposée
• changement de base
• routage
• réduction géometrique
• opération fonctionnelle
• sémantique d'une équation
• interprétation fonctionnelle
• raffinement
• méthodes de raffinement
• fenêtre VPEI
• transformation par changement de base
• transformation pour la simplification des communications
• introduction d'une diffusion
• cadencement des équations récurrentes
• traduction d'un changement de base en HPF
• traduction d'une opération géométrique combinée avec une opération fonctionnelle en HPF
• traduction d'une définition récursive en HPF

Exemple 1 : Addition d'une matrice et de sa transposée

MatSum : A C
 

A = matrix :: A  T = A  transp  C = add  (A /&/ T)

matrix = (i,j)|(0<=i<n & 0<=j<n).(i,j)
transp = (i,j)|(0<=i<n & 0<=j<n).(j,i)
add = (a;b).(a+b)

La première équation est une précondition sur le champ de donnée en entrée A. Elle exprime que A n'est pas modifié par l'application du changement de base matrix.

La deuxième équation définit le champ T par une opération de routage appliquée sur A. Les valeurs placées aux points de coordonnées (i,j) dans T sont celles placées en (j,i) dans le champ A.

La troisième équation définit le champ de données en sortie C. La partie droite définit la superposition de A et T. L'opération fonctionnelle définie ici consiste en l'application de la fonction add à tous les éléments de ce champ.

Exemple 2 : Changement de base

 

1 2 -3 1 V

*

1 2 -3 1 M

M = align :: V
align = (i)|(0<=i<=3).(i mod 2,i/2)

Exemple 3 : Routage

 

1 2 -3 1 V

*

1 1 2 -3 W

W = V  shift
shift = (i).((i-1) mod 4)

 

1 2 -3 1 V

*

1 1 1 1 W

W = V  spread
spread = (i)|(0<=i<4).(0)

Exemple 4 : Réduction géométrique

 

4 7 5 X

*

7;5;4 * * Y

Y = merge ; X
merge = (i)|(0<=i<3).(0)

Exemple 5 : Opération fonctionnelle

 

1 2 -3 1 V

*

4 5 0 4 W

W = inc  V
inc= (a).(a+3)

Exemple 6 : Sémantique d'une équation

Soit A = (v_A : _A) et B = (v_B : _B) et l'équation E : A = add (size :: B)

La sémantique de E est

(v_A= add o v_B o size^-1 ^ _A= _Bo size^-1 ^ dom(v_B) inclus dans dom(size) ^ img(v_B) inclus dans dom(add))

Exemple 7 : Interprétation fonctionnelle d'un champ résultat

Considérons le programme suivant et cherchons l'interprétation fonctionnelle du champ résultat B en fonction de l'entrée V.

P: V B
 

V = align :: M  A = M  spread  B = inc  A

align = (i,j)|(i=0).(j)
spread = (i,j).(0,j)
inc = (a).(a+1)

De la première équation, on tire v_V = v_M o align^-1 et _V = _M o align^-1. Il n'y a pas de changement de base entre les champs A, B et M donc _A = _B = _M.

[[B]] = [[inc  A]]

= inc o [[A]]
= inc o [[M  spread]]
= inc o [[M]] o _M o spread o _M^-1
= inc o v_M o _M^-1 o _M o spread o _M^-1
= inc o v_M o spread o _M^-1
= inc o v_V o align o spread o _M^-1
soit v_B o _B^-1 = inc o v_V o align o spread o _M^-1

et finalement v_B = inc o v_V o align o spread

Exemple 8 : Raffinement d'un programme

 Le programme P2 est raffiné par le programme P3

P2: X Y    X = carre :: X  Y = X carre = (i,j)|(0<=i,j<n).(i,j)

P3: X Y    X = carre :: X  transp :: Y = X carre = (i,j)|(0<=i,j<n).(i,j)  transp = (i,j)|(0<=i,j<n).(j,i)

 

Exemple 9 : Méthodes de raffinement

Raffinement par introduction d'un champ intermédiaire

P2 raffiné par P3
 

P2: X Y    X = carre :: X  Y = X carre = (i,j)|(0<=i,j<n).(i,j)

P3: X Y    X = carre :: X  Z = X  Y = Z carre = (i,j)|(0<=i,j<n).(i,j)

 

P4 raffiné par P5
 

P4: X Y    X = vecteur :: X  Y = X

P5: X Y    Y = X

 

P5 raffiné par P6

P6: X Y
 

vecteur :: Z = X  Y = vecteur :: Z

 

Exemple 10 : Construction d'un programme de multiplication de matrices avec VPEI
 

Exemple 11 : Transformation par changement de base

Le programme suivant traduit l'algorithme d'élimination de Gauss : il résout le système linéaire Ax = b où A est une matrice nxn et b un vecteur de taille n. L'algorithme procède pour cela à une triangularisation de la matrice A, ce à quoi nous nous intéressons ici. Les champs de données en entrée sont donc la matrice A et le vecteur B et les champs de données en sortie sont la matrice triangularisée XN et le vecteur modifié YN.

Le programme Gauss1 fait appel à des opérations de type diffusion, comme par exemple la fonction pivot, en choisissant l'axe k comme direction d'ordonnancement.

Le programme Gauss2 est une version systolique du programme Gauss1, obtenu par un nombre fini d'applications successives des règles de raffinement, définissant ainsi une stratégie bientôt implantée dans l'environnement de transformation.

Gauss1 : (A,B) (XN,YN)

A = alignx :: X  B = aligny :: Y  C = el  (X /&/ Y /&/ (C  pre) /&/ (C  cp) /&/ (C  lp) /&/ (C  pivot))  XN = C  last1  YN = C  last2

alignx = (i,j,k)|(1<=i<=n & 1<=j<=n & k=0).(i,j)
aligny = (i,j,k)|(1<=i<=n & j=n+1 & k=0).(i)
pre = (i,j,k)|(k<=i<=n & 1<=j<=n+1 & 0<k).(i,j,k-1)
pivot = (i,j,k)|(k<=i<=n & 1<=j<=n+1 & 0<k).(k,k,k-1)
cp = (i,j,k)|(k<=i<=n & 1<=j<=n+1 & 0<k).(i,k,k-1)
lp = (i,j,k)|(k<=i<=n & 1<=j<=n+1 & 0<k).(k,j,k-1)
el = id # (a;b;c;d).(a-b*c/d)
last1 = (i,j,k)|(1<=i<=n & i<=j<=n & k=i-1).(i,j,k)
last2 = (i,j,k)|(1<=i<=n & j=n+1 & k=i-1).(i,j,k)
 

Gauss2 : (A,B) (XN,YN)

A = alignx' :: X  B = aligny' :: Y  C = el  (X /&/ Y /&/ (C  pre') /&/ (C  cp') /&/ (C  lp') /&/ (C  pivot'))  XN = C  last1'  YN = C  last2'

alignx' = (i,j,k)|(1<=i<=n & 1<=k-i-j<=n & j=1).(i,k-i-j)
aligny' = (i,j,k)|(1<=i<=n & k-i-j=n+1 & j=1).(i)
pre'    = (i,j,k)|(j<i<=n & 2*j+i<k & k-i-j<=n+1 & 1<=j<=n).(i,j-1,k-1)
pivot'  = (i,j,k)|(j<i<=n & 2*j+i<k & k-i-j<=n+1 & 1<=j<=n).(j,j-1,3*j-1)
cp'     = (i,j,k)|(j<i<=n & 2*j+i<k & k-i-j<=n+1 & 1<=j<=n).(i,j-1,i+2*j-1)
lp'     = (i,j,k)|(j<i<=n & 2*j+i<k & k-i-j<=n+1 & 1<=j<=n).(j,j-1,j+k-i-1)
el      = id # (a;b;c;d).(a-b*c/d)
last1'  = (i,j,k)|(1<=i<=n & i<=k-i-j<=n & j=i-1).(i,j,k)
last2'  = (i,j,k)|(1<=i<=n & k-i-j=n+1 & j=i-1).(i,j,k)

Exemple 12 : Simplification des communications - application au produit matrice-vecteur

Considérons une première version, systolique, de programme du produit matrice-vecteur, calculant p = A x b, où b est un vecteur de longueur n. La première phase de ce calcul, auquel nous nous intéressons ici exclusivement, consiste a effectuer la multiplication des coefficients.

Dans le programme Matvect1, le vecteur b est initialement placé sur la diagonale de la matrice A. A chaque étape indexée par k, on effectue n produits p_ii = A_i,i x b_i sur la diagonale. Tous les éléments de A sont ensuite décalés vers la gauche, et les éléments de b sont décalés le long de la diagonale, vers le haut à gauche, les bords étant bouclés toroïdalement. Au bout de n étapes, on possède l'ensemble des produits sur le plan (i = j) du cube.
 

Matvect1 : (M,V) P
 

A0 = cube :: A0  B0 = cube :: B0  M = aligna :: A0  V = alignb :: B0  A = A0 /&/ (A  left)  B = B0 /&/ (B  upleft)  P = prod  ((A /&/ B)  diag)

 
cube = (i,j,k)|(0<=i,j,k<n).(i,j,k)
aligna = (i,j,k)|(0<=i,j<n & k=0).(i,j)
alignb = (i,j,k)|(0<=i,j<n & i=j & k=0).(i)
left = (i,j,k)|(0<=i,j<n & 0<k<n).(i,(j+1) mod n,k-1)
upleft = (i,j,k)|(0<=i,j<n & 0<k<n).((i+1) mod n,(j+1) mod n,k-1)
prod = (a;b).(a*b)
diag = (i,j,k)|(0<=i,j,k<=n & i=j)
Ce programme fait apparaître des routages de la forme X = X0 /&/ (X  g o f') qui peuvent se réécrire sous la forme : h :: X = (h :: X0) /&/ ((h :: X)  f').
En effet, on peut décomposer les fonctions left et upleft de la façon suivante :
 

left =	(i,j,k)|(0<=k<n).(i,(j+1) mod n,k) o
	(i,j,k)|(0<k<n & 0<=i,j<n).(i,j,k-1)
=	g o prev

 

upleft =	(i,j,k)|(0<=k<n).(i,(j+1) mod n,k) o
	(i,j,k)|(0<=i,j<n).((i+1) mod n,j,k) o
	(i,j,k)|(0<=i,j<n & 0<k<n).(i,j,k-1)
=	g o up o prev

On peut alors procéder aux transformations :
 

A = A0 /&/ (A  left)	h :: A = (h :: A0) /&/ ((h :: A)  prev)
B = B0 /&/ (B  upleft)	h :: B = (h :: B0) /&/ ((h :: B)  up o prev)

avec h = (i,j,k)|(0<=k<n).(i,(j+k) mod n,k)

On doit ensuite exprimer les champs M et V, qui dépendent de A0 et B0 en fonction de h :: A0 et h :: B0, soit :
 

M = (aligna o h-1 o h) :: A0	M = aligna o h-1 :: (h :: A0)
V = (alignb o h-1 o h) :: B0	V = alignb o h-1 :: (h :: B0)

On montre par le calcul que aligna o h_-1 = aligna et alignb o h_-1 = alignb.

Enfin, il faut introduire h :: A et h :: B dans l'équation définissant, ce qui donne, après transformations :
 

P = prod  ((A /&/ B)  diag)

h :: P = prod  (((h :: A) /&/ (h :: B))  diag')

avec diag' = h o diag o h_-1 = (i,j,k)|(i=(j-k) mod n)

On obtient ainsi le programme Matvect1' :
 

Matvect1' : (M,V) P

h :: A0 = cube :: (h :: A0)  h :: B0 = cube :: (h :: B0)  M = aligna :: (h :: A0)  V = alignb :: (h :: B0)  h :: A = h :: A0 /&/ ((h :: A)  prev)  h :: B = h :: B0 /&/ ((h :: B)  up o prev)  h :: P = prod  (((h :: A) /&/ (h :: B))  diag')

 
 

cube	= (i,j,k)|(0<=i,j,k<n).(i,j,k)
prev	= (i,j,k)|(0<=i,j<n & 0<k<n).(i,j,k-1)
up	= (i,j,k)|(0<=i,j<n).((i+1) mod n,j,k)
aligna	= (i,j,k)|(0<=i,j<n & k=0).(i,j)
alignb	= (i,j,k)|(0<=i,j<n & i=j & k=0).(i)
prod	= (a;b).(a*b)
diag'	= (i,j,k)|(i=(j-k) mod n)

 
Ce programme peut encore être raffiné et mener au programme Matvect2 :
 
Matvect2 : (M,V) P

M = aligna :: A0  V = alignb :: B0  A = A0 /&/ (A  prev)  B = B0 /&/ (B  up o prev)  P = prod  (A /&/ B)  diag'

 
 

prev	= (i,j,k)|(0<=i,j<n & 0<k<n).(i,j,k-1)
up	= (i,j,k)|(0<=i,j<n).((i+1) mod n,j,k)
aligna	= (i,j,k)|(0<=i,j<n & k=0).(i,j)
alignb	= (i,j,k)|(0<=i,j<n & i=j & k=0).(i)
prod	= (a;b).(a*b)
diag'	= (i,j,k)|(i=(j-k) mod n)

 

Exemple 13 : Introduction d'une diffusion - application au produit matrice-vecteur

Le programme Matvect2 obtenu à l'exemple 12 peut, par introduction d'une diffusion, raffiner le programme Matvect3 ci-dessous, utilisant uniquement des routages de type diffusion.
 
 Matvect3 : (M,V) P

M = aligna :: A0  V = alignb :: B0  A = A0  spreada  B = B0  spreadb  P = prod  ((A /&/ B)  diag')

 
 

spreada	= (i,j,k)|(0<=i,j,k<n).(i,j,0)
spreadb	= (i,j,k)|(0<=i,j,k<n).((i+k) mod n,j,0)
aligna	= (i,j,k)|(0<=i,j<n & k=0).(i,j)
alignb	= (i,j,k)|(0<=i,j<n & i=j & k=0).(i)
prod	= (a;b).(a*b)
diag'	= (i,j,k)|(i=(j-k) mod n)

 

Exemple 14 : Cadencement des équations récurrentes - processus de diffusion discrète

Le processus de diffusion discrète s'écrit ainsi :
 
do i = 1,n
do j = 1,n
y(i,j) = f(y(i-1,j),y(i,j-1))
enddo
enddo
 
ce qui, en PEI, s'écrit de la façon suivante :
 
Y = f  (X /&/ (Y  f1) /&/ (Y  f2))
f1 = (i,j)|(1<=i,j<=n).(i-1,j)
f2 = (i,j)|(1<=i,j<=n).(i,j-1)
 
où X est le champ contenant les valeurs initiales. Il existe, pour ce type de problème, une transformation affine temps x espace permettant de paralléliser la récurrence. Ici, cette transformation peut être :
 

(

t  p

) = (

1 1  1 0

) (

i  j

)

où l'indice t représente le temps et p les processeurs. En PEI, cette transformation est réalisée en effectuant le changement de base h = (t,p).(t+p,t). On peut donc raffiner le programme précédent et obtenir :
 
Y' = f  (X' /&/ (Y'  g1) /&/ (Y'  g2))
g1 = (t,p)|(1<=p<=n & 1<=t-p<=n).(t-1,p-1)
g2 = (t,p)|(1<=p<=n & 1<=t-p<=n).(t-1,p)
 
où g1 = h o f1 o h^-1 et g2 = h o f2 o h^-1

Exemple 15 : Traduction d'un changement de base en HPF

 

Enoncé PEI	Traduction en HPF
X = matrix :: X  Y = transl :: X  transl = (i,j)|(1<=i,j<=n).(i+1,j)  matrix = (i,j)|(1<=i,j<=n).(i,j)	type X(1:n), type Y(2:n+1)  template T(n+1,n)  align X(i,j) with T(i,j)  align Y(i,j) with T(i+1,j)  forall (i=1:n,j=1:n) Y(i+1,j) = X(i,j)

 

Exemple 16 : Traduction d'une réduction géométrique combinée avec une opération fonctionnelle en HPF

 

Enoncé PEI	Traduction en HPF
Y = sum (red ; X)  sum = id # (a;b).(a+sum(b))  red = (i,j)|(1<=i,j<=3).(i,i)	Y = SUM_SCATTER(X,0,	[	1  2  3 1  2  3 1  2  3	])

 

Exemple 17 : Traduction d'une définition récursive en HPF

 Considérons l'énoncé de l'exemple 14 :
 

Enoncé PEI	Traduction en HPF
Y' = f  (X' /&/ (Y'  g1) /&/ (Y'  g2))  g1 = (t,p)|(1<=p<=n & 1<=t-p<=n).(t-1,p-1)  g2 = (t,p)|(1<=p<=n & 1<=t-p<=n).(t-1,p)	forall (t=1, p=0:1) Y'(t,p) = X(t,p)  do t = 2,2*n    forall (p=max(1,t-n):min(n,t-1)) &    Y'(t,p) = f(X'(t,p),Y'(t-1,p-1),Y'(t-1,p))  enddo