Sources du parallélisme

séquencement dans un algorithme classique

 Dépendance de contrôle de communication : lorsqu'une

action envoie des informations à une autre action

B(i) = 1.0 (S2)

 IF (A(i) = 0) (S1)  THEN   ELSE   ENDIF

B(i) = A(i) (S3)

23

Dépendances...

– Les deux cas de dépendance imposent des

restrictions sévères sur l’association des ressources de calcul aux actions

– L’exploitation du parallélisme de Contrôle consiste à

gérer les dépendances entre les actions d'une application pour obtenir une allocation des ressources de calcul aussi optimale que possible 

24

Dépendances...

 Mi ∩ Rj: producteur-consommateur :

dépendance vraie (RAW) : a=... ; ... =a

 Ri ∩ Mj : anti-dépendance (WAR) : ...=a ; a =...

 Mi ∩ Mj : dépendance de sortie (WAW) : a=...; a=...

25

Construction du graphe de dépendances

 Condition de BERSTEIN  Pour chaque tâche Ti,

– générer l’ensemble Ri des valeurs lues – générer l’ensemble Mi des valeurs modifiées

 Il y a une dépendance de Ti vers Tj si

– Ti est exécutée avant Tj – si l’un des trois ensembles

Mj est non vide

, Ri ∩ Mj ou Mi ∩

26

Mi ∩ RjRemarques sur le graphe de précédence  Le temps d’un chemin du graphe de précédence est la somme des temps d’exécution des tâches qui le composent

 Le plus long chemin du graphe de précédence est celui dont le temps d’exécution est le plus grand : Chemin Critique

 Chemin critique : est la plus grande chaîne dans

le graphe de précédence qui relie une tâche initiale à une tâche finale

27

Remarques sur le graphe de précédence...

 La hauteur H(G) du graphe est le nombre de

tâches du chemin critique

 Décomposition en niveaux : l’ensemble D(G) = {N1,N2,...,N(HG)} qui constitue un ensemble de niveaux des sommets vérifiant les conditions suivantes: – niveau 1: tâches sans prédécesseurs – niveau k : tâches dont les prédécesseurs sont de niveaux inférieurs et dont les successeurs sont de niveaux supérieurs

– niveau H(G) : tâches sans successeurs

28

Remarques sur le graphe de précédence...

 Un même graphe peut admettre plusieurs

décompositions en niveaux

 Décomposition par prédécesseur Dp(G) la

décomposition en niveaux/ – niveau 1: toutes les tâches sans prédécesseurs – k=2, H(G), est constitué des tâches dont tous les

prédécesseurs sont dans des niveaux inférieurs et ayant au moins un prédécesseur dans le niveau k-1

 dès qu’une tâche est prête, on l’exécute 29

temps optimal et p optimal

 Avec un nombre illimité de processeurs, le

temps optimal (topt) est égal au temps de calcul du plus long chemin du graphe de tâches (sans communication ou autre)

 Le nombre minimal de processeurs Popt

permettant de réaliser un algorithme s’exécutant en temps topt est égal à la largeur L(G) du graphe de tâches

30

Ordonnancement

 Étant donné

– le graphe de précédence – l’ensemble de ressources

 Affecter les tâches aux processeurs disponibles

en respectant les contraintes du graphe

31

Ordonnancement...

Processeurs

T5

T7

T2

T4

T6

T1

T3

T8

Temps

MakeSpan (Cmax)

32

Ordonnancement

 L’ordonnancement consiste à

– Choisir une ressources – Choisir une date d’exécution pour chaque tâche

 La valeur de l’ordonnancement est la valeur de

la fonction objectif choisie – temps d’exécution (makespan) : Cmax – temps d’exécution optimal Cmax*

33

Parallélisme du contrôle…

– Exemple :

 Soit l’expression suivante (a+4)*(b+c)-(d-1)

-

-

d 1

+

*

+

a

4

b

c

L’analyse de cet arbre : Faire en parallèle a+4 b+c d-1 Puis calculer (a+4)*(b+c)-(d-1)

3 unités de temps

34

