Capitolul 5 Exemple de algoritmi paraleli. Proiectare si analiza.
description
Transcript of 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
Inmultire matrice*matrice: algoritmul Dekel-Nassimi-Sahni DNS
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
Inmultire matrice*matrice: algoritmul Dekel-Nassimi-Sahni DNS
• 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
Din Ec3 se scade 3*Ec1
Din Ec4 se scade 1*Ec1
Exemplu eliminare Gaussiana – etapa 2
262
5024
7
3812
32
32
1
3210
xx
xx
x
xxxx
Ec2 se imparte la 2
Din Ec3 se scade -Ec2
Din Ec4 se scade 0*Ec2
262
5724
14 2
3812
32
321
1
3210
xx
xxx
x
xxxx
Exemplu eliminare Gaussiana – etapa 3
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
Exemplu – pipeline pentru matrice 5*5 (cont.)
i) P2: Impartire2; P3: Scadere1
j) P2: transmite Linia2; P4: Scadere1
k) P3: transmite Linia2;
l) P3: Scadere2
Exemplu – pipeline pentru matrice 5*5 (cont.)
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.)
Exemplu – pipeline pentru matrice 5*5, 2D cu 25 procese (cont.)
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