1  Parallélisme

2  Problèmes d'ordonnancement

• Revenons à la mémoire partagée... et aux PRAM!
• Problème important: paralléliser les nids de boucle
• ou au moins comprendre ce qui est intrinsèquement séquentiel, de ce qui peut être calculé en parallèle

3  Loi d'Amdahl

• s pourcent séquentiel,
• sur p processeurs,
• accélération du calcul complet par rapport à un calcul séquentiel sera au maximum de,

  1

  s+ 1-s p

  (maximum de 1/ s)

4  Exemple de nid de boucle

for (i=1;i<=N;i++) {
  for (j=i;j<=N+1;j++)
    for (k=j-i;k<=N;k++) {
      S1;
      S2;
    }
  for (r=1;r<=N;r++)
    S3;
}

5  Explication

• Ceci n'est pas un nid de boucle parfait:
• S1 et S2 sont englobées par les boucles i, j et k
• alors que S3 est englobée par les boucles i et r

6  Vecteurs d'itération

• Les itérations de n boucles parfaitement imbriquées sont représentées par un vecteur de dimension n
• Par exemple, pour S3 on a un vecteur d'itération en (i,r) dont le domaine est 1 £ i, r £ N
• Pour S1 on a un vecteur d'itération en (i,j,k) dont le domaine est 1 £ i £ N, i £ j £ N+1 et j-i £ k £ N.
• On note une instance de S à l'itération I, S(I)
• On suppose que les domaines d'itération forment des polyèdres.

7  Ordre séquentiel d'exécution

• Pour les nids de boucles non-parfaits, les domaines d'itérations sont incomparables a priori
• Il suffit de ``compléter'' les vecteurs d'itération de façon cohérente: I ® I

• S(I) <seq T(J)	Û
  	(I <seq J) ou
  	(I = J et S <text T)

8  Dépendances de données

• On veut mettre en parallèle certaines instructions: une partie de l'ordre séquentiel est à respecter absolument, une autre pas (permutation possible d'actions)
• On va définir un ordre partiel (Bernstein), ordre minimal à respecter pour produire un code sémantiquement équivalent à l'ordre initial
• En fait, l'ordre séquentiel va être une extension de l'ordre partiel de Bernstein
• Cet ordre partiel est défini à partir de 3 types de dépendances de données: flot, anti et sortie.

9  Flot, anti et sortie...

• Toujours dirigées par l'ordre séquentiel
• Dépendance de flot de S(I) vers T(J): si un emplacement mémoire commun est en écriture pour S(I) et en lecture pour T(J)
• Dépendance anti de S(I) vers T(J): si un emplacement mémoire commun est en lecture pour S(I) et en écriture pour T(J)
• Dépendance de sortie de S(I) vers T(J): si un emplacement mémoire commun est en écriture pour S(I) et en écriture pour T(J)

10  Exemple

for (i=1;i<=N;i++)
  for (j=1;j<=N;j++)
    a(i+j) = a(i+j-1)+1;

11  Dépendances

12  Calcul des dépendances

• Supposons que S(I) et T(J) accèdent au même tableau a (S en écriture, T en lecture)
• S(I): a(f(I))=... et T(J): ...=a(g(J));
• L'accès au tableau est commun si f(I)=g(J)
• Si f et g sont des fonctions affines à coefficients entier: peut se tester en temps polynomial

13  Calcul des dépendances