Parallélisme du contrôle:Graphe de dépendance…

 Le nombre de processeurs ?

 Diagramme de gantt

 Le temps d’exécution parallèle ? Gain ?

 Peut-on faire mieux ? Diagramme de gantt ?

35

Parallélisme du contrôle:Graphe de dépendance…

 Critiques :

– Si TS n’est pas négligeable par rapport à TU alors le

T//>Tseq .

– Pour éviter que cette situation se produise il faut

essayer de maintenir le rapport TS/TU le plus bas possible.

 diminuer TS soit augmenter TU. En général il est difficile

d’agir sur TS car c’est une donnée technique de la machine sous-jacente. On peut par contre essayer d’agir sur TU36

Parallélisme du contrôle: Exemple

 Supposons un programme séquentiel peut être divisé en 7 tâches prenant respectivement t1, t2,…, t7

T4

T1

T2

T3

T5

T6

T6 T7

T7

T1 T2 T3 T4 T5



P1

2

1

2 1

3

1 1

37

Parallélisme du contrôle: Exemple…

P2 T1 T4

P1

T2

T6

T3

T5

T7

P2 T1

T3

T4 T2

P1

T5

T6

T7

T1

T5

P2

T4

P1

T3

T2

T6 T7

38

Parallélisme de Contrôle et parallélisation efficace

 Pour obtenir une parallélisation efficace il est

donc important de bien placer les tâches sur les processeurs

 Ce placement dépend :

– du nombre de processeurs, – du graphe dépendance, – de la durée et de la taille des tâches, – des communications entre ces tâche.

39

Parallélisme de données

40

Parallélisme de données

– L’exploitation du parallélisme de Données vient de la

constatation naturelle que certaines applications sont composées de données identiques (tableaux de données par exemple) sur lesquelles on doit répéter une même action.

– Les ressources de calcul sont associées aux

données.

– Souvent, les données identiques sont en très grand

41

Parallélisme de données…

42

!"#$% &'()* &$+,-$.(,$#)

Distribution de données

! /0#1234!510$134/0#126!510$1

!"#$% &'()* &$+,-$.(,$#)

! /0#1234!510$134/0#126!510$1

 Distribution cyclique

 Distribution par bloc

 Bloc cyclique

!"#$% &'()* &$+,-$.(,$#)

! /0#1234!510$134/0#126!510$1

43

Exemple





-- Produit matriciel pour machine à mémoire partagée --

...

 N : CONSTANT integer := 1024;

 TYPE Matrice_NN IS ARRAY(1..N,1..N) OF float;



...

 PROCEDURE Produit_Mat(A,B:in Matrice_NN; C:out Matrice_NN) IS

 BEGIN

 FORALL i IN 1..N LOOP // exécution parallèle





//toutes les itérations de 1 à N sont indépendantes et peuvent

//être exécutées en parallèle sur l’indice i.

 FORALL j IN 1..N LOOP

 C(i,j):=0.0;





FOR k IN 1..N LOOP

C(i,j):= C(i,j) + A(i,k)*B(k,j);

44

Exemple...

Temps théorique : le calcul de C(i,j) suppose trois accès à la mémoire (C(i,j), A(i,k) et B(k,j)). Le goulet d’étranglement provoqué par les accès à la mémoire va donc faire chuter les performances. L’accès simultané de plusieurs processeurs à la mémoire centrale est le problème majeur rencontré par les concepteurs de machines multiprocesseurs à mémoire partagée (étranglement de la mémoire)

Une autre version possible qui consisterait à n’utiliser que N processeurs et à ne paralléliser effectivement que la première boucle. Le temps serait alors de l’ordre de N^2

45

Exemple...

 Si on dispose de N^2 processeurs, écrire un

algorithme adéquat sur une machine à mémoire distribuée ?

46

Exemple...

PROCESSEUR IS p; ... N : CONSTANT integer := 1024; TYPE Vecteur_N IS ARRAY (1..N) OF float; ...

PROCEDURE Produit_Mat (A,B:in Vecteur_N; C:out float) IS BEGIN C:=0.0; FOR k IN 1..N LOOP C := C + A(k)*B(k); END FOR; ....... END Produit_Mat;

