Modèles de Parallélisme

1

Systèmes Distribués - K. Yétongnon

Systémes Distribués2004 – 2005K. Yétongnon

Modèles de Parallélisme


2

Modèles de traitement parallèle

Trois types de modèles : Modèles Graphes (DAG : Directed Acyclic Graph) Modèle à mémoire partagée PRAM

Parallel Random Access Machine Deux modes d’opération d’une Machine PRAM

Synchorne : tous les processeurs sont contrôlés par une horloge commune

Asynchrone : chaque processeur est contrôle par une horloge dédiée

Modèle Réseau Mémoire distribuée Processeurs communiquent par échange de messages

3



Traitement Parallèle

Modèles Graphes


4

Modèles Graphes

Ceci sera fait en TD et par des exemples dans d’autres parties du cours

5




Modèles PRAM


6

Modèle PRAM

Classification de différentes architectures parallèles PRAM

Flynn propose une classification basée sur deux critères : Flux des données Flux des instructions

Chaque flux peu être : Unique (Single) Multiple


7

Modèle PRAM

Classification de Flynn

SINGLE MULTIPLE

SINGLE SISD SIMD

MULTIPLE MISD MIMD

Flux de données

Flu

x d

’In

stru

ctio

ns


8

Modèle PRAM

Une extension simple du modèle classique RAM (Random Access Memory) pour prendre en compte la multiplicité de processeurs

Mémoire Globale (Shared – Memory)

P1 P2 Pp


9

Modèle PRAM

Propriétés

p Processeurs ayant chacun une mémoire locale (non accessible aux autres processeurs)

Une Mémoire Globale (Shared-Memory) partagée par tous les processeurs

Chaque processeur a un indexe (une identité) i (0 i p-1 qui peut être utilisé dans les comparaisons logiques ou les calculs d'adresses


10

Modèle PRAM

Deux modes d'opération du modèle PRAM : Synchrone

Les processeurs évoluent de manière synchronisée sous le contrôle d'une horloge commune. A chaque étape (unité de temps), les processeurs actifs exécutent une instruction sur des données (déterminées selon les indexes des processeurs)

A chaque étape, certains processeurs sont inactifs

Ce mode est adapté aux architecture de type SIMD, MIMD

Asynchrone Chaque processeur évolue sous le contrôle d'une horloge locale.

Le programmeur doit inclure des points de synchronisation quand nécessaire pour coordonner les activités des processeurs.

Plutôt adapté aux architectures MIMD


11

Modèle PRAM

Exemple d'opération en MODE SYNCHRONE Exécuter en mode synchrone sur une machine parallèle à 4

processeurs, l'instruction suivante :

Algorithme : Processeur iInput : (1) A, B (2) i, identité du processeurOutput : (1) CBegin

If ( B==0) C = AElse C = A/B

End


12

Modèle PRAM

Etape 1

A : 7

B : 0

C : 7 (Actif, B=0)

A : 2

B : 1

C : 0 (Inactif, B0)

A : 4

B : 2

C : 0 (Inactif, B0)

A : 5

B : 0

C : 5 (Actif, B=0)

Processeur 3Processeur 2Processeur 1Processeur 0

Etape 2

A : 7

B : 0

C : 7 (Inactif, B=0)

A : 2

B : 1

C : 2 (Actif, B0)

A : 4

B : 2

C : 2 (Actif, B0)

A : 5

B : 0

C : 5 (Inactif, B=0)


Initial

A : 7

B : 0

C : 0

A : 2

B : 1

C : 0

A : 4

B : 2

C : 0

A : 5

B : 0

C : 0



13

Modèle PRAM

Quatre variantes du Modèle PRAM : selon le type d'accès simultané à une même adresse mémoire ou un bloc de mémoire

EREW : Exclusive - Read, Exclusive -Write Les accès simultanés ( en lecture ou écriture) à une adresse

mémoires sont interdits

CREW : Concurrent – Read, Exclusive – Write Accès simultanés autorisés en lecture Accès exclusif en écriture (une seule écriture à la fois à la même

adresse)


14

Modèle PRAM

CRCW : Concurrent – Read, Concurrent – Write Accès simultanés en lecture Accès simultanés en écriture

ERCW : Exclusive Read – Concurrent Write

Problèmes d'écritures concurrentesQu'est ce qu'on écrit dans une adresse mémoire en cas d'écritures concurrentes?


15

Modèle PRAM

Résolution des problèmes d'écritures concurrentes dans le modèle CRCW ( m processeurs en écriture sur une variable X) :

Common CRCW : les écritures concurrentes sont autorisées si les valeurs écrites par les m processeurs sont égales

SUM CRCW : la somme des valeurs est écrite dans X

Random CRCW : un processeur est choisi au hasard et autorisé à eécrire sa valeur dans X. Les autres écritures échouent (terminent sans écrire)

Priority CRCW : Une priorité est associée à chaque processeur. Le processeur de plus forte priorité est autorisé à écrire X. Les autres écritures échouent (terminent sans écrire)


16

Modèle PRAM

Exemple : Soit P1 (50 X) , P2 (60 X), P3 (70 X) des demandes d’écritures simultanées sur une variable X :

Common CRCW ou ERCW : ECHEC

SUM CRCW : la somme (180) des valeurs est écrite dans X

Random CRCW : un processeur est choisi au hasard et autorisé à eécrire sa valeur dans X. Les autres écritures échouent (terminent sans écrire)

X { 50, 60, 70 } Priority CRCW : Une priorité est associée à chaque processeur. Le

processeur de plus forte priorité est autorisé à écrire X. Les autres écritures échouent (terminent sans écrire)

SI P1 a la plus forte priorité, alors x = 50


17

Modèle PRAM

Instructions spéciales pour lire et écrire en mémoire globale

Global read (X, x)

Global write (Y, y)


18

Modèle PRAMExemple de Calcul (1) : Produit Matrice Vecteur

Produit Matrice-Vecteur Y = AXA est une matrice n x n, X un vecteur de taille n p processeurs opérant en mode asynchrone, pn et r = n/p

Y1Y2….

Yn

A1,1 A1,2 … A1,nA2,1 A2,2 … A2,n ……..

A n,1 An,2 ... An,n

=

X1X2….

Xn

X

Mémoire Globale

P1 P2 Pp


19


Principe de la solution

Partitionner les données en blocs ou partitions.

Chaque processeur calcule des résultats partiels

sur une partition

Combiner les résultats partiels

Comment partitionner le calcul de Y = AX?


20


Partition Horizontale de la matrice A La matrice A est découpée horizontalement en p blocs Ai,*

(sous matrices) de r lignes

A =

A1A2….

Ap

A1,1 A1,2 … A1,n …….Ar,1 A2,2 … A2,n …….

A(p-1)r,1 A(p-1),2 … A(p-1),n ……..A pr,1 Apr,2 ….Apr,n

=

A1

Ap

r lignes

r lignes

Processeur Pi calcule le produit matriciel partiel Yi = Ai * X


21


Partition Horizontale de la matrice A Processeur Pi calcule le produit matriciel partiel Yi = Ai * X

A1,1 A1,2 … A1,n …….Ar,1 A2,2 … A2,n

X1X2….Xn

X

Ar+1,1 Ar+1,2 … Ar+1,n …….A2r,1 A2r,2 … A2r,n

X1X2….Xn

X

A(p-1)r,1 A(p-1)r,2 …A(p-1)r,n …….Apr,1 Apr,2 … Apr,n

X1X2….Xn

X

Y1Y2….Yr

Y(p-1)r+1Y(p-1)r+2….Ypr

Yr+1Yr+2….Y2r

P1

P2

Pp


22


Partition Horizontale de la matrice A

Chaque Ai est une matrice r x n Chaque processus Pi :

lit de la mémoire globale les valeurs Ai et Xcalcule le produit Zi = Ai Xécrit les valeurs de Zi sur les composants correspondants de Y en

mémoire globale Cette solution nécessite :

des lectures concurrentes du vecteur X des lectures exclusives des blocs de lignes ((i-1)r +1) – ir de la

matrice A affectées au processeur Pi i = 1,2, … n des écritures exclusives sur les composantes ((i-1)r +1) – ir du

vecteur Y calculées par le processeur Pi i = 1,2, … n Architecture requise : PRAM CREW


23


Algorithme exécuté par le processeur Pi

Input A : Une matrice nxn (mémoire globale)

X : Un vecteur de n éléments (mémoire globale)

Outputy = AX (y est une variable partagée en mémoire globale)Variables locales à Pi i : identité du processeur Pi

p, n : nombre de processeurs et la dimension de A

Begin1. Global read ( x, z)2. global read (A((i-1)r + 1 : ir, 1:n), B)3. calculer W = Bz4. global write (w, y(i-1)r+1 : ir))

