capitolul 5 exemple de algoritmi paraleli. proiectare si analiza

Capitolul 5 Exemple de algoritmi

paraleli.Proiectare si analiza.

Prelucrare de matrici/masive regulate de date

• Caracteristici: structuri masive regulate de date (tip matrice) => descompunere de date

• Scop: algoritm paralel eficient, cost-optimal, scalabil• Puncte de variabilitate a solutiei:

– Descompunere• 1D• 2D• 3D

– Granularitate: • P=n• P<n;

– Distributie: pe blocuri, ciclica• Exemple:

– Inmultirea matrice-vector– Sistem de n ecuatii liniare– Modelarea bazata pe diferente finite

Operatie Timp

One-to-one ts+m*tw

One-to-all broadcast

All-to-one reduction (ts+m*tw)*log(p)

All-to-all broadcast

All-to-all reduction ts* log(p) + tw*m*(p-1)

Reminder: performantele operatiilor pentru comunicatii colective

Exemplul 1

Inmultire matrice*vector

Inmultirea matrice-vector

Timpul de executie secvential Ts=W=n*n

Inmultirea matrice-vector: paralelizare prin descompunere de date 1D pe linii

• Se presupune ca dimensiunea matricii este n*n si se utilizeaza p<n procese

• Fiecare proces Pi detine n/p linii ale matricii A si n/p elemente ale vectorului x si calculeaza n/p elemente ale rezultatului

y[i]=sumj=0,n-1(A[i,j]*x[j]), n/p valori ale lui i• Fiecare proces Pi are nevoie de toate elementele

vectorului x => acestea sunt distribuite printr-o operatie de tip all-to-all broadcast intre p procese, cu mesaje de lungime n/p

• Difuzarea vectorului x prin operatia all-to-all broadcast: – Tbroadc= ts* log(p) + tw*m*(p-1), m=n/p

– Tbroadc≈ ts* log(p) + tw* n

• Fiecare proces Pi: n*n/p calcule• Timpul de executie paralel:

– Tp=Tbroadc+Tpi=n*n/p + ts* log(p) + tw* n

• Cost=Tp*p= n*n + ts* p*log(p) + tw* n*p

• Alg cost-optimal (Cost=O(Ts)): daca p=O(n)• Eficienta E=S/p=Ts/(p*Tp)

• E=n*n/(n*n+ts* p*log(p) + tw* n*p)

Evaluarea performantelor – cazul 1D cu p<n procese

• Analiza scalabilitatii: calculul functiei de izoeficienta

• To=Cost-W= ts* p*log(p) + tw* n*p

• W(p)=K*To(W,p)• W=K*(ts* p*log(p) + tw* n*p)

• W=n*n• Rezulta ecuatie de grd 2 in n: n*n-b*n-c=0• => n functie de p (n=O(b)) => n*n functie de p

• W=O(p*p)

Evaluarea performantelor – cazul 1D cu p<n procese

Inmultirea matrice-vector: paralelizare prin descompunere de date 2D

• p<n*n procese, organizate sub forma de masiv bidimensional

• Fiecare proces detine un bloc de dimensiune n/sqrt(p)*n/sqrt(p)

• Elementele vectorului x sunt initial distribuite in blocuri de dimensiune n/sqrt(p) intre procesele din ultima coloana

• Fiecare bloc j trebuie sa fie difuzat tuturor proceselor de pe coloana j (sqrt(p) operatii simultane de one-to-all broadcast pe fiecare coloana, de n/sqrt(p) valori per mesaj)

• Dupa efectuarea inmultirilor, rezultatele acestora trebuie adunate pe linii (all-to-one reduction)

Evaluarea performantelor – cazul 2D cu p<n*n procese

• Comunicare: – One-to-one communication (alinierea pe diagonala

a lui x): ts+tw*n/sqrt(p)– One-to-all broadcast (difuzarea fiecarui x[j] pe

coloana j): (ts+tw*n/sqrt(p))*log(sqrt(p))– All-to-one reduction (insumarea pe linii):

(ts+tw*n/sqrt(p))*log(sqrt(p))

