Sources du parall lisme
Dr. Khedija AROUR
INSAT
GL4
1
Plan
Motivation
Parall lisme de contr le
Parall lisme de donn es
Parall lisme de flux
2
Sources du parall lisme
Source du parall lisme
Parall lisme
de Contr le
de Donn es de Flux
3
Parall lisme de contr le
4
Parall lisme du contr le
Lexploitation du parall lisme de Contr le vient de la
constatation naturelle qu'une application est compos e
dactions que l'on peut faire en m me temps. Les
actions, appel es aussi T ches, Processus,
Instructions etc., peuvent tre ex cut es de mani re
plus ou moins ind pendante sur des ressources de
calcul appel es aussi Processeurs l mentaires (ou
PEs).
Dans le cas o toutes les actions sont ind pendantes,
il suffit alors dassocier une ressource de calcul
chacune dentre-elles pour obtenir un gain en temps
dex cution qui est lin aire
5
Mise en route
Algorithme s quentiel : A
Parall lisation de A
D composition en t ches
Analyse de d pendances
Ordonnancement de t ches
6
T che
Une t che est une unit de traitement
caract ris e par
le temps dex cution (dur e) = temps de calcul+
temps de communication + autre
7
T che : granularit
Plusieurs d compositions sont possibles pour le
m me algorithme
granularit = taille des t ches
Le choix de la meilleure d composition est un
probl me difficile
le nombre de processeurs
le rapport communication VS calcul
les acc s m moires
8
Grain de parall lisme
Comment diviser un traitement en sous-t ches ?
Quelle taille doivent avoir ces sous-t ches. La
taille des t ches l mentaires sur lesquelles vont
porter la parall lisation ?
La taille des t ches l mentaires sur lesquelles
vont porter la parall lisation d termine le grain de
parall lisme. En g n ral on distingue entre grain
fin (fine grain) et grain grossier (coarsed grain).
9
Exemple
Calcul du produit matriciel C=AxB
Cas1: une t che= une op ration l mentaire
(produit scalaire/additaion scalaire) : c(i,j)=c(i,j)+A
(i,k)xB(k,j) Grain fin
Cas2: une t che calcule un l ment de C Grain
moyen
Cas3 : Une t che calcule une ligne de C Grain
grossier
10
Degr de parall lisme
Le grain de parall lisme a g n ralement une
grande influence sur un autre param tre
caract risant les programmes parall les: le
degr de parall lisme.
Le degr et profil du parall lisme
Le degr de parall lisme est la mesure du nombre
de sous-t ches ex cut es simultan ment dans un
programme parall le.
11
Profil de parall lisme
profil du parall lisme
L volution du degr de parall lisme au cours de
lex cution est appel le profil du parall lisme. Le
degr maximal est une borne sup rieure sur le
nombre de processeurs quil faut allouer au
programme.
12
Exemple illustratif
Exemple 1 :
Soit a et b deux vecteurs donn s d'indices 1..n, on
calcule le vecteur c d'indices 0..n et le vecteur d
d'indices 1..n de la fa on suivante:
d(i) = a(i) - b(i)
SI i=0 ALORS c(i) = 0
SINON c(i) = c(i-1) + a(i) + b(i)
13
Exemple illustratif...
BEGIN
c(0):=0;
FOR i IN 1..n LOOP
d(i) := a(i) - b(i);
c(i) := c(i-1) + a(i) + b(i);
END FOR;
END exemple
BEGIN
c(0):=0;
FOR i IN 1..n LOOP
PARBEGIN
d(i) := a(i) - b(i);
t(i) := a(i) + b(i);
END PAR;
c(i) := c(i-1) + t(i);
END FOR;
END exemple
14
Parall lisme de Contr le :Exemple
illustratif&
Le niveau de parall lisation est linstruction, on
peut donc parler de grain fin,
Le degr maximal de parall lisme
Le profil du parall lisme est donn
d1
t1
c1
c0
d2
t2
15
D pendances
Deux t ches du m me algorithme sont soit li es
par une relation de pr c dence soit
ind pendantes
Deux t ches Ti et Tk sont cons cutives sil
nexiste aucune autre t che Tj / Ti < Tj < Tk ou
Tk < Tj < Ti
16
D pendances...
d composition en n t ches
A= {T1,T2,...,Tn,<}
< : Relation de d pendance dordre partiel Ti < Tj
Un syst me de t ches A= {T1,T2,...,Tn,<} est un
syst mes de pr c dence si pour tout couple (Ti,
Tk), une et une seule des 3 conditions est v rifi e
Ti < Tk
Tk< Ti
Ti et Tk sont ind pendantes
Advertisement
17
Analyse de d pendances
d composition en n t ches
A= {T1,T2,...,Tn,<}
< : Relation de d pendance dordre partiel Ti <
Tj
Ti=
un ensemble dentr es : Ri
un ensemble de sorties : Mi
dur e dex cution : di
18
Graphe de pr c dence
Le graphe de pr c dence G associ au
syst me de pr c dence A est :
Lensemble de sommets de G sont les t ches de A
Ti et Tj sont reli es par un arc Ssi Ti et Tj sont
cons cutives et ordonn es (par la relation dordre)
19
Exemple
Soit un algorithme compos de 8 t ches
T1,...,T8
T1 < T3, T1< T4, T1 < T5, T1 < T6, T1 < T7, T1 < T8
T2 < T3, T2 < T4, T2 < T5, T2 < T6, T2 < T7 T2 <
T8
T3 < T7, T3 < T8
T4 < T6, T4 < T7, T4 < T8
T5 < T7
T6 < T8
Graphe
20
Exemple...
Rechercher les t ches ind pendantes
D duire le syst me de pr c dence
Rechercher les t ches cons cutives
Graphe de t ches
Niveau 1 : T1, T2
Niveau 2 : T3, T4, T5
Niveau 3: T6, T7 (AU PLUS T T)
Niveau 4 : T8, T7 (AU PLUS TARD)
21
Exemple...
T1
T2
T3
T4
T6
T5
T7
T8
T7
22
D pendances
D pendance de contr le de s quence : correspond au
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 lassociation des ressources
de calcul aux actions
Lexploitation 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 lensemble Ri des valeurs lues
g n rer lensemble Mi des valeurs modifi es
Il y a une d pendance de Ti vers Tj si
Ti est ex cut e avant Tj
si lun des trois ensembles
Mj est non vide
, Ri ) Mj ou Mi )
26
Mi ) RjRemarques sur le graphe de
pr c dence
Le temps dun chemin du graphe de pr c dence
est la somme des temps dex cution des t ches
qui le composent
Le plus long chemin du graphe de pr c dence est
celui dont le temps dex 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 : lensemble 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 quune t che est pr te, on lex 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 sex 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
lensemble 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
Advertisement
MakeSpan
(Cmax)
32
Ordonnancement
Lordonnancement consiste
Choisir une ressources
Choisir une date dex cution pour chaque t che
La valeur de lordonnancement est la valeur de
la fonction objectif choisie
temps dex cution (makespan) : Cmax
temps dex cution optimal Cmax*
33
Parall lisme du contr le&
Exemple :
Soit lexpression suivante (a+4)*(b+c)-(d-1)
-
-
d 1
+
*
+
a
4
b
c
Lanalyse 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 dex cution parall le ? Gain ?
Peut-on faire mieux ? Diagramme de gantt ?
35
Parall lisme du contr le:Graphe de
d pendance&
Critiques :
Si TS nest 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
dagir sur TS car cest une donn e technique de la machine
sous-jacente. On peut par contre essayer dagir 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
Lexploitation 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 lindice 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
Advertisement
provoqu par les acc s la m moire va donc faire chuter les
performances.
Lacc 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 nutiliser que N
processeurs et ne parall liser effectivement que la premi re
boucle. Le temps serait alors de lordre 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 oat;
...
PROCEDURE Produit_Mat
(A,B:in Vecteur_N; C:out
oat) 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 d N chaque processeur va devoir
calculer au moins une ligne compl te de C et il
devra donc disposer dune copie locale de toute
la matrice B
48
Exemple...
calculer un l ment C(i,j), un processeur a
besoin dune ligne de A et dune colonne de B
chaque processeur calcule un pav de 1x1 de la
matrice C
Si lon 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 lencha 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, cest 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 cest 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((pm - 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 lappelant de la proc dure
La programmation sur une machine MIMD
implique principalement une distribution
Advertisement
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 lun 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 sagit 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 nest 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(3i-1) = 2b(i)
S2: c(i) = d(i)a(6i+1)
End Do
DoALL i = 1,n
S1: a(3i-1) = 2b(i)
S2: c(i) = d(i)a(6i+1)
End DoALL
3i-6j=2
Impossible
63
Parall lisme de flux
Lexploitation 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 dutilisation du parall lisme de
flux est lorsque lon 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 larriv e continue
des mesures provenant dun dispositif de saisie des
donn es
&
67