End


24


Analyse de la solution et Estimation : Coût de calcul

Ligne 3 représente le calcul du produit vectoriel et nécessite O( n2/p) opérations arithmétiques

r lignes X n opérations ( avec r = n/p) Coût de communication

Ligne 1 : transfert de O(n) nombres de la mémoire globale vers la mémoire locale

Ligne 2 : transfert de O(n2/p) nombres de la mémoire globale vers la mémoire locale de Pi

Ligne 4 : transfert de O(n/p) nombres de la mémoire locale de Pi vers la mémoire globale

Au total :

Coût : O(n) + O(n2/p) + O(n2/p) + O(n/p) = O(n2/p)


25


Autre solution : Partition Verticale de la matrice A + Partition du vecteur X

Y1Y2

….

Yn

A1,1 … A1,r A2,1 … A2,r An,1 … An,r

X1 … Xr

A1

X1

*

r colonnesProcesseur P1

A1,(p-1)r +1 ... A1,prA2,(p-1)r +1 ... A2,pr

An,(p-1)r +1 ... An,prX(p-1)r +1 ... Xpr

Ap

Xp

*

r colonnesProcesseur Pp

……..


26


Solution en deux phases :

Phase 1 : Calcul des produits partiels

Les p processeurs calculent les produits partiels

Z1 =A1X1

Z2 = A2 X2,

…

Zp = ApXp

Phase 2 : Calcul du produit final

Y= AX = Z1 + Z2 + … + Zp

Nécessite une synchronisation en fin de phase 1. Toutes les valeurs Zi doivent être disponibles avant le début de la phase 2


27



Begin1. Global read ( x( (i-1)r +1 : ir) , z)2. global read (A(1:n, (i-1)r + 1 : ir), B)3. calculer W = Bz4. Synchroniser les processeurs Pi5. global write (w, y(i-1)r+1 : ir))

End

Input A : Une matrice nxn (mémoire globale)

X : Un vecteur de n éléments (mémoire globale)Output

y = AX (y est une variable partagée en mémoire globale)Variables locales à Pi