• Calcule: n*n/p• Tp≈n*n/p+ts*log(p)+tw*n/sqrt(p)*log(p)

• Analiza scalabilitatii: calculul functiei de izoeficienta

• To=Cost-W=p*Tp-W= ts*p*log(p)+tw*n*sqrt(p)*log(p)• W(p)=K*To(W,p)

• W=K*(ts*p*log(p)+tw*n*sqrt(p)*log(p))• W=n*n

• Rezulta o ecuatie de grd 2 in n => n => W=n*n

• W=O(p*log(p)*log(p))

Evaluarea performantelor – cazul 2D cu p<n*n procese

Comparatia solutiilor: partitionare 1D vs. 2D

• Timpul paralel de executie:– Solutia 1D: Tp=n*n/p + ts* log(p) + tw* n– Solutia 2D: Tp≈n*n/p+ts*log(p)+tw*n/sqrt(p)*log(p)– La utilizarea aceluiasi numar p de procese, solutia 2D este

mai rapida– Solutia 1D poate utiliza maxim n procese– Solutia 2D poate utiliza maxim n*n procese

• Scalabilitate:– Solutia 1D: W=O(p*p)– Solutia 2D: W=O(p*log(p)*log(p))– Solutia 2D este mai scalabila

Exemplul 2

Inmultirea matrice*matrice

Inmultire matrice*matrice • Matrici dense de dimensiune n x n : C =A x B.

• Complexitatea seriala este O(n3).

• Operatii matriceale pe blocuri: o matrice A de n*n elemente este echivalenta cu o matrice de q*q blocuri Ai,j (0 ≤ i, j < q) unde fiecare bloc este o submatrice de dimensiune (n/q) x (n/q)

• Se executa q3 inmultiri de matrici de dimensiune (n/q) x (n/q)

Inmultire matrice*matrice: paralelizare prin descompunere de date 2D

• Matricile A si B de dimensiune n*n se partitioneaza 2D in p blocuri Ai,j si Bi,j (0 ≤ i, j < ) de dimensiune

• Fiecare proces Pi,j detine initial Ai,j si Bi,j si calculeaza blocul Ci,j al matricii rezultat

Inmultire matrice*matrice: paralelizare prin descompunere de date 2D

• Pentru calculul submatricii Ci,j este nevoie de toate submatricile Ai,k si Bk,j pentru 0 ≤ k < .

• All-to-all broadcast blocuri din A pe linii si blocuri din B pe coloane.

• Inmultirea submatricilor (blocurilor) se face local

Evaluarea performantelor• Operatiile de broadcast pe linii si pe coloane: participa

procesoare si se transmit n*n/p cuvinte: • Calculele pe care le realizeaza fiecare proces:

inmultiri de matrici de dimensiune

• Timpul paralel este aprox

• Algoritmul este cost optimal pentru p=O(n*n)• Functia de izoeficienta W=O(p1.5) • Dezavantaj major al algoritmului: fiecare proces va

memora la sfarsitul operatiilor de broadcast blocuri => se utiliz de ori mai multa memorie decat secv

• Matricile A si B de dimensiune n*n se partitioneaza 2D in p blocuri Ai,j si Bi,j (0 ≤ i, j < ) de dimensiune

• Fiecare proces Pi,j detine initial Ai,j si Bi,j si calculeaza blocul Ci,j al matricii rezultat

• Se urmareste ca fiecare proces sa nu detina in memoria locala mai mult de un bloc din A si un bloc din B la fiecare moment

• Se schimba ordinea calculului termenilor, astfel incat pentru orice linie i, la un moment dat, toate procesele utilizeaza un bloc diferit Ai,k.

• Blocurile Ai,k sunt rotite intre procesele de pe o linie, dupa fiecare inmultire de blocuri

• Analog pentru blocurile Bkj pe coloane• Este nevoie de un pas de initializare, in care fiecare proces

primeste perechea sa de start Ai,k si Bkj

Inmultire matrice*matrice: algoritmul lui Cannon

1. Se aliniaza blocurile lui A si B astfel incat fiecare proces sa detina blocurile pe care le inmulteste. Alinierea se face shift-and pe linii toate blocurile Ai,j la stanga cu i pozitii si toate blocurile Bi,j pe coloane in sus cu j pozitii.

