1  Parallélisme

Eric Goubault

Commissariat à l'Energie Atomique

Saclay

2  Algorithmique sur anneau de processeurs

3  Architecture

file=ring.eps,width=15cm,clip=

4  Architecture

5  Fonctionnement

Mode SPMD: On doit s'arranger pour qu'à tout send corresponde un receive.

6  Sémantique

Plusieurs hypothèses possibles:

7  Modélisation du coût d'une communication

Difficile en général: ici envoyer/recevoir un message de longueur L (au voisin immédiat) coûtera:
b+Lt
où: D'où envoyer/recevoir un message de longueur L de proc_num()+/-q coûte q(b+Lt).

8  Problème élémentaire: la diffusion

9  Implémentation (receive bloquant)

broadcast(k,adr,L) { // emetteur initial=k
  q = my_num();
  p = tot_proc_num();
  if (q == k) 
    (1) send(adr,L);       
  else
    if (q == k-1 mod p)
      (2) receive(adr,L);  
    else {
      (3) receive(adr,L);  
      (4) send(adr,L);      
    } 
}

10  Exécution - temps 0 et k=0

file=ringd0.eps,width=15cm,clip=

11  Exécution - temps b+Lt

file=ringd1.eps,width=15cm,clip=

12  Exécution - temps k(b+Lt) (k<p-1)

file=ringd2.eps,width=15cm,clip=

13  Exécution - temps (p-1)(b+Lt)

file=ringd3.eps,width=15cm,clip=

14  Diffusion personnalisée

15  Programme

scatter(k,adr,L) {
  q = my_num();
  p = tot_proc_num();
  if (q == k) {
    adr = adr[k];
    for (i=1;i<p;i=i+1)
      send(adr[k-i mod p],L); }
  else 
    (1) receive(adr,L);
  for (i=1;i<k-q mod p;i = i+1) {
    (2) send(adr,L); 
    (3) receive(temp,L);
    adr = temp; } }

16  Exécution - temps 0 et k=0

file=ringdp0.eps,width=15cm,clip=

17  Exécution - temps b+Lt

file=ringdp1.eps,width=15cm,clip=

18  Exécution - temps i(b+Lt)

file=ringdp2.eps,width=15cm,clip=

19  Exécution - temps (p-1)(b+Lt)

file=ringdp3.eps,width=15cm,clip=

20  Echange total

Peut se faire aussi en (p-1)(b+Lt). De même pour l'échange total personnalisé

21  Programme

all-to-all(my_adr,adr,L) {
  q = my_num();
  p = tot_proc_num();
  adr[q] == my_adr;
  for (i=1;i<p;i++) {
    send(adr[q-i+1 mod p],L);
    receive(adr[q-i mod p],L);
  }
}

22  Diffusion pipelinée

Le temps d'une diffusion simple et d'une diffusion personnalisée sont les mêmes; peut-on améliorer le temps de la diffusion simple en utilisant les idées de la diffusion personnalisée?

23  Programme

broadcast(k,adr,L) {
  q = my_num();
  p = tot_proc_num();
  if (q == k)
    for (i=1;i<=r;i++) send(adr[i],L/r);
  else
    if (q == k-1 mod p)
      for (i=1;i<=r;i++) receive(adr[i],L/r);
    else {
      receive(adr[1],L/r);
      for (i=1;i<r;i++) {
        send(adr[i],L/r);
        receive(adr[i+1],L/r); } } }

24  Temps d'exécution

25  Optimisation du paramètre r

26  Produit matrice-vecteur

Problème: calculer y=Ax avec,

27  Programme séquentiel

le calcul produit matrice-vecteur revient au calcul de n produits scalaires:

for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
    y[i] = y[i]+a[i,j]*x[j];

28  Principe de la distribution

Distribuer le calcul des produits scalaires aux processeurs:

29  Principe du calcul -distribution initiale des données

P0
æ
è
A00 A01 A02 A03 A04 A05 A06 A07
A10 A11 A12 A13 A14 A15 A16 A17
ö
ø
æ
è
x0
x1
ö
ø

