2.

Algorithmique parallèle

Introduction au parallélisme 1

Plan

1. Le modèle graphe de tâches

1. Défini9on
2. Exemples élémentaires
2. Applica9ons et algorithmique
1. Primi9ves et fonc9ons génériques
2. Applica9ons simples
3. Applica9ons difficiles
3. Scheduling
1. Sta9que
2. Dynamique

Introduction au parallélisme 2

Un Modèle générique du parallélisme: le DAG

• Directed Acyclic Graph

• Nœud: une tâche
– instruc9on, fonc9on,
programme
– Implémentée par
processus, thread
• Arête: séquen9alisa9on
• Donc acyclique
• Nœuds dis9ngués
début/fin

Introduction au parallélisme 3

1
 Un Modèle générique du parallélisme: le DAG

• Un DAG définit un ordre T1 T2

par9el
– T1 << T2 s’il existe un chemin
de T1 vers T2 T3

– Ordre total : programme

séquen9el T1 // T2
– Ordre par9el : programme T3
parallélisable

Introduction au parallélisme 4

Un Modèle générique du parallélisme: le DAG

• Directed Acyclic Graph

• La réalisa9on du
parallélisme est vue
uniquement comme un
problème
d’ordonnancement

Introduction au parallélisme 5

Un Modèle générique du parallélisme: le DAG

• T∞ est la longueur pondérée

du chemin cri9que (span,
profondeur). C’est la borne
inférieure du temps de calcul
• T1 la charge, est la somme des
temps d’exécu9on de tous les
nœuds – exécu9on
séquen9elle. C’est la borne
supérieure du temps de calcul.
• Indice de Parallélisme:
T1 /T∞
Quan9té moyenne de travail
par étape le long du chemin
cri9que

Introduction au parallélisme 6

2
 CILK

Les exemples de cette partie seront donnés en CILK

h_p://supertech.csail.mit.edu/cilk/
• Langage adapté à • Nous n’u9liserons que
l’algorithmique parallèle les construc9ons
récursive élémentaires, mais il y
• Exécu9f en a beaucoup d’autres.
• Développé au MIT puis
industrialisé en CILK++

Introduction au parallélisme 7

Basic Cilk Keywords

Identifies a function as a
Cilk procedure, capable of
cilk int fib (int n) { being spawned in parallel.
if (n<2) return (n);
else {
int x,y;
x = spawn fib(n-1);
y = spawn fib(n-2);
sync;
return (x+y); The named child Cilk
} procedure can execute
} in parallel with the
parent caller.

Control cannot pass this point

until all spawned children have
returned.

© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 8

Dynamic Multithreading
cilk int fib (int n) {
if (n<2) return (n); Example: fib(4)
else {
int x,y;
x = spawn fib(n-1);
y = spawn fib(n-2); 4
sync;
return (x+y);
} 3 2
}

2 1 1 0
“Processor
oblivious”

1 0 The computation dag unfolds

dynamically.
© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 9

3
 Multithreaded Computation
initial final
thread thread
continue
edge return edge
spawn edge

• The dag G = (V, E) represents a parallel instruction stream.

• Each vertex v ∈ V represents a (Cilk) thread: a maximal
sequence of instructions not containing parallel control
(spawn, sync, return).
• Every edge e ∈ E is either a spawn edge, a return edge, or
a continue edge.
© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 10

Anatomie d’une applicaDon simplissime:

addiDonner deux vecteurs
Séquentiel
void vadd (double *X, double *Y, double *Z,int n){
int i; for (i=0; i<n; i++)
Z[i]= X[i]+Y[i];}

Stratégie de parallélisation:
1. convertir la boucle en récursion
void vadd (double *X, double *Y, double *Z,int n) {
if (n <= B) {
int i; for (i=0; i<n; i++)
Z[i]= X[i]+Y[i];}
else {
vadd(X, Y ,Z, n/2);
vadd(X+n/2, Y+n/2 ,Z+n/2, n-n/2);}
}