2. Executa inmultirea blocurilor in fiecare proces.

3. Fiecare bloc din A se shift-eaza cu o pozitie la stanga si fiecare blod din B se shift-eaza cu o pozitie in sus

4. In fiecare proces, executa inmultirea blocurilor curente si aduna la rezultatul partial.

5. Repeta pasii 3 si 4 pentru toate cele perechi de blocuri

Inmultire matrice*matrice: algoritmul lui Cannon

Evaluarea performantelor - Algoritmul lui Cannon

• Pasul de aliniere initiala a blocurilor: – distanta maxima de shiftare este – Cantitatea de date transportata = un bloc – Timpul necesar pentru cele 2 shiftari:

• Cei pasi de calcul: – Inmultirea blocurilor: – Shift-are.

• Timpul de calcul paralel:

• Din punct de vedere al costului si izoeficientei, algoritmul lui Cannon se comporta ca si varianta simpla anterioara

• Algoritmul lui Cannon este optimal din punct de vedere al necesarului de memorie

• Limitarile algoritmilor care utilizeaza partitionari 2D: – Se pot utiliza maximum n2 procese– Oricat s-ar imbunatati algoritmul paralel de inmultire, nu poate

depasi performanta paralela de O(n), deoarece W=O(n3)

• Algoritmul DNS: utilizeaza o partitionare 3-D bazata pe partitionarea datelor intermediare

• Exista n3 inmultiri A[i,k]*B[k,j] => acestea vor fi efectuate in paralel de n3 procese Pi,j,k

• Fiecare element C[i,j] al rezultatului se obtine insumand rezultatele partiale de la cele n procese P i,j,k , 0<=k<n. Insumarea se poate face paralel in O(log n) => inmultirea matricilor in paralel poate fi facuta in principiu in O(log n)

Inmultire matrice*matrice: algoritmul Dekel-Nassimi-Sahni DNS

p=n3 procesoare• Procesoarele sunt organizate sub forma unui cub• Initial fiecare procesor din planul orizontal k=0 detine

perechea de elemente Aij si Bij• Elementele trebuie replicate pe celelalte plane k, astfel :

– orice Pijk sa detina Aik si Bkj– Valoarea Aik trebuie sa se gaseasca pe toata linia i din planul k– Valoarea Bkj trebuie sa se gaseasca pe toata coloana j din planul k

• Aranjarea elementelor se obtine astfel:– Muta elementul Aij din planul k=0 Pi,j,0 in planul k=j Pi,j,j

– Difuzeaza one-to-all broadcast elementul Aij pe toata linia i din planul sau

– Analog pentru B


Evaluarea performantelor – algoritmul DNS cu p=n3 procesoare• Fiecare procesor calculeaza o adunare. Aceasta este

urmata de o insumare pe axa k – insumarea se poate face sub forma unei operatii de all-to-one reduction

• Timpul paralel este dat de timpii de comunicare:– Mutarea coloanelor lui A si a liniilor lui B– One-to-all broadcast pe axa j pentru A si one-to-all broadcast pe

axa i pentru B– All-to-one reduction pe axa k– Fiecare dintre aceste operatii este O(log n)

• TP=O(log n)Nu este cost-optimal

p=q3 <n3 procesoare

• Matricile sunt partitionate in blocuri de (n/q) x(n/q).

• Algoritmul descris anterior se adapteaza astfel incat lucreaza cu blocuri in loc de elemente


• Mutarea liniilor si coloanelor in alte plane: one-to-one communication

• Difuzarile in plane: one-to-all broadcasts

• Insumarea prin all-to-one reduction . • Inmultirea a doua blocuri de dimensiune

dureaza • Timpul paralel este aproximativ:

• Algoritmul este cost-optimal pentru p=O(n3/(log n)3)

Evaluarea performantelor – algoritmul DNS cu p=q3<n3 procesoare

Exemplul 3

Rezolvarea sistemelor de ecuatii liniare

Rezolvarea unui sistem de n ecuatii cu n necunoscute

111,111,100,1