47

Exemple...

 Idée 1 : calculer par chaque processeur

plusieurs éléments de C, par exemple C(1..m,j), m étant un paramètre dépendant du nombre de processeurs.

 Avec cette méthode si le nombre de

processeurs ≤ N chaque processeur va devoir calculer au moins une ligne complète de C et il devra donc disposer d’une copie locale de toute la matrice B

48

Exemple...

 calculer un élément C(i,j), un processeur a

besoin d’une ligne de A et d’une colonne de B  chaque processeur calcule un pavé de 1x1 de la

matrice C

 Si l’on ne dispose pas de N^2 processeurs mais

seulement de P< N^2 processeurs, chaque processeur peut calculer un pavé mxm de la matrice C avec m = ?

49

Exemple...

 m ?  Problème



50

Exemple...

 problème de la distribution préalable des matrices A et B lors de l’enchaînement de plusieurs calculs

 Solution : Avoir une seule copie des matrices A et B avec une répartition qui minimiserait le volume de communications durant le calcul

 Répartir les matrices A et B de la même façon

que la matrice C, c’est à dire par pavés de mxm avec m=N/(P1/2)

 Volume de communication?

51

Exemple...

 Chaque processeur calcule un pavé de C et possède les pavés correspondant de A et B

 Ainsi chaque processeur doit aller chercher sur les autres processeurs les parties manquantes des lignes de A et des colonnes de B.

 Le volume total de communications est le

suivant:



52

Exemple...

 2(mN-m^2) = 2(N/(√ P )N- Nm^2/P) = 2 N^2((√

P )-1)/P

2(N-1)

 Lorsque P vaut N^2, on obtient:   En effet ce qui est important c’est le rapport entre le volume des communications et le volume de calculs

 Volume de calculs par processeur?

53

Exemple  Dans ce cas le volume de calculs pour chaque

élément C(i,j) est de:

 (N-1) additions + N multiplications = 2N-1

opérations

 Chaque processeur calcule m^2 = N^2/P

éléments de la matrice C

 le volume de calculs pour un processeur est de:  (2N-1) N^2/P

54

Exemple...



-- Produit matriciel pour machine à mémoire distribuée (2) --

 PROCESSEUR IS p;



...

 MaxP : CONSTANT integer := 256;

 N : CONSTANT integer := 1024;

 m : CONSTANT integer := N DIV (Sqrt

(MaxP));

 TYPE Pave_mN IS ARRAY(1..m,1..N) OF

float;

 TYPE Pave_Nm IS ARRAY(1..N,1..m) OF

float;

 TYPE Pave_mm IS ARRAY(1..m,1..m) OF

float;



...

 PROCEDURE Produit_Mat(A:in Pave_mN;

B:in Pave_Nm; C:out Pave_mm) IS













i1 : CONSTANT integer := m*((p*m - 1) DIV N) + 1;

j1 : CONSTANT integer := ((p-1)*m + 1) MOD N;

i2 : CONSTANT integer := j1 + m ;

j2 : CONSTANT integer := i1 + m ;

-- Je possède mes bloc: --

-- A(i1..i2-1,j1..j2-1) et B(i1..i2-1,j1..j2-1) --

55

Exemple...

 BEGIN

 GET(A(i1:i2-1,1:j1-1));

 GET(A(i1:i2-1,j2:N));

 GET(B(1:i1-1,j1:j2-1));

 GET(B(i2:N,j1:j2-1));

 FOR i IN 1..m LOOP

 FOR j IN 1..m LOOP

 C(i,j):=0.0;

 FOR k IN 1..N LOOP

 C(i,j):=C(i,j) + A(i,k)*B(k,j);

 END FOR;

 END FOR;

 END FOR;

 END Produit_Mat;



On recopie localement les m lignes de A et les m colonnes de B et l’appelant de la procédure

 La programmation sur une machine MIMD implique principalement une distribution judicieuse des données afin de :





minimiser le rapport communications/ calculs

de ne pas dépasser la mémoire disponible sur chaque processeurs. Cette “répartition judicieuse” doit la plupart du temps être faite “à la main”.

