1  Parallélisme

2  Algorithmique sur anneau de processeurs

• Macro-communications sur un anneau
• Produit matrice-vecteur
• Factorisation LU

3  Architecture

4  Architecture

• p processeurs en anneau
• chacun a accès à:
  • son numéro d'ordre (entre 0 et p-1), par my_num()
  • nombre total de processeur: tot_proc_num (=p)

5  Fonctionnement

• tous les processeurs exécutent le même code,
• ils calculent tous dans leur mémoire locale,
• ils peuvent envoyer un message au processeur de numéro
  
  proc_num()+1[p] par send(adr,L) avec,
  • adr, adresse de la première valeur dans la mémoire locale de l'expéditeur
  • L la longueur du message
• ils peuvent recevoir un message de proc_num()-1[p] par
  
  receive(adr,L)

6  Sémantique

• send et receive bloquants (OCCAM etc.)
• plus classiquement send non bloquant mais receive bloquant (mode par défaut en PVM, MPI)
• plus moderne: aucune bloquante (trois threads en fait: 1 pour calcul, 1 pour send, 1 pour receive)

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

• b est le coût d'initialisation (latence)
• t (débit) mesure la vitesse de transmission en régime permanent

8  Problème élémentaire: la diffusion

• C'est l'envoi par un P_k d'un message de longueur L (stocké à l'adresse adr) à tous les autres processeurs:
• Implémenté de faon efficace dans la plupart des librairies de communications (PVM, MPI etc.).

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

11  Exécution - temps b+Lt

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

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

14  Diffusion personnalisée

• send non-bloquant, receive bloquant
• envoi par P_k d'un message différent à tous les processeurs (en adr[q] dans P_k pour P_q)
• à la fin chaque processeur a son message à la location adr
• opère en pipeline: recouvrement entre les différentes communications!

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

17  Exécution - temps b+Lt

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

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

20  Echange total

• Chaque processeur k veut envoyer un message à tous les autres
• Au départ chaque processeur dispose de son message à envoyer à tous les autres à la location my_adr
• A la fin, tous ont un tableau (le même) adr[] tel que adr[q] contient le message envoyé par le processeur q

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

• tronçonner le message à envoyer en r morceaux (r divise L)
• l'emetteur envoie successivement les r morceaux, avec recouvrement partiel des communications
• au début ces morceaux de messages sont dans adr[1],...,adr[r] du processeur k

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

• le premier morceau de longueur L/r du message sera arrivé au dernier processeur k-1 mod p en temps (p-1)(b+L/ rt) (diffusion simple)
• les r-1 autres morceaux arrivent les uns derrière les autres, d'où un temps supplémentaire de (r-1)(b+L/ rt)
• En tout (p-2+r)(b+L/ r t)

25  Optimisation du paramètre r

• r_opt=L(p-2)t/ b
• le temps optimal d'exécution est donc de

  (

  (p-2)b+Lt

  )

  2

• quand L tend vers l'infini, ceci est asymptotiquement équivalent à Lt, le facteur p devient négligeable!

26  Produit matrice-vecteur

• A matrice de dimension n × n
• x vecteur à n composantes (de 0 à n-1)
• sur un anneau de p processeurs, avec r=n/p entier

27  Programme séquentiel

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

• chaque processeur a en mémoire r lignes de la matrice A rangée dans une matrice a de dimension r × n
• P_q contient les lignes qr à (q+1)r-1 de la matrice A et les composantes de même rang des vecteurs x ety:

  float a[r][n];
  float x[r],y[r];
  

29  Principe du calcul -distribution initiale des données

30  Première étape

31  Deuxième étape

32  Troisième étape

33  Quatrième étape

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

• en notant t_a le temps de calcul élémentaire, t_c le temps de communication élémentaire
• il y a p étapes identiques, chacune de temps égal le plus long entre le calcul local et le temps de communication: max(r² t_a,b+rt_c)
• d'où temps total de p*max(r² t_a,b+rt_c)
• quand n assez grand r² t_a devient prépondérant, d'où asympotiquement un temps de n²/ pt_a: efficacité 1!

36  Factorisation LU

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

• distribution des colonnes aux différents processeurs
• on suppose que cette distribution nous est donnée par une fonction alloc telle que alloc(k)=q veut dire que la kième colonne est affectée à la mémoire locale de P_q
• on utilise la fonction broadcast, pour faire en sorte qu'à l'étape k, le processeur qui possède la colonne k la diffuse à tous les autres

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

• le nombre de données varie au cours des étapes (de moins en moins)
• le volume de calcul n'est pas proportionnel au volume des données: quand un processeur a par exemple r lignes consécutives, le dernier processeur a moins de calcul (que de données) par rapport au premier
• il faut donc une allocation qui réussisse à équilibrer le volume des données et du travail!
• équilibrage de charge à chaque étape de l'algorithme, et pas seulement global

40  Cas de l'allocation cyclique par lignes

41  Allocation cyclique - k=0

42  Allocation cyclique - k=0

43  Puis...

44  Allocation cyclique - k=1

45  Allocation cyclique - k=1

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

• Coût de la mise à jour (update) de la colonne j par le processeur j:
  • à toutes les étapes k=0 à k=n-1
  • un coût de n-k-1 pour l'étape k (éléments en position k+1 à n-1)
  • d'où un coût total de

    t=

    n-1 S k=0

    (n-k-1)ta=

    n(n-1) 2

47  Temps de calcul

• Le chemin critique d'exécution est:
  prep₀(0)® update₁(0,1), prep₁(1) ® update₂(1,2), prep₂(2) ® ...
• Comme si on faisait environ r fois le travail quand allocation cyclique pour r=n/ p processeurs
• Remarque: recouvrement des communications, mais pas communication/calcul!

48  Temps de calcul

• nb+n²/ 2t_c+O(1) pour les n-1 communications (transportant de l'ordre de n² données)
• n²/ 2t_a+O(1) pour les prep
• Pour l'update des r colonnes sur le processeur j mod p, en parallèle sur tous les processeurs, environ rn(n-1)/ 2
• D'où un coût de l'ordre de n³/ 2p pour les update des p processeurs: terme dominant si p<<n et efficacité excellente asymptotiquement (pour n grand)

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

• Etape k=0: P₁ reçoit la colonne pivot 0 de P₀
• P₁ l'envoit à P₂
• Fait update(0,j) pour toutes les colonnes j qui lui appartiennent, cad j=1 mod p
• Etape k=1: fait prep(1)
• Envoie la colonne pivot 1 à P₂
• Fait update(1,j) pour toutes les colonnes j qui lui appartiennent, cad j=1 mod p
• etc.

51  

52  Défaut...

• update(0,1)
• prep(1)
• Envoi vers P₂
• update(0,j) pour j=1 mod p et j>1
• etc.

53  

This document was translated from L^AT_EX by H^EV^EA.