111,111,100,1

011,011,000,0

...

...

...

...

nnnnnn

nn

nn

bxaxaxa

bxaxaxa

bxaxaxa

bxA Etapele rezolvarii sistemului prin metoda Gauss de eliminare:1. Reducerea sistemului la o forma tridiagonala2. Substitutia regresiva

Reducerea sistemului la o forma tridiagonala

11

111,11

011,011,00

...

...

...

nn

nn

nn

yx

yxux

yxuxux

algebrice operatii de serie o-printr forma aceasta la aduce se Sistemul

superioara ra triangulamatrice Uunde

yxUbxA

Exemplu eliminare Gaussiana – etapa 1

6433

57223

5223

762422

3210

3210

3210

3210

xxxx

xxxx

xxxx

xxxx

262

5724

14 2

3812

32

321

1

3210

xx

xxx

x

xxxx

Ec1 se imparte la 2

Din Ec2 se scade 1*Ec1




262

5024

7

3812

32

32

1

3210

xx

xx

x

xxxx

Ec2 se imparte la 2

Din Ec3 se scade -Ec2


262

5724

14 2

3812

32

321

1

3210

xx

xxx

x

xxxx


5.135.1

5.125.0

7

38 12

3

32

1

3210

x

xx

x

xxxx

Ec3 se imparte la -4

Din Ec4 se scade Ec3

262

5024

7

3812

32

32

1

3210

xx

xx

x

xxxx

Exemplu substitutii regresive

5.135.1

5.125.0

7

38 12

3

32

1

3210

x

xx

x

xxxx

Pentru un sistem de ecuatii adus la forma tridiagonala:

6:ec1In

7:ec2In

8:ec3In

9 :ec4Din

0

1

2

3

x

x

x

x

Paralelizare prin descompunere 1D pe linii

• Matricea A este partitionata pe linii intre n procese: procesul Pi detine linia i a matricii pe care o transforma

• La un moment dat toate procesele executa aceeasi iteratie k• Exista dependente de date intre instructiunile 12 (scadere) si 6 (impartire)

P0

P1

P2

Pn-1

impartire

scadere

scadere

scadere

impartire

scadere

scadere

K=0 K=1 K=2

impartire

scadere

Evaluarea performantelor - descompunere 1D pe linii

• Intr-un pas k:– Calcule impartire (instructiunile 5-6): Procesul Pk:

n-k-1 operatii aritmetice de impartire– Calcule scadere (instructiunile 11-12): procesele

Pi, k<i<n: 2*(n-k-1) operatii aritmetice( de inmultire si scadere)

– Comunicare: one-to-all broadcast

Tcomm=(ts+(n-k-1)*tw)*log(n)

Evaluarea performantelor (continuare)

• Timpul total in toti pasii k:

nnntnntnnT

nknttknT

WSP

n

kWS

n

kP

log)1(2

1log)1(

2

3

log))1(()1(31

0

1

0

• Cost:

• Timpul secvential:

3

3

2nW

)log( 3 nnOCost

Descompunere 1D pe linii cu procesare pipeline

• Solutia prezentata anterior: La un moment dat toate procesele executa aceeasi iteratie k => executia iteratiei k+1 incepe dupa terminarea tuturor actiunilor iteratiei k

• Posibilitate de imbunatatire a performantei: executia iteratiei k+1 poate incepe inainte de terminarea completa a iteratiei k => algoritm pipeline

• Reguli:– Daca un proces detine date cerute de alte procese, le

transmite– Daca un proces are suficiente date pentru a executa o

secventa de calcul, o executa

P0

P1

P2

P5

Impartire0

Scadere0

Scadere0

Impartire1

P3 Scadere0

Scadere1

Scadere0 P4

Impartire2

Scadere1

Scadere0

• Operatiile one-to-all broadcast sunt inlocuite de comunicatii simple: Procesul Pk transmite procesului Pk+1 care transmite mai departe la Pk+2. In timp ce Pk+1 transmite mai departe, Pk poate deja incepe calculele.

Descompunere 1D pe linii cu procesare pipeline (cont.)

Exemplu – pipeline pentru matrice 5*5

a) P0: Impartire0

b) P0: transmite Linia0