56

Calcul des dépendances: cas des boucles

 Paralléliser une boucle

analyse des dépendances qui existent

entre les différentes itérations de la boucle

 Deux itérations sont dépendantes si elles accèdent à une même cellule

mémoire dont l’un au moins des deux accès soit en écriture.

Pas de dépendance

Do I=1,N A(I)=B(I)*C(I) X(I)=A(I)+F(I+1)

DOALL I=1,N A(I)=B(I)*C(I) X(I)=A(I)+F(I+1)

Do I=1,N A(I)=A(I-1)+c

dépendance de type S(I) δ S(I+1) : Boucle

séquentielle

57

Calcul des dépendances: cas des boucles

 Paralléliser une boucle :

– Analyse des dépendances – Restructuration du programme initial

 Il s’agit d’étudier pour une boucle données les liens entre les itérations

f(I)-g(I)=0

Do I=1,N A(f(I))=… …=A(g(I))

∃ (i,j) ∈[1,N]x [1,N] / f(i)=g(i) avec i≠j

58

Techniques de parallélisation de boucles...

 Transformations standards

– Normalisation des boucles

Do I=V1,VN Step p T(I)

Do I1=1,V T(I1)

– Propagation des constantes

V=1000 X=12 Do I=1,V T(I)=T(X)+B(I)

V=1000 X=12 Do I=1,1000 T(I)=Cte+B(I)

59

Techniques de parallélisation de boucles...

 Techniques de restructuration – Permutation des boucles

Do I=1,N Do j=1,N S: X(I,J)= X(I-1,J-1)*X(I,J-1)

Do j=1,N DoALL i=1,N X(I,J)= X(I-1,J-1)*X(I,J-1)

 La boucle interne n’est pas parallélisable : dépendance

indique une relation entre des itérations : il suffit de permuter les deux boucles : fixer j et exécuter toutes les itérations de i en parallèle

60

Techniques de parallélisation de boucles...

 Techniques de restructuration – Distribution des boucles

Do i = 1,n S1: a(i) = 2*b(i) S2: c(i) = d(i)*a(i+1) End Do

–

S2(I) δ S1 (I+1)

Doall i = 1,n c(i) = d(i)*a(i+1) End Doall Doall i = 1,n a(i) = 2*b(i) End Doall

61

Techniques de parallélisation de boucles...

 Techniques de restructuration – Distribution des boucles…

Do I=1,N S1: X(I)= A(I)*C

S2: Y(I)=X(I-4)

DoALL i=1,N S1 DoALL i=1,N S2

–

–

S1(I) δ S2 (I+4) S2 δ S1 (I+4) (S2 consomme une case mémoire qui

va être modifiée par S1 après 4 itérations)

62

Techniques de parallélisation de boucles...

 Techniques de restructuration – Distribution des boucles…

Do i = 1,n S1: a(3*i-1) = 2*b(i) S2: c(i) = d(i)*a(6*i+1) End Do

DoALL i = 1,n S1: a(3*i-1) = 2*b(i) S2: c(i) = d(i)*a(6*i+1) End DoALL

–

3i-6j=2

Impossible

63

Parallélisme de flux

 L’exploitation du parallélisme de Flux vient de

la constatation que certaines applications fonctionnent selon le mode du travail à la chaîne :

– on dispose d'un Flux de données, généralement

similaires, sur lesquelles on doit effectuer une suite d'opérations en cascade

 Les ressources de calcul sont associées aux

64

Parallélisme de flux…

65

Parallélisme de flux…

 Le cas typique d’utilisation du parallélisme de

flux est lorsque l’on doit appliquer à des données une fonction F qui peut se décomposer en plusieurs fonctions:



F(x) = F1(F2(F3(...Fp(x)..)))

 Dans ce cas le calcul peut être divisé en P

étages de la façon suivante:

66

Parallélisme de flux…

Parallélisme de flux…

 Dans les systèmes temps réel de traitement de

données (traitement de signal) – Le flux de données est ici fourni par l’arrivée continue des mesures provenant d’un dispositif de saisie des données

 …

67