i : identité du processeur Pi p, n : nombre de processeurs et la dimension de A


28


Partition Horizontale de la matrice A

Chaque Ai est une matrice n x r Chaque processus Pi :

lit de la mémoire globale les colonnes associées ( Ai ) et le sous bloc Xi de X

calcule le produit Zi = Ai Xise synchronise avec les autres processeurs avant le début de la

phase de la somme Y = AX = Z1 + Z2 + … + Zp Cette solution nécessite :

des lectures exclusives des vecteurs Xi des lectures exclusives des blocs de colonnes ((i-1)r +1) – ir de la

matrice Ades écritures concurrentes sur le vecteur final Y

Architecture requise : PRAM ERCW ( avec résolution de conflit d’écriture SUM)


29

Modèle PRAMExemple de Calcul (3) : Somme de n entiers

Somme de n entiers sur une machine PRAM

Soit A un tableau de n éléments en mémoire globale.

Un tableau A de n = 2k éléments en mémoire globale d’une machine PRAM

On veut calculer la somme S = A(1) + A(2) + …. + A(n)

Construire un arbre binaire pour calculer la somme.


30


B(1)=A(1)

B(2)=A(2)

B(1)=A(1)

B(2)=A(2)

B(1)=A(1)

B(2)=A(2)

B(1)=A(1)

B(2)=A(2)

P1 P2 P3 P4 P5 P6 P7 P8

B(1) B(2) B(3) B(4)

P1 P2 P3 P4

B(1) B(2)

P1 P2

B(1)

S=B(1)

P1

P1

Niveau >1, Pi calculeB(i) = B(2i-1) + B(2i)

Niveau 1, Pi calculeB(i) = A(i)


31



Input A : Un tableau de n = 2k éléments en mémoire global

OutputS : où S= A(1) + A(2) + …. . A(n)

Variables locales à Pin : nombre d’éléments

i : identité du processeur Pi

Begin1. global read ( A(i), a)2. global write (a, B(i))3. for h = 1 to log n do

if ( i ≤ n / 2h ) then begin global read (B(2i-1), x)

global read (b(2i), y) z = x +y global write (z,B(i)) end

4. if i = 1 then global write(z,S)End


32

Modèle PRAMExemple de Calcul (4) : Produit de matrice C = AB

Produit de deux matrices C[Cij] = A[Aij] B[Bij]

L'élément Cij est calculé par l'expression

Cij = l Ail * Blj

Si on dispose de n3 processeurs dénommés par Pi,j,l (1 i,j,l n)

Chaque valeur est calculé par l'ensemble de processeurs

Pi,j,l (1 l n) en O(logn) unités de temps.


33


P0,0,3 C0,0,3 = A00 * B03 + A01 * B13 + A02 * B23 + A03 * B33

C0,0,0

C0,0,1

C0,0,2

C0,0,3

C00 =

P0,0,3

P0,0,2

P0,0,1

P0,0,0

C0,1,0 C0,2,0 C0,3,0C0,0,0


34


Algorithme exécuté par le processeur Pi,j,l i,j,l = 0,1,…,n-1

Input : (1) les matrices n x n A et B en mémoire globale (n = 2k)

(2) Les variables locales (i,j,l) indexe du processeur

Output : Le produit C = AB

Begin

1. calculer C'(i,j,l) = A(i,l) * B(l,j)

2. for h = 1 to log n do

if ( l n/ 2h) then C'(i,j,l) = C'(i,j,2l - 1 ) + C'(i,j,2l)

3. if (l=1) then C(i,j) = C'(i,j,1)

End


35


Remarques Lectures concurrentes de certains éléments

Par exemple les processeurs Pi,1,l, Pi,2,l, …, Pi,n,l lisent l'élément A(i,l) en même temps

Nécessité d'une architecture CREW

36




Modèles Réseaux


37

Modèle Réseau

Prend en compte l'architecture de communication sous-jacente

Un réseau peut être vu comme un graphe G=(N,E) dans lequel : Chaque nœud i N est un processeur Chaque arc (i,j)E représente une communication entre les

processeurs i et j

(lien direct bidirectionnel entre deux processeurs)


38

Modèle RéseauExemple (1) : Produit Matrice Vecteur

Matrix-Vector multiplication on a linear arrayGiven an nxn matrix A = [aij], i,j [1,n] and an n order

vector X=[xi], compute the product Y=Ax

J=1

n

Y=[yi], where yi = aij*xj

Systolic array algorithm for n=4

x4 x3 x2 x1

a14

a13

a12

a11

a24

a23

a22

a21

a34

a33

a32

a31

a44a43

a42

a41

. ..

.

.

.

P1 P2 P3 P4


39


•At step j, xj enters the processor P1. At step j, processor Pi receives (when possible) a value from its left and a value from the top. It updates its partial as follows:

Yi = Yi + aij*xj , j=1,2,3, ….

• The computation is completed when x4 and a44 reach processor P4 at Step N + N –1 = 2N-1• Conclusion: The algorithm requires (2N-1) steps. At each step, active processor Perform an addition and a multiplication• Complexity of the algorithm: O(N)

• Values xj and aij reach processor i at the same time at step (i+j-1)•(x1, a11) reach P1 at step 1 = (1+1-1)•(x3, a13) reach P1 at setep 3 = (1+3-1)

• In general, Yi is computed at step N+i-1


40


J=1

4 y2 = a2j*xj

J=1

4 y3 = a3j*xj

J=1

4 y4 = a4j*xj

J=1