• Chercher une dépendance de flot par exemple revient à prouver en plus S(I) <_seq T(J)
• Encore une fois: en général résolution de systèmes d'égalités et d'inégalités affines
• Chercher les dépendances directes: plus compliqué (par programmation linéaire, problèmes d'optimisation dans les entiers)

14  Exemple

• f(I)=i+j et g(J)=i+j-1
• On cherche dépendance entre écriture S(i',j') et lecture S(i,j)
• f(I)=g(J) Û i'+j'=i+j-1
• S(i',j') <_seq S(i,j) Û ( (i'£ i-1) ou (i=i' et j'£ j-1) )

15  Exemple

• Dépendance de flot directe implique résoudre:

  max

  <seq

  {(i',j') | (i',j') <seq (i,j), i'+j'=i+j-1, 1 £ i,i',j,j' £ N }

• Solution:

  (i,j-1)	si j ³ 2
  (i-1,j)	si j=1

• Antidépendance directe de S(i,j) vers S(i',j') implique résoudre:

  min

  <seq

  {(i',j') | (i,j) <seq (i',j'), i'+j'=i+j-1, 1 £ i,i',j,j' £ N }

• Solution (pour j³ 3, i£ N-1):
  (i+1,j-2)

16  Approximation des dépendances

• Sommets: instances S_i(I), 1 £ i £ s et I Î D_Si
• Arcs: S(I) ® T(J) pour chaque dépendance

17  Quelques définitions

• Ensemble des paires de dépendances entre S et T:

  {(I,J) | S(I) ® T(J)}Í ZZ

  nS

  × ZZ

  nT

• Ensemble de distance de ces dépendances:

  {(J-I) | S(I) ® T(J) }Í ZZ

  nS,T

• Problème: on ne peut calculer le GDE à la compilation! (de toutes façons, est trop gros!)

18  Graphe de Dépendance Réduit

• Sommets: instructions S_i (1 £ i £ s)
• Arcs: e: S ® T si il existe au moins un arc S(I) ® T(J) dans le GDE
• Etiquette: w(e) décrivant un sous-ensemble D_e de ZZ^n_S,T

19  Quelques abstractions

• Une dépendance entre S(I) et T(J) est boucle indépendante si elle a lieu au cours d'une même itération des boucles englobant S et T
• Sinon elle est portée par la boucle...
• Etiquetage en conséquence, de e: S ® T du GDR:
  • l(e)=¥ si S(I)® T(J) avec J - I=0
  • l(e) Î [1,n_S,T] si S(I) ® T(J), et la première composante non nulle de J-I est la l(e)^ieme composante

20  Exemple

for (i=2;i<=N;i++) {
  S1: s(i) = 0;
  for (j=1;j<i-1;j++) 
    S2: s(i) = s(i)+a(j,i)*b(j);
  b(i) = b(i)-s(i);
}

21  GDRN

22  Vecteurs de direction

• lecture a(i+j-2)-écriture a(i+j): ensemble de distance {(1,-2)}
• écriture a(i+j)-lecture a(i+j-1): ensemble de distance {(1,0),(0,1)}
• écriture a(i+j)-écriture a(i+j): ensemble de distance {(1,-1)}

23  Vecteurs de direction

• on note z+ pour une composante si toutes les distances sur cette composante ont au moins la valeur z
• on note z- pour une composante si toutes les distances sur cette composante ont au plus la valeur z
• on note + à la place de 1+, - à la place de -1-
• on note * si la composante peut prendre n'importe quelle valeur
• on note z si la composante a toujours la valeur z

24  GDRV

25  Transformations de boucles

• Distribution de boucle
• Torsion de boucle
• Inversion de boucle
• Permutation de boucle
• etc.

26  Algorithmes de parallélisation de boucles

• Allen et Kennedy (basé sur le GDRN) : distribution de boucles
• Lamport - transformations unimodulaires (basé sur le GDRV) : torsion, inversion, permutation de boucles

27  Distribution de boucles

• Toute instance d'une instruction S peut être exécutée avant toute instance de T si on n'a jamais T(J) ® S(I) dans le GDE
• Plusieurs cas à considérer, pour le code:

  for (i=...) {
    S1;
    S2;
  }
  

28  Cas 1

for (i=...)
  S1;
for (i=...)
  S2;

29  Cas 2

for (i=...)
  S2;
for (i=...)
  S1;

30  Fusion de boucles

forall (i=1;i<=N;i++)
 D[i]=E[i]+F[i];
forall (j=1;j<=N;j++)
 E[j]=D[j]*F[j];

forall (i=1;i<=N;i++)
 {
  D[i]=E[i]+F[i];
  E[j]=D[j]*F[j];
 }

31  Composition de boucles

forall (j=1;j<=N;j++)
 forall (k=1;k<=N;k++)
  ...

forall (i=1;i<=N*N;i++)
 ...

32  Echange de boucles

for (i=2;i<=N;i++)
 for (j=2;j<=M;j++)
  A[i,j]=A[i,j-1]+1;

for (j=1;j<=M;j++)
 A[1:N,J]=A[1:N,j-1]+1;

33  Division de noeud

for (i=1;i<=N;i++)
 { A[i]=B[i]+C[i];
   D[i]=A[i-1]*A[i+1]; }

for (i=1;i<=N;i++)
 { A[i]=B[i]+C[i];
   temp[i]=A[i+1];
   D[i]=A[i-1]*temp[i]; }

34  Intérêt

forall (i=1;i<=N;i++)
 A[i]=B[i]+C[i];
forall (i=1;i<=N;i++)
 temp[i]=A[i+1];
forall (i=1;i<=N;i++)
 D[i]=A[i-1]*temp[i];

35  Réduction de boucle

for (i=3;i<=N;i++)
 { A[i]=B[i-2]-1;
   B[i]=A[i-3]*k; } 

for (j=3;j<=N;j=j+2)
 forall (i=j; i<=j+1; i++)
  { A[i]=B[i-2]-1;
    B[i]=A[i-3]*k; } 

36  Déroulement de boucle

for (i=1;i<=100;i++)
 A[i]=B[i+2]*C[i-1];

for (i=1;i<=99;i=i+2)
 {
  A[i]=B[i+2]*C[i-1];
  A[i+1]=B[i+3]*C[i];
 }

37  Rotation de boucle

for (i=2;i<=N-1;i++)
 for (j=2;j<=N-1;j++)
  A[i,j]=(A[i+1,j]+A[i-1,j]+A[i,j+1]+A[i,j-1])/4;

forall (i=2;i<=N-1;i++)
 for (j=i+2;j<=i+N-1;j++)
  A[i,j-1]=(A[i+1,j-i]+A[i-1,j-i]+A[i,j+1-i]+A[i,j-1-i])/4;

38  Exemple de parallélisation de code

39  Remontée...

40  Code séquentiel

x[n]=b[n]/U[n,n];
for (i=n-1;i>=1;i--)
{  
x[i]=0;
for (j=i+1;j<=n;j++)
     L: x[i]=x[i]+U[i,j]*x[j];
     x[i]=(b[i]-x[i])/U[i,i];
     }

41  Graphe de dépendances

42  Parallélisation

H': forall (i=1;i<=n-1;i++)
       x[i]=b[i];
T': x[n]=b[n]/U[n][n];
H:  for (t=1;t<=n-1;t++)
     forall (i=1;i<=n-t;i++)
      L: x[i]=x[i]-x[n-t+1]*U[i][n-t+1];
     T: x[n-t]=x[n-t]/U[n-t][n-t];

43  Allen et Kennedy: principe

• Remplacer certaines boucles for par des boucles forall
• Utiliser la distribution de boucles pour diminuer le nombre d'instructions dans les boucles, et donc réduire les dépendances

44  Algorithme

• Commencer avec k=1
• Supprimer dans le GDRN G toutes les arêtes de niveau inférieur à k
• Calculer les composantes fortement connexes (CFC) de G
• Pour tout CFC C dans l'ordre topologique:
  • Si C est réduit à une seule instruction S sans arête, alors générer des boucles parallèles dans toutes les dimensions restantes (i.e. niveaux k à n_S) et générer le code pour S
  • Sinon, l=l_min(C), et générer des boucles parallèles du niveau k au niveau l-1, et une boucle séquentielle pour le niveau l. Puis reboucler l'algorithme avec C et k=l+1

45  Exemple

for (i=1;i<=N;i++) 
  for (j=1;j<=N;i++) {
    S1: a(i+1,j+1) = a(i+1,j)+b(i,j+2);
    S2: b(i+1,j) = a(i+1,j-1)+b(i,j-1);
    S3: a(i,j+2) = b(i+1,j+1)-1;
  }

46  Exemple

• Flot S1 ® S1, variable a, distance (0,1),
• Flot S1 ® S2, variable a, distance (0,2),
• Flot S2 ® S1, variable b, distance (1,-2),
• Flot S2 ® S2, variable b, distance (1,1),

47  Exemple

• Anti S1 ® S3, variable a, distance (1,-2),
• Anti S2 ® S3, variable a, distance (1,-3),
• Anti S3 ® S2, variable b, distance (0,1),
• Sortie S1 ® S3, variable a, distance (1,-1).

48  Exemple

49  Algorithme

• Le GDRN est fortement connexe et a des dépendances de niveau 1
• La boucle sur i sera donc séquentielle
• On enlève maintenant les dépendances de niveau 1...

50  GDRN modifié

51  Parallélisation finale

for (i=1;i<=N;i++) {
  for (j=1;j<=N;j++) 
    S1: a(i+1,j+1) = a(i+1,j)+b(i,j+2);
  forall (j=1;j<=N;j++)
    S3: a(i,j+2) = b(i+1,j+1)-1;
  forall (j=1;j<=N;j++)
    S2: b(i+1,j) = a(i+1,j-1)+b(i,j-1);
}

52  Quelques perspectives

• Modèles sémantiques du parallélisme
• Autres langages ou paradigmes:
  • Linda, Facile, CHOCS, Erlang, CML, OCCAM, PVM/MPI etc.
  • algèbres de processus: CCS, CSP, p-calcul, Join-calcul etc.
• Analyse statique par interprétation abstraite
• Algorithmes distribués... (voir N. Lynch ``Distributed Algorithms'')
• Systèmes distribués tolérants aux pannes - Systèmes auto-stabilisants
• Projets GRID

53  Modèles sémantiques

• Systèmes de transitions
• Structures d'événements
• Réseaux de Petri
• etc.

54  Motivations

• Associer à un programme (ici parallèle) un modèle mathématique
• Manipulable, et dont on puisse tirer (par algorithmes) des propriétés d'intérêt
• Exemple: points morts, états atteignables, chemins d'exécutions, valeurs que peuvent prendre les variables etc.

55  Exemple: systèmes de transitions

56  Exemple d'exécution possible

57  Exemple

58  Chemins

• Les 5 chemins les plus en haut à gauche sont ``équivalents'' à T<sub>2</sub> puis T<sub>1</sub> : ils calculent b=5 (2*2+1)
• Les 5 chemins les plus en bas à droite sont ``équivalents'' à T₁ puis T₂: ils calculent b=6 ((2+1)*2)
• Les 6 chemins près de la diagonale sont équivalents: ils ne terminent pas

59  En général, pénible...

60  Autres langages

• PVM/MPI: voir par exemple: http://www-unix.mcs.anl.gov/mpi/
• Algèbres de processus: exemple CCS
• Join calcul: voir par exemple: http://join.inria.fr/
• Paradigme Linda: ``tuple space'' et récupération/accès par pattern matching
• cf. également www.cs.yale.edu/Linda/linda.html

61  CCS

• plus de calcul, fonctions etc. mais flot de contrôle (récursion, suite d'instructions)
• choose ¾® + (choix non-deterministe),
• send(a,x) ¾® a(x) (envoi),
• val x=accept(a) ¾® a(x)

62  CCS pur

63  Exemples

• Composition parallèle et hiding :
  let c=channel() in spawn(fn () Þ accept(c)); send(c,0) end
  devient (c.nil| c)\c
• Choix :
  select [transmit(a,1); wrap(accept b, fn x Þ send(b,x))]
  devient a+(b.b)
• Récursion :
  let fun entiers n = send(c,n); entiers(n+1) in entiers(0) end
  devient rec X.c.X

64  Sémantique opérationnelle

65  Sémantique de CCS

66  Notion d'observation

67  Mais...

68  Exemple

69  Exemple

70  Equations algébriques

• P+Q ~ Q+P
• P+(Q+R) ~ (P+Q)+R
• P+P ~ P
• P+nil ~ P
• P | Q ~ Q | P
• P | (Q | R) ~ (P | Q) | R
• P | nil ~ P
• P \L ~ P si L(P) Ç (L È L) =
• P \K \L ~ P \(K È L)
• P[f]\L ~ P\f^-1(L)[f]
• (P | Q) \L ~ (P \L) | (Q \L)
• P[Id] ~ P
• P[f] ~ P[f'] si f_L(P)=f'_L(P)
• P[f][f'] ~ P[f' ° f]
• (P | Q)[f] ~ P[f] | Q[f] si f_{L È L} est bijective où L=L(P) È L(Q)

71  Suite

• a.P₁ ~ a.P₂
• P₁+Q ~ P₂+Q
• P₁ | Q ~ P₂ | Q
• P₁ \L ~ P₂ \L
• P₁[f] ~ P₂[f]

72  Spécification : bit alterné

73  Spécification, suite

74  Vérification

75  Vérification

76  Analyse statique

• Vous avez vu un premier exemple avec la logique de Hoare en IF
• Voir maintenant http://www.di.ens.fr/~cousot
• Par exemple, à partir d'une sémantique par systèmes de transitions, ``abstraire'' les valeurs que peuvent prendre les variables par des intervalles d'entiers (abstraction ici de la logique de Hoare)
• Sujet très actif aussi bien dans la recherche qu'industriellement (cf. Polyspace Technologies par exemple)

77  Systèmes distribués tolérants aux pannes

78  Résultat

79  Systèmes auto-stabilisants

• Cas particulier de protocoles ``tolérants aux pannes''
• Communauté importante, longtemps après le papier important (1974) sur le sujet, de E. W. Dijkstra
• Chaque processus doit arriver en un temps fini à ``réparer'' une mauvaise valeur fournie à un moment donné par un processus
• Voir par exemple: http://www.cs.uiowa.edu/ftp/selfstab/bibliography/

80  Projets GRID

• Un sujet à la mode!
• Systèmes distribués ``coopératifs'' à l'échelle de la planète... (cluster de stations sur internet par exemple)
• Au menu: algorithmique hétérogène, tolérance aux pannes etc.
• Voir par exemple http://www.gridcomputing.com/

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