Introduction au parallélisme 11

Anatomie d’une applicaDon simplissime:

addiDonner deux vecteurs
Séquentiel
void vadd (double *X, double *Y, double *Z,int n){
int i; for (i=0; i<n; i++)
Z[i]= X[i]+Y[i];}

Stratégie de parallélisation:
2. expliciter le parallélisme
cilk vadd (double *X, double *Y, double *Z,int n) {
if (n <= B) {
int i; for (i=0; i<n; i++)
Z[i]= X[i]+Y[i];}
else {
spawn vadd(X, Y ,Z, n/2);
spawn vadd(X+n/2, Y+n/2 ,Z+n/2, n-n/2);
sync;}
}

Introduction au parallélisme 12

4
 ParallélisaDon récursive
cilk vadd (double *X, double *Y, double *Z,int n) {
if (n <= B) {
int i; for (i=0; i<n; i++)
Z[i]= X[i]+Y[i];}
else {
spawn vadd(X, Y ,Z, n/2);
spawn vadd(X+n/2, Y+n/2 ,Z+n/2, n-n/2);
sync;}
}

July 13, 2006 13

ParallélisaDon récursive

T(1) = Θ(n)
T∞ = Θ(lg(n))
T1 = Θ( n )
T∞ lg(n)

BASE
July 13, 2006 14

Avantages

Stratégie de parallélisa9on:
1. Conver9r la boucle en récursion
2. Expliciter le parallélisme
• C’est une stratégie Divide & Conquer qui
favorise la localité ET la répar99on de charge
• La performance ne dépend pas de B au
premier ordre
• Mais synchronisa9ons inu9les
Introduction au parallélisme 15

5
 GesDon explicite des tâches
cilk void vadd1 (double *X, double *Y, double *Z){
int i; for (i=0; i<B; i++)
Z[i]= X[i]+Y[i];}
}
cilk void vadd (double *X, double *Y, double *Z){
int j; for(j=0; j<N; j+=B) {
spawn vadd1(X+j, Y+j, Z+j);}
sync;
}
Aussi à la PVM, threads
… T∞ = B + N/B
T1 = N
… Conclusion ?
Réaliste : l’addi9on et le spawn sont au mieux du même ordre

Une autre vision du même algorithme