4 y1 = a1j*xj

x2

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

Step1

2

3

4

5

6

7

x1

x3

x4

x1

x2 x1

x1

x1

x2

x2

x2 x1

x3

x3

x3

x3 x2 x1

x4

x4

x4


41


Systolic array algorithm: Time-Cost analysis

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

1 Add; 1 Mult; active: P1 idle: P2, P3, P4

2 Add; 2 Mult; active: P1, P2 idle: P3, P4

3 Add; 3 Mult; active: P1, P2,P3 idle: P4

4 Add; 4 Mult; active: P1, P2,P3 P4idle:

3 Add; 3 Mult; active: P2,P3,P4idle: P1

2 Add; 2 Mult; active: P3,P4idle: P1,P2

1 Add; 1 Mult; active: P4idle: P1,P2,P3


42


Systolic array algorithm: Time-Cost analysis

x2

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

P1 P2 P3 P4

Step1

2

3

4

5

6

7

x1

x3

x4

x1

x2 x1

x1 x2

x2

x3

x3

x3

x4

x4

x4

1 Add; 1 Mult; active: P1 idle: P2, P3, P4

2 Add; 2 Mult; active: P1, P2 idle: P3, P4

3 Add; 3 Mult; active: P1, P2,P3 idle: P4

4 Add; 4 Mult; active: P1, P2,P3 P4idle:

3 Add; 3 Mult; active: P2,P3,P4idle: P1

2 Add; 2 Mult; active: P3,P4idle: P1,P2

1 Add; 1 Mult; active: P4idle: P1,P2,P3


43

Modèle RéseauExemple (2) : Matrix multiplication on a 2-D nxn Mesh

Given two nxn matrices A = [aij] and B = [bij], i,j [1,n],

Compute the product C=AB , where C is given by :

J=1

n

C=[cij], where cij = aik*bkj

Example: Systolic mesh algorithm for n=4

•At step i, Row i of A (starting with ai1) is entered from the top into column i (into processor P1i)

•At step j, Column j of B (starting with b1j) is entered from the left into row j (to processor Pj1)

• The values aik and bkj reach processor (Pji) at step (i+j+k-2). At the end of this step aik is sent down and bkj is sent right.


44

Modèle Réseau Exemple (2) : Matrix multiplication on a 2-D nxn Mesh


STEP 1

(1,1)

(2,1)

(3,1)

(4,1)

(1,2) (1,3) (1,4)

(2,4)(2,3)(2,2)

(3,4)(3,3)(3,2)

(4,4)(4,3)(4,2)

a14a13a12a11

a24a23a22a21

a34a33a32a31 . .

a44a43a42a41 . . ..

b41 b3 b21 b11

b42 b32 b22 b12 .

b43 b33 b23 b13 . .

b44 b34 b24 b14 ..


45



STEP 5

a11

a24 a33 a42b41 b31 b21

a14

a13

a12

b42

b33

b24

b32 b22 b12

b23 b13

b14

a23 a32 a41

a22 a31

a21

b43

b34b44

b11

a34 a43a44 A

B


46


Analysis

To determine the number of steps for completing the multiplication of the matrice, we must find the step at which the terms ann and bnn reach rocessor Pnn.

Values aik and bkj reach processor Pji at i+j+k-2 Substituing n for i,j,k yields :

n + n + n – 2 = 3n - 2

Complexity of the solution: O(N)


47

Modèle Réseau Exemple (3) : Matrix multiplication on a ring

Goal

To pipeline data into the processors, so that n product terms are computed and added to partial sums at each step.

Distribution of X on the processors

Xj 1j N, Xj is assigned to processor N-j+1

N=4

X4 X3 X2 X1

P1 P2 P3 P4

a13

a12

a11

a14

a22

a21

a24

a23

a31

a34

a33

a32

a44

a43

a42

a41

Xi

aij

This algorithm requires N steps for a matrix-vector multiplication


48

Modèle Réseau Exemple (3) : Matrix multiplication on a ring

Another way to distribute the Xi over the processors and to input

Matrix A Row i of the matrix A is shifted (rotated) down i (mod n) times

and entered into processor Pi. Xi is assigned to processor Pi, at each step the Xi are shifted right

X1 X2 X3 X4

P1 P2 P3 P4

a12

a13

a14

a11

a23

a24

a21

a22

a34

a31

a32

a33

a41

a42

a43

a44

Xi

aij

N=4

Diagonal


49

Modèle Réseau Exemple (4) : Matrix multiplication on a 2D Mesh with Wrap around

Given two nxn matrices A = [aij] and B = [bij], i,j [1,n],

Compute the product C=AB

The values of the matrices are stored in the processors.

Initially:

PE[i,j] has x[i,j] = a[i,j] and y[i,j] = b[i,j]

Row i shift left x data (n- i-1) mod n times

Col j shift up y data (n- j-1) mod n times


50


Step 1

a11 a12 a13 a14b11 b12 b13 b14

a21

a31

a41

b21

b31

b41

b22 b23 b24

b32 b33 b34

b42 b43 b44

a22 a23 a24

a32 a33 a34

a42 a43 a44


51


Step 2Rearrange Data a11 a12 a13 a14

b11 b22 b33 b44

a22

a33

a44

b21

b31

b41

b32 b43 b14

b42 b13 b24

b12 b23 b34

a23 a24 a21

a34 a31 a32

a41 a42 a43

Left Shift

Up Shift


52


a11 a12 a13 a14b11 b22 b33 b44

a22

a33