c) P1: transmite Linia0

d) P1: Scadere0; P2: transmite Linia0

Exemplu – pipeline pentru matrice 5*5 (cont.)

e) P1: Impartire1; P2: Scadere0; P3: transmite Linia 0

f) P1: transmite Linia1; P3: Scadere0

g) P2: transmite Linia1; P4: Scadere0

h) P2: Scadere1; P3: transmite Linia1


i) P2: Impartire2; P3: Scadere1

j) P2: transmite Linia2; P4: Scadere1

k) P3: transmite Linia2;

l) P3: Scadere2


m) P3: impartire3; P4: Scadere2

n) P3: transmite Linia 3

o) P3: Scadere 3

p) P4: impartire 4

Evaluarea performantelor - Descompunere 1D pe linii cu procesare pipeline

• Cazul p=n• Numarul total de pasi in pipeline: 4*(n-1) • Fiecare pas consta din una din operatiile:

– Impartire O(n)

– Scadere O(n)

– Comunicare directa O(n)

• Timpul total : Tp=O(n*n)• Cost: O(n*n*n) – varianta pipeline este cost-optimala

Partitionare 1D, pipeline, distributie pe blocuri

• Se utilizeaza p<n procese

• Fiecare proces detine n/p linii succesive

• Descompunere 1D, procesare pipeline

• Se schimba raportul dintre timpul de comunicare si timpul de calcul:– Impartire: (n-k-1)*n/p operatii, O(n*n/p)– Scadere: 2*(n-k-1)*n/p operatii, O(n*n/p)– Comunicare directa: (n-k-1) cuvinte, O(n)

Evaluarea performantelor – partitionare 1D, pipeline, cu distrib pe blocuri

inactive repededevin

mici) indicii la (de procese multe :Cauza

! optimal-cost estenu

)! comunicare de seama nu tine (si

/)1(2

:)comunicare de timpulignorand

aaproximeaz (se paralel calcul de Timpul

3

1

0

3

nTpCost

p

npnknT

P

n

kP

Partitionare 1D, pipeline, distributie ciclica

• Linia i => procesul i%4

Evaluarea performantelor – partitionare 1D, pipeline, cu distrib ciclica

• Distributie ciclica:– Diferenta dintre incarcarea intre procese: cel mult

o linie O(n) operatii– Suprasarcina (overhead) cumulata datorata

inactivitatii: O(n*n*p)

• Distributie pe blocuri:– Suprasarcina cumulata datorata inactivitatii:

O(n*n*n)

Paralelizare prin descompunere 2D, p=n*n

• Matricea A este partitionata pe un masiv de n*n procese procesul Pi,j detine elementul Ai,j a matricii pe care o transforma

• In iteratia k (zona activa din matrice este formata din linile k:n, coloanele k:n):

a) Pe fiecare linie i din zona activa (k<=i<n), difuzeaza A[i,k] pe linie celor n-k procese

b) Pentru linia k, realizeaza impartirea A[k,j] :=A[k,j]/A[k,k], k<j<n

c) Pe fiecare coloana j din zona activa k<j<n difuzeaza A[k,j] celor n-k procese

d) Pentru toate elementele din zona activa, realizeaza scaderea A[i,j]:=A[i,j]-A[i,k]*A[k,j]

Evaluarea performantelor – descompunere 2D

• Intr-un pas k:a) one-to-all broadcast mesaj de lungime 1 la n-k

procese O(log(n-k))b) Calcule impartire : 1 op aritm impartirec) One-to-all broadcast mesaj de lungime 1 la n-k-1

procese O(log(n-k))d) Calcule scadere : 2 op aritm impartire si scadere

O(1)=> Operatiile de comunicare au o pondere mult

mai mare decat operatiile de calcul ! => solutia nu este cost-optimala

Paralelizare prin descompunere 2D, p=n*n, cu procesare pipeline

Iteratia k:• realizeaza impartirea elementului j de pe linia k

A[k,j] :=A[k,j]/A[k,k] in momentul in care A[k,k] a ajuns la el (nu asteapta difuzarea lui A[k,k] pe toata linia)