void vadd1 (double *X, double *Y, double *Z){

int i; for (i=0; i<B; i++)
Z[i]= X[i]+Y[i];}
}
void vadd (double *X, double *Y, double *Z){
int j; parfor (j=0; j<N; j+=B) {
vadd1(X+j, Y+j, Z+j);}
• A la OpenMP, …
T∞ = B
T1 = N
B O 1 2 … P-1 T1/T∞ = N/B
Conclusion ?
July 13, 2006 17

Conclusion sur l’exemple simplissime

• L’approche Divide & Conquer est la plus robuste

• Le modèle par graphe de tâches dépend de
finesse de la représenta9on des tâches
– Granularité: degré de repliement du parallélisme
maximal.
– Réalisme: descrip9on des ac9ons de ges9on
• Le modèle par graphe de tâches représente assez
naturellement la programma9on en EAU, mais
pas en EAM

Introduction au parallélisme 18

6
 RelaxaDon
ij 0 k+1
• Calculer en chaque 0
point la moyenne des 4
voisins
• Tant que la différence
entre le tableau actuel k+1

et le précédent n’est
pas négligeable

Stencil 5 points

19 Introduction au parallélisme

La relaxaDon : code séquenDel

ij 0 k+1
double X[k+1], Y[k+1], err; 0
<random init Y>
while (err > epsilon) {
for (i = 1; i <= k ; i++)
for (j = 1; j <= k ; j++) k+1
X[i,j] = 0.25*(Y[i+1,j] + Y[i‐1,j] +Y[i, j‐1] + Y[i, j+1]);
for (i = 1; i <= k ; i++)
for (j = 1; j <= k ; j++) Parallèle
err += abs(X[i,j] ‐Y[i,j]);
for (i = 1; i <= k ; i++)
for (j = 1; j <= k ; j++)
Y[i,j] = X[i,j];

Introduction au parallélisme

La relaxaDon : code séquenDel

double X[k+1], Y[k+1], err;

<random init Y> Parallèle ?
while (err > epsilon) {
for (i = 1; i <= k ; i++)
for (j = 1; j <= k ; j++)
X[i,j] = 0.25*(Y[i+1,j] + Y[i‐1,j] +Y[i, j‐1] + Y[i, j+1]);
for (i = 1; i <= k ; i++)
for (j = 1; j <= k ; j++)
err += abs(X[i,j] ‐Y[i,j]);
for (i = 1; i <= k ; i++)
for (j = 1; j <= k ; j++)
Y[i,j] = X[i,j];

Introduction au parallélisme

7
 Plan

1. Le modèle graphe de tâches

1. Défini9on
2. Exemples élémentaires
2. Applica9ons et algorithmique
1. Primi9ves et fonc9ons génériques
2. Applica9ons simples
3. Applica9ons difficiles
3. Scheduling
1. Sta9que
2. Dynamique

Introduction au parallélisme 22

PrimiDves

• Problème: calculer et communiquer des

valeurs conceptuellement uniques lorsque
– En espace d’adressages mul9ples, les données
sont distribuées
– En espace d’adressage unique, les données sont
privées
• Parallélisme de données

Introduction au parallélisme 23

La réducDon

• s = f (x0, …, xn-1) où f est

« associa9ve et
commuta9ve » : addi9on,
produit max, min, …

• Réalisa9ons op9misées
spécifiques de chaque
architecture, visibles à
travers des construc9ons
du langage
– OpenMP: reduc9on(+:result) S(n, n) = ?
– MPI_reduce S(n, p) = ?

Introduction au parallélisme 24

8
 La réducDon

• Où est le résultat ?
– OpenMP: partout, plus
précisément dans une
variable partagée
– MPI_reduce : sur un seul
processeur
– Si on veut l’avoir sur tous
les processeurs,
MPI_Allreduce
– Pourquoi ?

Introduction au parallélisme 25

SémanDque du parallélisme et traitement

d’erreurs
« Notes on collec9ve opera9ons: The reduc9on
func9ons (MPI_Op) do not return an error value. As a
result, if the func9ons detect an error, all they can do
is either call MPI_Abort or silently skip the problem.
Thus, if you change the error handler from
MPI_ERRORS_ARE_FATAL to something else, for
example, MPI_ERRORS_RETURN, then no error may
be indicated.The reason for this is the performance
problems in ensuring that all collec9ve rou9nes
return the same error value. » Manuel MPI

Introduction au parallélisme 26

Gather et ScaMer : compacter et décompacter

des données

Gather A[i] = B[L[i]]

Sca_er B[L[I]] = A[i]

• En espaces d’adressages mul9ples

• Gather : récupérer un tableau à par9r de tableaux répar9s sur
processeurs
• Sca_er : distribuer un tableau aux processeurs
• Dans quel ordre ?
• En espace d’adressage unique, compacter/décompacter un tableau
dans un autre
• En parallèle, quelle séman9que si L n’est pas injec9ve ?
Modèles PRAM
• Quelle rela9on avec le tri ?
Introduction au parallélisme 27

9
 ApplicaDons élémentaires

• Retour sur la relaxa9on

• Produit de matrices
• Relaxa9on de Gauss‐Seidel
– Et remplissage dynamique d’un tableau
• Merge Sort (en TD)

Introduction au parallélisme 28

RelaxaDon : un schéma générique pour

• Résolu9on numérique d’EDP par méthode des

éléments finis – « toute » la simula9on
numérique tradi9onnelle
• Certaines applica9ons de traitement d’images
• En général, méthodes de point fixe lorsque le
voisinage n’est pas trop grand
F(X) = X
Sous des condi9ons assez générales, l’itéra9on
Xn+1 = F(Xn)
à par9r de X0 arbitraire converge vers le point fixe
Introduction au parallélisme 29

Master Method

Problème : résoudre
T(n) = aT (n/b) + f(n)
Avec a ≥ 1, b > 1 et f(n) asymptotiquement
positive

Idée: comparer f(n) et n log b a

Introduction au parallélisme 30
€

10
 Master Method – Cas 1

T(n) = aT (n/b) + f(n)

n log b a >> f (n),
spécifiquement f (n) = O(n log b a−ε ) pour ε > 0
alors T(n) = Θ(n log b a )
Exemple : a = 4, b = 2, f(n) = Θ(n) ou Θ(1)
n log b a = n 2
€ T(n) = Θ(n2)
Introduction au parallélisme 31

Master Method – Cas 2

T(n) = aT (n/b) + f(n)

n log b a ≈ f (n),
spécifiquement f (n) = Θ(n log b a lg k n) pour k ≥ 0
alors T(n) = Θ(n log b a lg k +1 n)
Exemple : a = 1, f(n) = Θ(lg n) ou Θ(1)
n log b a = 1
€ T(n) = Θ(lg2n) ou Θ(lg n)
Introduction au parallélisme 32

Master Method – Cas 3

T(n) = aT (n/b) + f(n)

n log b a << f (n),

spécifiquement f (n) = Ω(n log b a +ε ) pour ε > 0
et af (n/b) ≤ cf (n) pour 0 < c < 1
alors T(n) = Θ( f (n))

Introduction au parallélisme 33

11
 Produit de matrices
c11 c12  c1n a11 a12 $ a1n b11 b12 $ b1n
c21 c22  c2n a21 a22 a2n b21 b22 b2n
= X
$ $

    $ $ $ $ $ $ $ $
cn1 cn2  cnn an1 an2 $ ann bn1 bn2 $ bnn

C A B
n
c ij = ∑ aik bkj
k=1

July 14, 2006 34

Programme séquenDel naïf

<init C>
for (i= 0; i < n; i++)
for (j = 0 ; j < n; j++)
for (k = 0; k <n; k++)
C[i,j] = A[i,k]*B[k,j];

Introduction au parallélisme 35

Programme parallèle naïf

<init C>
parfor (i= 0; i < n; i++)
parfor (j = 0 ; j < n; j++) {
parfor (k = 0; k <n; k++)
temp[i,j,k] = A[i,k]*B[k,j];
C[i,j] = Sum_reduce (3, temp);
}
En réalité, temp est réalisé soit comme une variable
privée (EAU), soit comme une variable locale
(EAM)
Introduction au parallélisme 36

12
 ParallélisaDon naïve

• Parallélisme non borné

– Lancer les n3 calculs en parallèle
– Lancer les n2 réduc9ons en parallèle
T1 = Θ(n 3 )
T∞ = Θ(lg(n))
T1 /T∞ = Θ(n 3 /lg(n))
• MAIS problème de localité

€ Introduction au parallélisme 37

Produit de matrices par blocs – vision récursive

C11 C12 A11 A12 B11 B12

= x
C21 C22 A21 A22 B21 B22

A11B11 A11B12 A12B21 A12B22

= +
A21B11 A21B12 A22B21 A22B22

8 multiplications de matrices (n/2) x (n/2).

1 addition de 2 matrices n x n.
July 14, 2006 38

Produit de matrices par blocs – vision récursive

void Mult(*C, *A, *B, n) {

double *T = Cilk_alloca(n*n*sizeof(double));
< base case & partition matrices>
spawn Mult(C11,A11,B11,n/2);
spawn Mult(C12,A11,B12,n/2);
spawn Mult(C22,A21,B12,n/2);
spawn Mult(C21,A21,B11,n/2);
spawn Mult(T11,A12,B21,n/2);
spawn Mult(T12,A12,B22,n/2);
spawn Mult(T22,A22,B22,n/2);
spawn Mult(T21,A22,B21,n/2);
sync;
spawn Add(C,T,n);
sync;
return;
}

July 14, 2006 39

13
 AddiDon de matrices

void Add(*C, *T, n) {

<base case & partition matrices>
spawn Add(C11,T11,n/2);
spawn Add(C12,T12,n/2);
spawn Add(C21,T21,n/2);
spawn Add(C22,T22,n/2);
sync;
return;
}

A1(n) = 4A(n/2) + Θ(1) = Θ(n2) CAS 1

A∞(n) = A∞ (n/2) + Θ(1) = Θ(lg n) CAS 2

July 14, 2006 40

Complexité du produit de matrices par blocs

récursif
cilk void Mult(*C, *A, *B, n) {
double*T = Cilk_allocate(n*n*sizeof(double));
h base case & partition matrices i
spawn Mult(C11,A11,B11,n/2);
8 spawn Mult(C12,A11,B12,n/2);
$
spawn Mult(T21,A22,B21,n/2);
sync;
spawn Add(C,T,n);
sync;
return;
}

M1 (n) = 8M1 (n /2) + A1 (n) + Θ(1)

= 8M1 (n /2) + Θ(n 2 ) CAS 1
3 2 3
= Θ(n ) car log 2 8 = 3 et n << n

Complexité du produit de matrices par blocs

récursif
cilk void Mult(*C, *A, *B, n) {
double*T = Cilk_allocate(n*n*sizeof(double));
h base case & partition matrices i
spawn Mult(C11,A11,B11,n/2);
8 spawn Mult(C12,A11,B12,n/2);
$
spawn Mult(T21,A22,B21,n/2);
sync;
spawn Add(C,T,n);
sync;
return;
}

M∞ (n) = M∞ (n /2) + lg n + Θ(1) = Θ(lg 2 (n))

M1 (n) / M∞ (n) = Θ(n 3 /lg 2 (n)) CAS 2
Meilleur en pra9que

14
 ConstrucDon de tableau

Remplir un tableau nxn avec

A[i, j] = f ( A[i, j–1], A[i–1, j], A[i–1, j–1] ).

Complexité
séquen9elle : n2

July 14, 2006 43

ApplicaDons

• Relaxa9on de Gauss‐Seidel
– Même applica9ons que la relaxa9on de Jacobi
– Converge beaucoup plus vite
• Programma9on dynamique
– Edit distance
– Alignement de séquences
–…

Introduction au parallélisme 44

ConstrucDon Récursive

spawn I;
sync;
spawn II;
I II spawn III;
sync;
n spawn IV;
sync;

III IV
DAG ?

July 14, 2006 45

15
 ConstrucDon récursive

n
T∞(n)= 3T∞(n/2)
T∞(n) = Θ(nlg(3))
I II T1/T∞ = n2/nlg(3)
n ≈ n0.42
Pour n = 1000,
III IV T1/T∞ ≈ 17

Plus de parallélisme

n
spawn I;
sync;
spawn II;
I II IV spawn III;
sync;
spawn IV;
n spawn V;
III V VII spawn VI
sync;
spawn VII;
spawn VIII;
VI VIII IX sync;
spawn IX;
sync;
July 14, 2006 47

Plus de parallélisme

n
T∞(n)= 5T∞(n/3)
T∞(n) = nlg3(5)
I II IV
T1/T∞ = n2/nlg3(5)
n ≈ n0.54
III V VII
Pour n = 1000,
VI VIII IX T1/T∞ ≈ 40

July 14, 2006 48

16
 Calculs creux

• Toutes les structures de

données représentables
par une matrice
d’adjacence où les zéros
sont très dominants
– Maillages
– Certains Graphes
• On ne peut pas/ne veut
pas
– Stocker les 0
– Effectuer les calculs inu9les
• Problème de localité
D’après http://bebop.cs.berkeley.edu/
pubs/gahvari2007-spmvbench-spec.pdf

Introduction au parallélisme 49

ReprésentaDon CRS

• Compressed Row Storage

• V: valeurs non nulles 1 1 0 00
3 0 2 00
• L: L[i] = indice dans V du 0 4 0 50
début de la ligne i 0 0 7 06
• C: C[k] = numéro de
colonne de V[k]
L 1 3 5 7 9

Pour L[i] ≤ k < L[i+1] V 1 1 3 2 4 5 7 6

V[k] == A[i][C[k]] C 1 2 1 3 2 4 3 5
Introduction au parallélisme 50

Produit matrice‐vecteur creux

• Accès par indirec9on

for i= 1, n
for k = L[i], L[i+1] ‐1
y[i] += V[k]*x[C[k]]

Introduction au parallélisme 51

17
 DécomposiDon de domaines

• Renuméroter les • Matrice creuse avec une

sommets structure localisée
2 7
D1 D2 I
4
1 6 D1 A1 0 C1
D2 0 A2 C2
3 5
I B1 B2 S1+S2
8
• Surcoût important,
amor9 car structure
sta9que ré‐exploitée
Introduction au parallélisme 52

ParallélisaDon du produit matrice‐vecteur en

décomposiDon de domaines
Y1 A1 0 C1 X1
Y2 = 0 A2 C2 X2
Y3 B1 B2 S1+S2 X3

En parallèle, calcul local op9misé (cache). X3

doit être dupliqué
Y1 A1 C1 X1 Y2 A2 C2 X2
Z3 = B1 S1 X3 T3 = B2 S2 X3

Mise à jour aux interfaces (pe9t)

Y3 = T3 + T3
Introduction au parallélisme 53

Branch‐And‐Bound

Exemple: arbre max‐min

• Parallélisme naïf
– Développement de
l’arbre
– Heuris9que
d’évalua9ons
– Remontée

Introduction au parallélisme 54

18
 Branch‐And‐Bound

Exemple: arbre max‐min

• Parallélisme naïf
– Développement de
l’arbre
– Heuris9que
d’évalua9ons
– Remontée
• Coupures alpha‐beta
• Problème d’équilibrage
de charge

Introduction au parallélisme 55

ApplicaDons irrégulières dynamiques

Le voisinage évolue dans le temps

• Voisinage local – N • Voisinage global – N2

interac9ons interac9ons
• Dynamique moléculaire • N‐corps

Introduction au parallélisme 56

ApplicaDons irrégulières dynamiques

Le voisinage évolue dans le temps

• Voisinage local – N • Voisinage global – N2

interac9ons interac9ons
• Dynamique moléculaire • N‐corps

Introduction au parallélisme 57

19
 ApplicaDons irrégulières dynamiques

Le voisinage évolue dans le temps

• Voisinage local – N • Voisinage global – N2

interac9ons interac9ons
• Dynamique moléculaire • N‐corps

Introduction au parallélisme 58

Plan

1. Le modèle graphe de tâches

1. Défini9on
2. Exemples élémentaires
2. Applica9ons et algorithmique
1. Primi9ves et fonc9ons génériques
2. Applica9ons simples
3. Applica9ons difficiles
3. Scheduling
1. Sta9que
2. Dynamique

Introduction au parallélisme 59

Scheduling = placement‐ordonnancement

Avec P processeurs, réaliser un ordre par9el compa9ble avec

celui défini par le DAG.
« Replier » le parallélisme illimité sur P ressources
• Objec9f : Minimisa9on du temps total d’exécu9on (makespan)
TP ‐> équilibrage de charge
• Contrainte : minimisa9on des surcoûts, au premier ordre
localité spa9ale et temporelle voir chapitres programma9on
• Qui ? Placement des calculs
• Quand ? Ordonnancement
– Intra‐code: synchronisa9on (OpenMP, HPF, Cilk ‐ PAR(SEQ)),
communica9on (MPI, PVM ‐ PAR(SEQ)), structures de contrôles (HPF
‐ SEQ(PAR))
– Extérieur: Exécu9f (Condor, Cilk)

Introduction au parallélisme 60

20
 Scheduling staDque

• Off‐line, éventuellement paramétré par le

nombre de processus et le numéro de
processus
Parallélisme de données / itéra9f: les temps de
calcul sont supposés iden9ques
• Cas régulier : Block, cyclic, cyclic (k), …
• Cas irrégulier : ad hoc – par exemple bisec9on
récursive

Introduction au parallélisme 61

DistribuDon bloc

I = p*B +j

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

I indice global. B taille du bloc. B = N/P

p numéro de processeur. p = I/B
j indice local. j = I mod P
Introduction au parallélisme 62

DistribuDon bloc

I = p*B +j

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2

I indice global. B taille du bloc. P = N /B

p numéro de processeur. p = I/B
j indice local. j = I mod P
Introduction au parallélisme 63
€

21
 DistribuDon cyclique

I = j*P + p

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4

I indice global
p numéro de processeur. p = I mod P
j indice local. j = I/P
Introduction au parallélisme 64

DistribuDon cyclique

I = j*P + p

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5

I indice global
p numéro de processeur. p = I mod P
j indice local. j = I/P
Introduction au parallélisme 65

DistribuDon bloc‐cyclique – cyclic(B)

I = b*B + j = B*(c*P+ p) + j

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

I indice global
p numéro de processeur. p = I mod P
j indice local. j = I/P
Introduction au parallélisme 66

22
BisecDon récursive

Les éléments de calcul sont

caractérisés par une
donnée nD

Souvent posi9on spa9ale

Introduction au parallélisme 67

BisecDon récursive

Les éléments de calcul sont

caractérisés par une
donnée nD

Souvent posi9on spa9ale

Introduction au parallélisme 68

BisecDon récursive

Applicable aussi à un
maillage
Et plus généralement à
toute structure de données
• irrégulière
• creuse
• organisée spatialement
(localité)

Introduction au parallélisme 69

23
 Limites du scheduling staDque

Parallélisme de contrôle
Pour un problème modérément général et
réaliste
P processeurs iden9ques
M tâches indépendantes de durée ti
La minimisa9on du makespan est un problème
NP‐complet
Scheduling dynamique
Introduction au parallélisme 70

Scheduling dynamique

• Mo9va9ons supplémentaires et plus

réalistes :
– La durée des calculs n’est pas prévisible
– La puissance des machines n’est pas connue
• Scheduling on‐line : décidé à l’exécu9on
• Ques9ons
– Surcoûts : ges9on des processus ou des threads,
des échanges d’informa9on
– Robustesse à l’irrégularité des temps d’exécu9on
Introduction au parallélisme 71

Scheduling glouton (greedy)

• Parallélisme de contrôle
• Exécuter toute tâche
prête dès que possible
• (Rela9vement) facile à
implémenter
• Distance à l’op9mal ?

Introduction au parallélisme 72

24
 Scheduling glouton (greedy)

P processeurs
• Exécuter tout ce qui peut l’être dès que
possible
• Phase pleine: le nombre de processus ac9fs
est ≥ P
– Choix des processus ac9vés = algorithmique du
scheduling
• Phase incomplète: le nombre de processus
ac9fs est < P
Introduction au parallélisme 73

Scheduling glouton (greedy)

Théorème [Graham ’68].

Pour tout ordonnancement glouton
TP ≤ T1/P + T∞.
Preuve
• Le nombre de phases pleines est au plus T1/P
puisque chaque pas de chaque phase pleine
effectue un travail P,
• Le nombre de phases incomplètes est au plus T∞
puisque chaque pas de chaque phase incomplète
effectue un travail 1 le long du chemin critique

Introduction au parallélisme 74

Scheduling glouton (greedy)

Théorème [Graham ’68].

Pour tout ordonnancement glouton
TP ≤ T1/P + T∞
Corollaire 1 Tout ordonnancement glouton est au
plus à un facteur 2 de l’optimal.
Preuve
Si TP* est l’optimal (à P processeurs)
TP* ≥ T1/P et TP*≥ T∞
D’où
TP ≤ 2TP*
Introduction au parallélisme 75

25
 Scheduling glouton (greedy)

Théorème [Graham ’68].

Pour tout ordonnancement glouton
TP ≤ T1/P + T∞
Corollaire 2 Si P << T1/T∞ l’accélération est
quasi-linéaire
Preuve
T1/P >> TP donc T1/P +T∞≈ T1/P
T1/PT∞: parallel slackness
Introduction au parallélisme 76

ImplémentaDon du scheduling dynamique

Centralisé: Maître‐Esclave
Maître M
– Gère la distribu9on des tâches :
glouton, GSS, …
– Effectue les opéra9ons globales par S S S
exemple réduc9on
P Esclaves
– Exécutent un bloc, et redemandent du
travail dès que terminé

Introduction au parallélisme 77

Maître‐Esclave à grain fin

• Pure self‐scheduling : coût de synchronisa9on

excessif
• Idée : Au début, on alloue des blocs de grande
taille pour diminuer les coûts de synchronisa9on,
puis des blocs de taille décroissante pour ajuster
progressivement l’équilibrage de charge
– Guided self‐scheduling (GSS): chaque esclave reçoit
1/P du batch restant
– Factoring (FSS): durant chaque phase, chaque esclave
reçoit 1/P de la moi9é du batch restant

Introduction au parallélisme 78

26
 Maître‐Esclave à grain fin

N = 256, P = 4
Sta9que : 64, 64, 64, 64
PSS : 1,1,1,1,1,1,1…
GSS : 64,48,36,27,20,…
FSS : 32,32,32,32,8, 8, 8, 8, 4, 4, 4, 2,…

Introduction au parallélisme 79

Cilk’s Work-Stealing Scheduler

Spawn!
P P P P

© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 80

Cilk’s Work-Stealing Scheduler

Each processor maintains a work
deque of ready threads, and it
manipulates the bottom of the deque
like a stack.

Spawn! Spawn!
P P P P

© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 81

27
 Cilk’s Work-Stealing Scheduler
Each processor maintains a work
deque of ready threads, and it
manipulates the bottom of the deque
like a stack.

Return!
P P P P

© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 82

Cilk’s Work-Stealing Scheduler

Each processor maintains a work
deque of ready threads, and it
manipulates the bottom of the deque
like a stack.

Return!
P P P P

© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 83

Cilk’s Work-Stealing Scheduler

Each processor maintains a work deque
of ready threads, and it manipulates the
bottom of the deque like a stack.

Steal!
P P P P
When a processor runs out of
work, it steals a thread from the
top of a random victim’s deque.
© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 84

28
 Cilk’s Work-Stealing Scheduler
Each processor maintains a work deque
of ready threads, and it manipulates the
bottom of the deque like a stack.

Steal!
P P P P
When a processor runs out of
work, it steals a thread from the
top of a random victim’s deque.
© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 85

Cilk’s Work-Stealing Scheduler

Each processor maintains a work deque
of ready threads, and it manipulates the
bottom of the deque like a stack.

P P P P
When a processor runs out of
work, it steals a thread from the
top of a random victim’s deque.
© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 86

Cilk’s Work-Stealing Scheduler

Each processor maintains a work deque
of ready threads, and it manipulates the
bottom of the deque like a stack.

Spawn!
P P P P
When a processor runs out of
work, it steals a thread from the
top of a random victim’s deque.
© 2006 Charles E. Leiserson Multithreaded Programming in Cilk — LECTURE 1 July 13, 2006 87

29
 Placement/ordonnancement dynamique

• Répar9 : Vol de travail

– Peut être prouvé op9mal pour une large classe
d’applica9ons
– Implémenta9on délicate : ges9on de verrous en
espace d’adressage unique, protocole en espaces
d’adressages mul9ples
– h_p://supertech.lcs.mit.edu/cilk/

Introduction au parallélisme 88

30