a44

b21

b31

b41

b32 b43 b14

b42 b13 b24

b12 b23 b34

a23 a24 a21

a34 a31 a32

a41 a42 a43

Step 3Multiply Add and Move Data

c21 = a22b21 + a21b11 + a24b41 + a23b33

Data Move at Cell ij

bkj

aik

Data Move at Cell ij

aik*bkjk=1

n

Cij =


53

Modèle Réseau Exemple (5) : Sum of N=2P numbers on a p-hypercube

Compute S = xi, xi is assigned to processor Pi

0 1

32

4 5

6 7

(X0)

(X2)

(X1)

(X7)

(X3)

(X4) (X5)

(X6)


54


Step 1: Processors of the sub-cube 1XX send their data to corresponding processors in sub-cube 0XX

0 1

32

4 5

6 7

(X0+X4)

(X2+X6)

(X1+X5)

(X3+X7)


55


Step 2: Processors of the sub-cube 01X send their data to corresponding processors in sub-cube 00X

0 1

32

4 5

6 7

(X0+X4+X2+X6) (X1+X5+X3+X7)

P Processeurs actifs P Processeurs inactifs


56


Step 3: Processors of the sub-cube 01X send their data to corresponding processors in sub-cube 00X


0 1

32

4 5

6 7

S = (X0+X4+X2+X6+ X1+X5+X3+X7)

The sum of the N numbers is accumulated on node P0


57


Algorithm for Parallel sum on hypercube

Input: 1) An array of X of N=2p of numbers, X[i] is assigned to processor Pi 2) processor identity idOutput: S= X[0]+…+X[N], stored on processor P0

Processor PiBegin

My_id = id ( My_id i)S=X[i]For j = 0 to (d-1) do begin Partner = M_id XOR 2j

if My_id AND 2j = 0 beginreceive(Si, Partner)S = S + Si end

if My_id AND 2j 0 beginsend(S, Partner)exit end

end end


58

Modèle Réseau Exemple (6) : One-to-all broadcast in a p-hypercube

•Another example of processing on a 3-hypercube: Broadcast an element X stored on one processor (say P0) to the other processors of the hypercube.

• This broadcast can be performed in O(logn) as follows

0 1

32

4 5

6 7

X

Initial distribution of data


59


•Step 1: Processor Po sends X to processor P1•Step 2: Processors P0 and P1 send X to P2 and P3 respectively•Step 3: Processor P0, P1, P2 and P3 send X to P4, P5, P6 and P7

X0 1

32

4 5

6 7

XStep 1 Step 20 1

32

4 5

6 7

X X

X X

X X0 1

32

4 5

6 7

XX

X X

XX

Step 3



60


Algorithm for a broadcast of X on a p-hypercube

Input: 1) X assigned to processor P0 2) processor identity idOutput: All processor Pi contain X

Processor PiBegin

If i = 0 then B = XMy_id = id ( My_id i)For j = 0 to (d-1) do if My_id 2j begin Partner = My_id XOR 2j if My_id > Partner receive(B, Partner) if My_id < Partner send(S, Partner)

endend


61

Exercice

Illustrer sur une figure les différentes étapes du produit matrice vecteur

C[ij] = A[ij] x X[i], i,j sur les architectures suivantes. Déterminer pour chaque solution le nombre d’étapes et le facteur d’accélération

Un réseau linéaire de 3 processeurs Un anneau de 3 processeurs


62

Exercice

Illustrer les différentes étapes du produit de matrice 3 X3

C[ij] = A[ij] X B[ij] sur les architectures suivantes et déterminer pour chaque solution le nombre d’étapes et le facteur d’accélération

Une grille 3 X 3 Un tore 3X3 (grille avec retour)


63

Exercice

Illustrer les différentes étapes du produit de matrice 2 X2

C[ij] = A[ij] X B[ij] sur une architecture PRAM composée de 8 processeurs


64

Exercice

Show that the code fragment below computes a Prefix Sum on a PRAM model. From an array of values A of size n computes in place the prefix sums B[i] <----- A[1] + A[2] + … + A[i]

Give a figure to illustrate the data transfers and computations performed in the different steps.

for i=0 to (n-1) pardo begin

for k = 0 to log (n – 1) do

if ( i ≥ 2k ) then begin

global read ( A [ i - 2k ], a)

global read (A[ i ], b )

c = a + b

global write (c, A[i])

end

end

65



Calculs Matriciels

(2ème visite)


66

Partitions des données

Si le nombre de processeurs est égal ou supérieur au nombre de données On associe à chaque processeur une unité de chaque donnée

Si le nombre de processeurs est inférieur au nombre de données On associe à chaque processeur un bloc de données à traiter

Comment réaliser les partitions de données


67

Partition des données

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

P0 P1 P2 P3

•Découpage en bandes suivant les colonnes

•Un ensemble de n colonnesconsécutives est affecté à chaque processeur Pi


68


2

3

0

1

P0 P1 P2 P3

•Découpage en bandes suivant les colonnes

•Répartition cyclique

5

6

7

4

9 11

8 10

13

12 14

15


69


•Découpage en bandes suivant les lignes

•Un ensemble de n lignes consécutives est affecté à chaque processeur

P0

P1

P2

P3

0

1

2

3

4

5

6

7

14

15

13

12

10

11

9

8


70


•Découpage en bandes suivant les lignes

•Répartition cyclique

P0

P1

P2

P3

8

9

11

10

12

13

15

14

4

5

7

6

0

1