P1
æ
è
A20 A21 A22 A23 A24 A25 A26 A27
A30 A31 A32 A33 A34 A35 A36 A37
ö
ø
æ
è
x2
x3
ö
ø

P2
æ
è
A40 A41 A42 A43 A44 A45 A46 A47
A50 A51 A52 A53 A54 A55 A56 A57
ö
ø
æ
è
x4
x5
ö
ø

P3
æ
è
A60 A61 A62 A63 A64 A65 A66 A67
A70 A71 A72 A73 A74 A75 A76 A77
ö
ø
æ
è
x6
x7
ö
ø

30  Première étape

P0
æ
è
A00 A01 · · · · · ·
A10 A11 · · · · · ·
ö
ø
æ
è
x0
x1
ö
ø
temp ¬
æ
è
x6
x7
ö
ø

P1
æ
è
· · A22 A23 · · · ·
· · A32 A33 · · · ·
ö
ø
æ
è
x2
x3
ö
ø
temp ¬
æ
è
x0
x1
ö
ø

P2
æ
è
· · · · A44 A45 · ·
· · · · A54 A55 · ·
ö
ø
æ
è
x4
x5
ö
ø
temp ¬
æ
è
x2
x3
ö
ø

P3
æ
è
· · · · · · A66 A67
· · · · · · A76 A77
ö
ø
æ
è
x6
x7
ö
ø
temp ¬
æ
è
x4
x5
ö
ø

31  Deuxième étape

P0
æ
è
· · · · · · A06 A07
· · · · · · A16 A17
ö
ø
æ
è
x6
x7
ö
ø
temp ¬
æ
è
x4
x5
ö
ø

P1
æ
è
A20 A21 · · · · · ·
A30 A31 · · · · · ·
ö
ø
æ
è
x0
x1
ö
ø
temp ¬
æ
è
x6
x7
ö
ø

P2
æ
è
· · A42 A43 · · · ·
· · A52 A53 · · · ·
ö
ø
æ
è
x2
x3
ö
ø
temp ¬
æ
è
x0
x1
ö
ø

P3
æ
è
· · · · A64 A65 · ·
· · · · A74 A75 · ·
ö
ø
æ
è
x4
x5
ö
ø
temp ¬
æ
è
x2
x3
ö
ø

32  Troisième étape

P0
æ
è
· · · · A04 A05 · ·
· · · · A14 A15 · ·
ö
ø
æ
è
x4
x5
ö
ø
temp ¬
æ
è
x2
x3
ö
ø

P1
æ
è
· · · · · · A26 A27
· · · · · · A36 A37
ö
ø
æ
è
x6
x7
ö
ø
temp ¬
æ
è
x4
x5
ö
ø

P2
æ
è
A40 A41 · · · · · ·
A50 A51 · · · · · ·
ö
ø
æ
è
x0
x1
ö
ø
temp ¬
æ
è
x6
x7
ö
ø

P3
æ
è
· · A62 A63 · · · ·
· · A72 A73 · · · ·
ö
ø
æ
è
x2
x3
ö
ø
temp ¬
æ
è
x0
x1
ö
ø

33  Quatrième étape

P0
æ
è
· · A02 A03 · · · ·
· · A12 A13 · · · ·
ö
ø
æ
è
x2
x3
ö
ø
temp ¬
æ
è
x0
x1
ö
ø

P1
æ
è
· · · · A24 A25 · ·
· · · · A34 A35 · ·
ö
ø
æ
è
x4
x5
ö
ø
temp ¬
æ
è
x2
x3
ö
ø

P2
æ
è
· · · · · · A46 A47
· · · · · · A56 A57
ö
ø
æ
è
x6
x7
ö
ø
temp ¬
æ
è
x4
x5
ö
ø

P3
æ
è
A60 A61 · · · · · ·
A70 A71 · · · · · ·
ö
ø
æ
è
x0
x1
ö
ø
temp ¬
æ
è
x6
x7
ö
ø

34  Programme