• Incepe difuzarea lui A[k,j] pe coloana imediat dupa ce a fost calculat (nu asteapta realizarea impartirilor pe toata linia)

• realizeaza scaderea A[i,j]:=A[i,j]-A[i,k]*A[k,j] in momentul in care A[i,k] si A[k,j] sunt disponibili

Exemplu – pipeline pentru matrice 5*5, 2D cu 25 procese

a) P00 transmite A[0,0] lui P01b) P01 realizeaza impartirea A[0,1]:=A[0,1]/A[0,0]c) P01 transmite valoarea lui A[0,0] mai departe pe linie lui P02; P01 transmite

valoarea calculata a lui A[0,1] pe coloana lui P11; P10 transmite A[1,0] lui P11

d) P02 realizeaza impartirea A[0,2]:=A[0,2]/A[0,0]; P[1,1] calculeaza scaderea A[1,1]:=A[1,1]-A[1,0]*A[0,1]

Exemplu – pipeline pentru matrice 5*5, 2D cu 25 procese (cont.)

Avansul fronturilor de comunicatii:

Iteratia k=0Iteratia k=1Iteratia k=2

Avansul fronturilor de calcul:

Iteratia k=0Iteratia k=1Iteratia k=2

• Toate procesele care executa operatii de comunicare respectiv de calcul in cadrul unei iteratii se gasesc aliniate pe o diagonala formand un front care se deplaseaza cu o pozitie inspre coltul dreapta-jos la fiecare pas

• Un pas din pipeline: o impartire, o scadere sau o comunicare cu un proces vecin => O(1)

• Frontul k=0: pleaca din P[0,0] spre P[n-1, n-1], ajunge in 4*n pasi • Fiecare front k+1 este cu o linie diagonala in urma frontului k =>

se termina cu 2 pasi in urma predecesorului sau• Frontul k=n-1 (ultimul front): se termina dupa 2*(n-1) pasi dupa

frontul k=0• Total: 6*n pasi a O(1)• Tp= O(n)• Cost = O(n*n*n) = W

Evaluarea performantelor – descompunere 2D, p=n*n, pipeline

• Partitionare 2D pe blocuri

• P procese organizate intr-un masiv sqrt(p)*sqrt(p)

• Reduce comunicatiile interprocese• Difuzeaza A[i,k] (n/sqrt(p) cuvinte) pe linie celor

sqrt(p) procese• Difuzeaza A[k,j] (n/sqrt(p) cuvinte) celor sqrt(p)

procese

Descompunere 2D, p<n*n

Evaluarea performantelor – descompunere 2D, distributie pe blocuri

• Un proces care contine o parte activa a matricii: executa n*n/p operatii de calcul, comunica n/sqrt(p) cuvinte pe linie si n/sqrt(p) cuvinte pe coloana

• Daca p << n*n, operatiile de calcul au o pondere mai importanta decat comunicatiile => Tp= O(n*n*n/p), Cost= O(n*n*n)

• Surplusul se datoreaza in mare masura incarcarii inegale a proceselor care duce la procese inactive in coltul stanga-sus al masivului de procese

Comparatia solutiilor: partitionare 1D vs. 2D

• Timpul paralel de executie:– Pentru acelasi numar de procese p:– Partitionare 1D, procesare pipeline:

• Tp=O(n*n*n/p)

– Partitionare 2D:• Tp=O(n*n*n/p)

• Scalabilitate: – Partitionarea 2D permite utilizarea unui numar mai

mare de procese (n*n)

Rezolvarea sistemelor de ecuatii liniare

• Etapa 2: substitutii regresive

Paralelizarea substitutiilor regresive

• Descompunere 1D• Descompunere 2D

Exercitiu !

Rezolvarea sistemelor de ecuatii liniare in practica

• Problema: daca in matricea coeficientilor exista A[k,k]=0, alg de eliminare gaussiana nu se poate aplica => se aplica tehnica pivotarii

• Exista si alti algoritmi mai performanti decat eliminarea Gaussiana

capitolul 5 exemple de algoritmi paraleli. proiectare si analiza

Documents