3

2


71


P0 P1 P2 P3

P4 P5 P6 P7

P8 P9 P10 P11

P12 P13 P14 P15

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7)

(1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)

(2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7)

(3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7)

(4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7)

(5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7)

(6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7)

(7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7)

(0,0) (0,1) (0,2) (0,3)(0,4) (0,5) (0,6) (0,7)

(4,0) (4,4) (4,1) (4,5) (4,2) (4,6) (4,3) (4,7)

(1,0) (1,4) (1,1) (1,5) (1,2) (1,6) (1,3) (1,7)

(2,0) (2,4) (2,1) (2,5) (2,2) (2,6) (2,3) (2,7)

(6,0) (6,4) (6,1) (6,5) (6,2) (5,6) (6,3) (6,7)

(7,0) (7,4) (7,1) (7,5) (7,2) (7,6) (7,3) (7,7)

(3,0) (3,4) (3,1) (3,5) (3,2) (3,6) (3,3) (3,7)

(5,0) (5,4) (5,1) (5,5) (5,2) (5,6) (5,3) (5,7)

P0 P1 P2 P3

P4 P5 P6 P7

P8 P9 P10 P11

P12 P13 P14 P15

Répartition par BlocsRéguliers d’éléments consécutifs

Répartition par Blocscyclique


72

Transposition de Matrice

Transposition d’une matrice nxn est une matrice AT

AT [i,j] = A [j,i] pour 0 ≤ i,j ≤ n

On suppose que le temps nécessaire à l’échange (transposition) de deux éléments est égal à une unité ,

Le temps d’exécution de la solution séquentielle est égal à :

Ts = (n2 – n) / 2


73

Transposition de Matrice ( Grille n x n)

Exemple : Transposition d’une matrice 4x4 sur une grille carrée de 16 processeurs

P0 P1 P2 P3

P4 P5 P6 P7

P8 P9 P10 P11

P12 P13 P14 P15

(0,0) (0,1) (0,2) (0,3)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3)

(3,0) (3,1) (3,2) (3,3)

Etapes de communication

Nombre de processeurs égalà n2 (nombre de données)


74


Phase 1

P0 P1 P2 P3

P4 P5 P6 P7

P8 P9 P10 P11

P12 P13 P14 P15

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7)

(1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)

(2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7)

(3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7)

(4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7)

(5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7)

(6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7)

(7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7)

Etapes de communication

Nombre de processeurs p Inférieur au nombre de donnéesà n2 : ( p ≤ n2 )

Solution en deux phases :

Phase 1 : Les blocs associés aux processeurs sont considérés comme une seule valeur ==> Transposer la matrice ainsi obtenue

Phase 2 : Chaque processeur transpose localement sa sous matrice


75


Phase 2

P0 P1 P2 P3

P4 P5 P6 P7

P8 P9 P10 P11

P12 P13 P14 P15

(0,0) (0,1)

(0,2) (0,3)

(0,4) (0,5)

(0,6) (0,7)

(1,0) (1,1)

(1,2) (1,3)

(1,4) (1,5)

(1,6) (1,7)

(2,2) (2,3)

(2,4) (2,5)

(2,6) (2,7)

(3,2) (3,3)

(3,4) (3,5)

(3,6) (3,7)

(4,4) (4,5)

(4,6) (4,7)(5,4) (5,5)

(5,6) (5,7)

(6,6) (6,7)

(7,6) (7,7)

(2,0) (2,1)

(3,0) (3,1)

(4,0) (4,1)

(5,0) (5,1)

(4,2) (4,3)

(5,2) (5,3)

(6,0) (6,1)

(7,0) (7,1)

(6,2) (6,3)

(7,2) (7,3)

(6,4) (6,5)

(7,4) (7,5)

P0 P1 P2 P3

P4 P5 P6 P7

P8 P9 P10 P11

P12 P13 P14 P15

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7)

(1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)

(2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7)

(3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7)

(4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7)

(5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7)

(6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7)

(7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7)

Réarrangement local (Transposition)


76


Algorithme Récursif

(0,0) (0,1) (0,2) (0,3)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3)

(3,0) (3,1) (3,2) (3,3)

(0,4) (0,5) (0,6) (0,7)

(1,4) (1,5) (1,6) (1,7)

(2,4) (2,5) (2,6) (2,7)

(3,4) (3,5) (3,6) (3,7)

(4,0) (4,1) (4,2) (4,3)

(5,0) (5,1) (5,2) (5,3)

(6,0) (6,1) (6,2) (6,3)

(7,0) (7,1) (7,2) (7,3)

(4,4) (4,5) (4,6) (4,7)

(5,4) (5,5) (5,6) (5,7)

(6,4) (6,5) (6,6) (6,7)

(7,4) (7,5) (7,6) (7,7)

(0,0) (0,1) (0,2) (0,3)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3)

(3,0) (3,1) (3,2) (3,3)

(4,0) (4,1) (4,2) (4,3)

(4,4) (4,5) (4,6) (4,7)

(5,0) (5,1) (5,2) (5,3)

(5,4) (5,5) (5,6) (5,7)

(6,0) (6,1) (6,2) (6,3)

(6,4) (6,5) (6,6) (6,7)

(7,0) (7,1) (7,2) (7,3)

(7,4) (7,5) (7,6) (7,7)

(0,4) (0,5) (0,6) (0,7)

(1,4) (1,5) (1,6) (1,7)

(2,4) (2,5) (2,6) (2,7)