matrice-vecteur(A,x,y) {
  q = my_num();
  p = tot_proc_num();
  for (step=0;step<p;step++) {
    send(x,r);
    for (i=0;i<r;i++) 
      for (j=0;j<r;j++)
        y[i] = y[i]+a[i,(q-step mod p)r+j]*x[j];
    receive(temp,r);        
    x = temp;
  }
}

35  Performances

(on aurait aussi pu procéder à un échange total de x au début...)

36  Factorisation LU

Problème: résolution d'un système linéaire dense Ax=b par triangulation de Gauss. Version séquentielle:

for (k=0;k<n-1;k++) {
  prep(k): for (i=k;i<n;i++)
    a[i,k]=-a[i,k]/a[k,k];
  for (j=k+1;j<n;j++)
    update(k,j): for (i=k;i<n;i++)
      a[i,j]=a[i,j]+a[i,k]*a[k,j];
}

37  Distribution

Voir poly pour version la plus générale.

38  Programme - ici alloc(k)=k

q = my_num();
p = tot_proc_num();
for (k=0;k<n-1;k++) {
  if (k == q) { 
    prep(k): for (i=k;i<n;i++)
      buffer[i-k-1] = -a[i,k]/a[k,k];
    broadcast(k,buffer,n-k); 
  }
  else { 
      receive(buffer,n-k);
      update(k,q): for (i=k;k<n;k++)
        a[i,q] = a[i,q]+buffer[i-k]*a[k,q]; }
}

39  Difficultés de l'algorithme

40  Cas de l'allocation cyclique par lignes

P0
(
A00 A01 A02 A03 A04 A05 A06 A07
)
P1
(
A10 A11 A12 A13 A14 A15 A16 A17
)
P2
(
A20 A21 A22 A23 A24 A25 A26 A27
)
P3
(
A30 A31 A32 A33 A34 A35 A36 A37
)

P0
(
A40 A41 A42 A43 A44 A45 A46 A47
)
P1
(
A50 A51 A52 A53 A54 A55 A56 A57
)
P2
(
A60 A61 A62 A63 A64 A65 A66 A67
)
P3
(
A70 A71 A72 A73 A74 A75 A76 A77
)

41  Allocation cyclique - k=0

P0: prep(0); broadcast()
(
-1 A01' A02' A03' A04' A05' A06' A07'
)
P1
(
A10 A11 A12 A13 A14 A15 A16 A17
)
P2
(
A20 A21 A22 A23 A24 A25 A26 A27
)
P3
(
A30 A31 A32 A33 A34 A35 A36 A37
)

P0
(
A40 A41 A42 A43 A44 A45 A46 A47
)
P1
(
A50 A51 A52 A53 A54 A55 A56 A57
)
P2
(
A60 A61 A62 A63 A64 A65 A66 A67
)
P3
(
A70 A71 A72 A73 A74 A75 A76 A77
)

42  Allocation cyclique - k=0

P0
(
-1 A01' A02' A03' A04' A05' A06' A07'
)
P1: receive(); update(0,1)
(
0 A11' A12' A13' A14' A15' A16' A17'
)
P2: receive(); update(0,2)
(
0 A21' A22' A23' A24' A25' A26' A27'
)
P3: receive(); update(0,3)
(
0 A31' A32' A33' A34' A35' A36' A37'
)

P0: update(0,4)
(
0 A41' A42' A43' A44' A45' A46' A47'
)
P1
(
A50 A51 A52 A53 A54 A55 A56 A57
)
P2
(
A60 A61 A62 A63 A64 A65 A66 A67
)
P3
(
A70 A71 A72 A73 A74 A75 A76 A77
)

43  Puis...

P0
(
-1 A01' A02' A03' A04' A05' A06' A07'
)
P1
(
0 A11' A12' A13' A14' A15' A16' A17'
)
P2
(
0 A21' A22' A23' A24' A25' A26' A27'
)
P3
(
0 A31' A32' A33' A34' A35' A36' A37'
)

P0
(
0 A41' A42' A43' A44' A45' A46' A47'
)
P1: receive(); update(0,5)
(
0 A51' A52' A53' A54' A55' A56' A57'
)
P2: receive(); update(0,6)
(
0 A61' A62' A63' A64' A65' A66' A67'
)
P3: receive(); update(0,7)
(
0 A71' A72' A73' A74' A75' A76' A77'
)

