Parallel Algorithms (PDF)

Arhitecturi Paralele Abordări probleme paralele log(N) Prof. Ciprian Dobre [email protected] Sume prefix  Aplicații folosind paralelismul de date Calculul sumelor prefix Problemă: Se dă tabloul a[1:n], se cere s[1:n], unde:...

Arhitecturi Paralele Abordări probleme paralele log(N) Prof. Ciprian Dobre [email protected] Sume prefix  Aplicații folosind paralelismul de date Calculul sumelor prefix Problemă: Se dă tabloul a[1:n], se cere s[1:n], unde: 𝒔 𝒊 = σ𝒊𝒌=𝟏 𝒂[𝒌]  Algoritm secvențial: s = a; for [i = 2 to n] s[i] = a[i] + s[i-1];  Algoritm paralel: - derivat din algoritmul sumei elementelor unui vector  Suma elementelor unui vector 7 ෍ 0 3 7 ෍ ෍ 0 4 1 3 5 7 ෍ ෍ ෍ ෍ 0 2 4 6 0 1 2 3 4 5 6 7 𝑛 sup procesoare, sup log2 𝑛 pași 2  Suma elementelor unui vector a1 a2 a3 a4 a5 a6 a7 a8 a1 𝒔𝟐𝟏 a3 𝒔𝟒𝟑 a5 𝒔𝟔𝟓 a7 𝒔𝟖𝟕 Timp a1 𝒔𝟐𝟏 a3 𝒔𝟒𝟏 a5 𝒔𝟔𝟓 a7 𝒔𝟖𝟓 a1 𝒔𝟐𝟏 a3 𝒔𝟒𝟏 a5 𝒔𝟔𝟓 a7 𝒔𝟖𝟏  Suma elementelor unui vector int a[1:n]; process suma[k=1 to n] { // suma proceselor p din figura for [j = 1 to sup(log2 𝑛)] { if (k mod 2j == 0) a[k] = a[k-2j-1] + a[k]; barrier; } p1 p2 p3 p4 p5 p6 p7 p8 } a1 a2 a3 a4 a5 a6 a7 a8 a1 𝒔𝟐𝟏 a3 𝒔𝟒𝟑 a5 𝒔𝟔𝟓 a7 𝒔𝟖𝟕 Timp a1 𝒔𝟐𝟏 a3 𝒔𝟒𝟏 a5 𝒔𝟔𝟓 a7 𝒔𝟖𝟓 a1 𝒔𝟐𝟏 a3 𝒔𝟒𝟏 a5 𝒔𝟔𝟓 a7 𝒔𝟖𝟏  Sume prefix (varianta 1) a1 a2 a3 a4 a5 a6 𝒔𝟏𝟏 𝒔𝟐𝟏 𝒔𝟑𝟐 𝒔𝟒𝟑 𝒔𝟓𝟒 𝒔𝟔𝟓 Timp 𝒔𝟏𝟏 𝒔𝟐𝟏 𝒔𝟑𝟏 𝒔𝟒𝟏 𝒔𝟓𝟐 𝒔𝟔𝟑 𝒔𝟏𝟏 𝒔𝟐𝟏 𝒔𝟑𝟏 𝒔𝟒𝟏 𝒔𝟓𝟏 𝒔𝟔𝟏  Sume prefix – varianta 1 int a[1:n]; process suma[k=1 to n] { for [j = 1 to sup(log 2 𝑛)] { if (k - 2j-1 >= 1) a[k] = a[k-2j-1] + a[k]; barrier; a1 a2 a3 a4 a5 a6 } } 𝒔𝟏𝟏 𝒔𝟐𝟏 𝒔𝟑𝟐 𝒔𝟒𝟑 𝒔𝟓𝟒 𝒔𝟔𝟓 𝒔𝟏𝟏 𝒔𝟐𝟏 𝒔𝟑𝟏 𝒔𝟒𝟏 𝒔𝟓𝟐 𝒔𝟔𝟑 Eroare de sincronizare… 𝒔𝟏𝟏 𝒔𝟐𝟏 𝒔𝟑𝟏 𝒔𝟒𝟏 𝒔𝟓𝟏 𝒔𝟔𝟏  Sume prefix – varianta 1 – probleme Presupunem că procesorul numărul 3 este mai lent decât restul. Suprascriere a locației de memorie a1 𝒔a𝟐𝟏2 a3 a4 a5 a6 𝒔𝟐𝟏 𝒔𝟑𝟐 𝒔𝟒𝟑 𝒔𝟓𝟒 𝒔𝟔𝟓 𝒔𝟑𝟐 = 𝒂𝟑 + 𝒔𝟐𝟏  Sume prefix – varianta 2 int a[1:n], temp[1:n]; process suma[k=1 to n] { for [j = 1 to sup(log2 n)] { temp[k] = a[k]; barrier; if (k - 2j-1 >= 1) a[k] = temp[k-2j-1] + a[k]; barrier; } a1 a2 a3 } 𝒕𝟏 𝒕𝟐 𝒔𝟐𝟏 𝒔𝟑𝟐  Sume prefix – varianta 3 int a[1:n], temp[1:n]; process suma[k:1 to n] { int d = 1; while (d < n) { temp[k] = a[k]; barrier; if (k – d >= 1) a[k] = temp[k-d] + a[k]; barrier; d = 2 * d; } } Parallel Scan  Parallel Scan scan (o) < x1,..., xn > == < x1, x1 o x2,..., x1 o... xn > Exemplu: Filtru Considerați la intrare un vector, trebuie găsit la ieșire un alt vector care să conțină doar elementele pentru care (f elt) este true Fie f x = x > 10 filter f < 17, 4, 6, 8, 11, 5, 13, 19, 0, 24 > = < 17, 11, 13, 19, 24 > Paralelizabil? - Găsirea elementelor este o operație ușoară - Dar punerea lor în secvența corectă pare mai dificilă  Prefixe paralele - to the rescue 1. Folosim mapare paralelă pentru a calcula un bit-vector pentru elementele ce se potrivesc operației input: < 17, 4, 6, 8, 11, 5, 13, 19, 0, 24 > bits: < 1, 0, 0, 0, 1, 0, 1, 1, 0, 1 > 2. Aplicăm sume prefix pe elementele bit-vectorului bitsum < 1, 1, 1, 1, 2, 2, 3, 4, 4, 5 > 3. Aplicăm parallel map pentru a produce ieșirea output < 17, 11, 13, 19, 24 >  Generic: Scan Se aplică aceeași operație între elementele unui vector. Se colectează toate rezultatele parțiale Poate fi executat în log(n) pași folosind un arbore Operația poate lua orice formă (+, *, min, max, and, etc.)  Scan - sum 9 4 2 7 3 5 6 1 + + + + + + + 9 13 15 22 25 30 36 37  Scan - sum 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 Pot fi executate în paralel  Scan - sum 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 Pot fi toate executate în paralel  Scan - sum 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37 Pot fi toate executate în paralel  Scan – Cum funcționează? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – Cum funcționează 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – Cum funcționează? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – Cum funcționează? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37  Scan – How it works? 9 4 2 7 3 5 6 1 9 13 6 9 10 8 11 7 9 13 15 22 16 17 21 15 9 13 15 22 25 30 36 37 Difuzarea unei valori  Difuzarea unei valori – justificare O(log P) ▪ D – celula din memoria comună ce trebuie difuzată ▪ Folosim un tablou A[1:N] procedure BROADCAST (D, N, A) Pas 1: Procesorul P1 1.1. citește valoarea din D 1.2. o memorează în propria memorie 1.3. o scrie în A Pas 2: fa i = 0 to (log N -1) -> fa j = 2i+1 to 2(i+1) do in parallel Procesor Pj 2.1. citește valoarea din A[j-2i] 2.2. o memorează în propria memorie 2.3. o scrie în A[j] af af  Difuzarea unei valori 1 2 3 4 5 6 7 8 15 15 15 15 15 15 15 15  Operații cu vectori – broadcast Pas 1: (Procesorul P1) int t; t = D; A = t; Pas 2: for [i = 0 to (log N -1)] { process Pj[j = 2i+1 to 2i+1]{ int t; t = A[j-2i]; A[j] = t; } }  Value Broadcast Start 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7...  Value Broadcast End 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7...  Inefficient Value Broadcast O(n) time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7.............  Efficient Value Broadcast Every element that has the value copies it to its current position + i i=1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7...  Efficient Value Broadcast Every element that has the value copies it to its current position + i i=2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7... These operations can be executed in parallel  Efficient Value Broadcast Every element that has the value copies it to its current position + i i=4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7 7 7... These operations can be executed in parallel  Efficient Value Broadcast Every element that has the value copies it to its current position + i i=8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7 7 7 7 7 7 7... These operations can be executed in parallel  Efficient Value Broadcast O(log2(n)) time with p = n/2 processors 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7...  Efficient Value Broadcast i=2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7... These operations canNOT be executed in parallel i=4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7 7 7...  Efficient Value Broadcast i=2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7... i=4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... 7 7 7 7... Operații cu liste  Operații cu liste ▪Listă n elemente: data[1:n] ▪Legăturile între elemente: leg[1:n] ▪Capul listei: cap ▪Elementul i face parte din listă  fie ‒ cap = i ‒ există un element j, între 1 și n, a.î. leg[j]=i cap 3 4 2 5 0 Date Date Date Date Date 1 2 3 4 5 ▪Problemă: vrem ca fiecare procesor să afle capătul listei  Operații cu liste int leg[1:n], end[1:n]; process Află[i=1 to n] { int nou, d=1; end[i] = leg[i]; barrier; while (d