(3,4) (3,5) (3,6) (3,7)


77


Algorithme récursif

(0,0) (0,1)

(1,0) (1,1)

(2,0) (2,1)

(2,2) (2,3)

(3,0) (3,1)

(3,2) (3,3)

(4,0) (4,1)

(4,4) (4,5)

(5,0) (5,1)

(5,4) (5,5)

(6,0) (6,1)

(6,2) (6,3)

(6,4) (6,5)

(6,6) (6,7)

(7,0) (7,1)

(7,2) (7,3)

(7,4) (7,5)

(7,6) (7,7)

(0,4) (0,5)

(0,6) (0,7)

(1,4) (1,5)

(1,6) (1,7)

(2,6) (2,7)

(3,6) (3,7)

(0,2) (0,3)

(1,2) (1,3)

(4,2) (4,3)

(5,2) (5,3)

(2,4) (2,5)

(3,4) (3,5)

(4,6) (4,7)

(5,6) (5,7)

(0,0)

(0,1) (1,1)

(2,0) (3,0)

(2,2) (3,2)

(2,1) (3,1)

(2,3) (3,3)

(4,0) (5,0)

(4,4) (5,4)

(4,1) (5,1)

(4,5) (5,5)

(6,0) (7,0)

(6,2) (7,2)

(6,4) (7,4)

(6,6) (7,6)

(6,1) (7,1)

(6,3) (7,3)

(6,5) (7,5)

(6,7) (7,7)

(0,4) (1,4)

(0,6) (1,6)

(0,5) (1,5)

(0,7) (1,7)

(2,6) (3,6)

(2,7) (3,7)

(0,2) (1,2)

(0,3) (1,3)

(4,2) (5,2)

(4,3) (5,3)

(2,4) (3,4)

(2,5) (3,5)

(4,6) (5,6)

(4,7) (5,7)

(1,0)

78



Communication inter-processeurs

Opérations de base


79

Introduction et motivation

Motivations :

Identifier des opérations de base qui peuvent être combinées pour réaliser des communications plus complexes

Calculer les coûts de communication


80


Importance de la communication ou échange de données sur la performance des algorithmes parallèles

Nombre réduit de types d'opérations servant de base à la communication inter processeurs

Types de liens de communication Monodirectionnel

Bidirectionnel

Half-duplex : Communication dans une seule direction à la fois Full-duplex : Communications simultanées dans les 2 directions

PjPi

PjPi


81


Interface de communication d'un processeur Mono port, un seul port de communication

Envoi et réception simultanés de messages impossible Un seul transfert (envoi ou réception) à la fois

Multiple : un processeur a deux ou plusieurs ports de communication et peut donc être relié à plusieurs liens de communication


82


Hypothèses de communication (dans la suite)

Communication en mode Store and forward Liens duplex de communication (possibilité de communication

simultanées dans les deux sens sur un lien) Emission sur un seul lien à la fois à partir d'un processeur Réception sur un seul lien à la fois Un processeur peut émettre et recevoir un message en même

temps sur deux liens différents


83

Communication (Opérations de Base)

Opérations de base Transferts simples Diffusion de messages (Broadcast)

One-to-all broadcast sur Anneau Grille (TORE) Hypercube

All-to-all broadcast Anneau Grille (TORE) Hypercube


84

Communication de base

Transfert de message entre deux processeurs

Pi Pj

l nombre de liens traverss par le message

Coût de communication = ts + tw *m*l

ts est le temps de préparation du message

m est la longueur du message (mot ou octet)

tw est le temps de transfert d’un mot

l est le nombre de liens traversés par le message


85


Envoi d'un message de taille m d'un processeur source S vers un processeur destination D

Temps de transfert= ts + (tw)ml

ts (start up time)