44  Allocation cyclique - k=1

P0
(
-1 A01' A02' A03' A04' A05' A06' A07'
)
P1: prep(1); broadcast()
(
0 -1 A12'' A13'' A14'' A15'' A16'' A17''
)
P2
(
0 A21' A22' A23' A24' A25' A26' A27'
)
P3
(
0 A31' A32' A33' A34' A35' A36' A37'
)

P0
(
0 A41' A42' A43' A44' A45' A46' A47'
)
P1
(
0 A51' A52' A53' A54' A55' A56' A57'
)
P2
(
0 A61' A62' A63' A64' A65' A66' A67'
)
P3
(
0 A71' A72' A73' A74' A75' A76' A77'
)

45  Allocation cyclique - k=1

P0
(
-1 A01' A02' A03' A04' A05' A06' A07'
)
P1
(
0 -1 A12'' A13'' A14'' A15'' A16'' A17''
)
P2: receive(); update(1,2)
(
0 0 A22'' A23'' A24'' A25'' A26'' A27''
)
P3: receive(); update(1,3)
(
0 0 A32'' A33'' A34'' A35'' A36'' A37''
)

P0: receive(); update(1,4)
(
0 0 A42'' A43'' A44'' A45'' A46'' A47''
)
P1
(
0 A51' A52' A53' A54' A55' A56' A57'
)
P2
(
0 A61' A62' A63' A64' A65' A66' A67'
)
P3
(
0 A71' A72' A73' A74' A75' A76' A77'
)

46  Cas de l'allocation 1 ligne 1 processeur - p=n

Ici, alloc(k)==k

47  Temps de calcul

48  Temps de calcul

49  Sur anneau: recouvrement communication/calcul

q = my_num();
p = tot_proc_num();
l = 0;
for (k=0;k<n-1;k++) {
  if (k == q mod p) {
    prep(k): for (i=k;i<n;i++)
      buffer[i-k-1] = -a[i,l]/a[k,l];
    l++; send(buffer,n-k); }
  else { receive(buffer,n-k);
    if (q != k-1 mod p) send(buffer,n-k); }
  for (j=l;j<r;j++)
    update(k,j): for (i=k;k<n;k++)
      a[i,j] = a[i,j]+buffer[i-k]*a[k,j]; }

50  Défaut...

Sur P1:

51  

P0 P1 P2 P3
prep(0)      
send(0) receive(0)    
update(0,4) send(0) receive(0)  
update(0,8) update(0,1) send(0) receive(0)
update(0,12) update(0,5) update(0,2) update(0,3)
  update(0,9) update(0,6) update(0,7)
  update(0,13) update(0,10) update(0,11)
  prep(1) update(0,14) update(0,15)
  send(1) receive(1)  
  update(1,5) send(1) receive(1)
receive(1) update(1,9) update(1,2) send(1)
update(1,4) update(1,13) update(1,6) update(1,3)
update(1,8)   update(1,10) update(1,7)
update(1,12)   update(1,14) update(1,11)
... ... ... ...

52  Défaut...

P1 aurait pu faire:

53  

P0 P1 P2 P3
prep(0)      
send(0) || up(0,4) receive(0)    
up(0,8) send(0) || up(0,1) receive(0)  
up(0,12) prep(1) send(0) || up(0,2) receive(0)
  send(1) || up(0,5) receive(1) || up(0,6) up(0,3)
  up(0,9) send(1) || up(0,10) receive(1) || up(0,7)
receive(1) up(0,13) up(0,14) send(1) || up(0,11)
up(1,4) up(1,5) up(1,2) up(0,15)
up(1,8) up(1,9) prep(2) up(1,3)
up(1,12) up(1,13) send(2) || up(1,6) receive(2) || up(1,7)
receive(2)   up(1,10) send(2) || up(1,11)
send(2) || up(2,4) receive(2) up(1,14) up(1,15)
... ... ... ...


This document was translated from LATEX by HEVEA.