tw (temps de transfert par unité de message l nombre de liens traversés par un message

Bornes supérieures du temps de transfert : Anneau, ts + (tw)m p/2 Grille, ts + (tw)m ((p)1/2)/2 Hypercube, ts + (tw)m log2p

Borne supérieure dépend du nombre maximal de liens traversés


86

Plusieurs types de transferts identifiés qui servent de base à l'échange de données inter-processeurs Transfert simple entre une source et une destination Diffusion (Broadcast) dans laquelle un message est envoyé à

plusieurs destinataires par une ou plusieurs sources One-to-all All-to-all All-to-one K-to-all


87

One-to-All broadcast

Solution naïve

Le processeur source P0 envoie le message M0 successivement aux processeurs P1, P2, … Pn-1

P1P0M0

P2P0M0

P3P0M0

Pp-1P0M0

( P0 P1 P2 )

( P0 P1 P2 P3 )

( P0 P1 P2 … Pp-1 )

Coût de communication = (ts + tw m0 ) i = (ts + tw m0 )*( p(p+1)/2)


88

One-to-all Broadcast

Un processeur source envoie le même message M à un ensemble de processeurs

Initialement : La source P0 contient le message M (taille m) Fin transfert : Plusieurs processeurs (p) ont une copie du message

d'origine

0 1 P-1 0 1 P-1

M M M M… …

One-to-all broadcast

Opération duale (Accumulation)


89

One-to-all Broadcast

Opération duale de One-to-all-Boradcast : Single-node-accumulation Chaque processeur contient un message de taille m Une opération associative est utilisée pour accumuler (aggrégation

de) les différents sur un processeur destinataire.

Single-node-accumulation peut être utilisée pour calculer Sum, Produit Maximum, minimum Opérations logiques

0 1 P-1 0 1 P-1

M M M M… …

One-to-all broadcast

Opération duale (Accumulation)


90


Deux types de diffusion de messages :

All-to-All Broadcast : Plusieurs diffusions One-to-All simultanées dans lesquels chaque processeur joue le rôle de source

0 1 p-1…X0

0 1 p-1…

All-to-All broadcast

Accumulation vers plusieurs noeuds

X1 Xp-1

…

X0

X1

Xp-1 …

X0

X1

Xp-1 …

X0

X1

Xp-1


91

One-to-All broadcast (Sur un anneau)

Solution naïve : envoyer séquentiellement (p-1) messages aux différents processeurs Coût de communication élevé Le même message traverse plusieurs fois les mêmes processeurs

Solution : chaque processeur garde une copie du message avant sa transmission vers un autre processeur

0 1 2 3

7 6 5 4

1 2 3

43

2 4

Coût de communication :

T = (ts + tw * m)p/2 où p est le nombre de processeurs


92

One-to-All broadcast (Sur un tore)

Solution en deux phases : Phase 1 : Diffusion One-to-All sure la première ligne

0

4

8

12

1

5

9

13

2

6

10

14

3

7

11

15

1 2

2


93


Solution en deux phases : Phase 2 : Chaque processeurs de la première ligne inite uune

diffusion One-to-All sur la colonne correspondante

0

4

8

12

1

5

9

13

2

6

10

14

3

7

11

15

1 2

2

3 3 3 3

4 4 4 4

4 4 4 4


94




T = 2 * (ts + tw * m) p(1/2)/ 2 2 où (p) est le nombre de processeurs

Broadcast ligne

Tcom = (ts + twm) p(1/2)/2

Broadcast colonne

Tcom = (ts + twm) p(1/2)/2


95

One-to-All broadcast (Sur un hypercube)

Solution en d phases pour un hypercube de dimension d

A chaque étape le nombre de processeurs participant à la diffusion est multiplié par

0 1

2 3

4 5

6 7

12

2

3

3

3

3


T = 2 * (ts + tw * m)*logpoù (p) est le nombre de processeurs


96

All-to-all Broadcast

Généralise la diffusion One-to-all. Permet d'initialiser p diffusion One-to-All simultanées

Chaque processeur Pi envoie un message Mi de taille mi aux autres processeurs

La diffusion All-to-all est utilisée dans plusieurs applications Produits matriciels Produit Matrice Vecteur Sommes préfixes Etc…


97


Sur un Anneau de 8 processeurs Etape 1

0 1 2 3

7 6 5 4

1(0) 1(1) 1(2)

1(3)1(7)

1(6) 1(5) 1(4)

(0) (1) (2) (3)

(4)(5)(6)(7)


98



0 1 2 3

7 6 5 4

2(7) 2(0) 2(1)

2(2)2(6)

2(5) 2(4) 2(3)

(0,7) (1,0) (2,1) (3,2)

(4,3)(5,4)(6,5)(7,6)


99



0 1 2 3

7 6 5 4

3(6) 3(7) 3(0)

3(1)3(5)

3(4) 3(3) 3(2)

(0,7,6) (1,0,7) (2,1,0) (3,2,1)

(4,3,2)(5,4,3)(6,5,4)(7,6,5)


100



0 1 2 3

7 6 5 4

7(2) 7(3) 7(4)

7(5)7(1)

7(0) 7(7) 7(6)

(0,7,6,5,4,3,2) (1,0,7,6,5,4,3) (2,1,0,7,6,5,4) (3,2,1,0,7,6,5)

(4,3,2,1,0,7,6)(5,4,3,2,1,0,7)(6,5,4,3,2,1,0)(7,6,5,4,3,2,1)


101


Sur un Anneau de 8 processeurs

Après (p-1) étapes, chaque processeur Pi a recu tous les messages A l'étape i, un transfert de message (taille m) est envoyé d'un

processeur vers un processeur directement connecté. Le coût Ti de ce transfert est

Ti = ts + tw m

Coût total :

Total : Tcom = Ti = (p-1) (ts + twm)


102


Algorithme pour un anneau de p processeurs

Processeur i Input : message, mon-idOutput : Messages diffusésBegin

gauche = (mon-id – 1) mod p;droite = (mon-id + 1) mod p;résultat = messagemess = messagefor i = 1 to p-1 do begin

send (mess, droite)receive (mes, gauche)résultat = résultat messendfor

End


103


Sur une TORE 2D

La diffusion se fait en deux phases : Une diffusion All-to-all sur chaque ligne de la grille. A la fin de cette

étape chaque processeur Pi détient un message Mi de taille égale à (p1/2)m

Une diffusion All-to-all sur les colonnes de la grille


104


Diffusion All-to-all sur une TORE 2D 3X3 de 9 processeurs

0 1 2

3 4 5

6 7 8

(0) (1) (2)

(3) (4) (5)

(6) (7) (8)

Diffusions All-to-All sur Chaque ligne

Début Phase 1


105



0 1 2

3 4 5

6 7 8

(0,1,2) (0,1,2) (0,1,2)

(3,4,5) (3,4,5) (3,4,5)

(6,7,8) (6,7,8) (6,7,8)

Diffusions All-to-All sur Chaque ligne

Début Phase 2


106



Coût de communication

Total = Coût phase 1 + coût phase 2

= (p1/2 -1)(ts + twm) + (p1/2-1) (ts + tw (p1/2)m)

Documents

Modèles de Parallélisme