Tipp: a diák között a J és K billentyűkkel lehet lépkedni.
Letöltés
Párhuzamos és Grid rendszerek
(9. ea)
Párhuzamos algoritmusok tervezése, vizsgálata
Szeberényi Imre
BME IIT
<szebi@iit.bme.hu>
A San Diego Supercomputer Center
oktatási anyagának felhasználásával.
M
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
EGYETEM 1782
2013.04.08.
-1-
PRAM modell
• Parallel Random Access Machine (PRAM)
• Elméleti modell a az algoritmusok
vizsgálatához
Célja:
• Algoritmusok osztályozása,
komplexitásának vizsgálata.
• Párhuzamosíthatóság elvi határainak
felfedése.
• Új algoritmusok kifejlesztése.
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
-2-
PRAM modell /2
• Végtelen memória és
processzorszám
• Nincs direkt kommunikáció a
processzorok között:
– csak a memóriában
kommunikálhatnak
– aszinkron m ködés ek
• A processzorok tetsz legesen
hozzáférnek a memóriához.
• Hozzáférés 1 ciklus
• Tipikusan minden processzor
ugyanazt az algoritmust hajtja
végre. (read, compute, write)
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
P1
P2
P3
.
.
.
Shared
Memory
PN
2013.04.08.
-3-
Memória hozzáférés
A modell több hozzáférési módot
támogat:
• Exclusive Read (ER)
• Concurrent Read (CR)
• Exclusive Write (EW)
• Concurrent Write (CW)
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
-4-
Klasszikus PRAM modellek
• CREW (concurrent read, exclusive write)
– leginkább használt
• CRCW (concurrent read, concurrent write)
– legjobb teljesítmény
• EREW (exclusive read, exclusive write)
– leginkább megszorító
– legrealisztikusabb
• CROW (concurrent read, owner write)r write
• Common CRCW, Priority CRCW, …
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
-5-
PRAM példa #1
• Feladat:
– Határozzuk meg egy láncolt lista hosszát
– Minden listaelemben van egy változó (h), ami a
mögötte lev lista hosszát mutatja
if next[i] = NULL then h[i] ← 0
else h[i] ← h[next[i]] + 1 fi
• A soros algoritmus O(n) komplexitású
• Az alábbi PRAM algorithmus O(log n) kompl.
– miden listaelemhez rendeljünk egy processzort;
– miden processzor 1. lépésben végezze el a következ t:
if next[i] = NULL then h[i] ← 0
else h[i] ← 1 fi
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
-6-
PRAM példa #1 /2
A további lépesekben pedig:
if next[i] ≠ NULL then h[i] ← h[i] + h[next[i]]
next[i] ← next[next[i]] fi
1
1
1
1
1
0
2
2
2
2
1
0
4
4
3
2
1
0
5
4
3
2
1
0
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
A lista mérete
mindig 2-vel
osztódik
2013.04.08.
-7-
PRAM példa #1 /3
Algoritmus:
forall i do
if next[i] = NULL then h[i] ← 0 else h[i] ← 1 fi
mindaddig amíg van olyan i next[i] ≠ NULL
forall i do
if next[i] ≠ NULL then
h[i] ← h[i] + h[next[i]]
next[i] ← next[next[i]]
fi
od
od
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
-8-
Konzisztencia probléma
• Minden lépésben szinkronozottan kell történnie
next[i] ← next[next[i]]
• Ezért valójában ez történik:
forall i
A[i] ← B[i]
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
forall i
tmp[i] ← B[i]
forall i
A[i] ← tmp[i]
2013.04.08.
-9-
amíg van olyan i ...
mindaddig amíg van olyan i next[i] ≠ NULL
Hogyan hajtható végre ez ?
– CRCW: Egy változót úgy írnak a processzorok,
hogy az eredményük logikai ÉS kapcsolatba kerül.
– CREW: valami hasonló de csak 1 processzor írhat,
amib l O(log n) lépés jön ki
– Így while ciklus átirható:
for step = 1 to
log n
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 10 -
Milyen PRAM modell kell?
• Valójában nem kell a CW, csak CR:
tmp[i] ← h[i] + h[next[i]]
• A CR is megszüntethet :
tmp2[i] ← h[i]
tmp[i] ← tmp2[i] + h[next[i]]
• Végül elegend az EREW
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 11 -
Végs algoritmus
forall i do
if next[i] = NULL then h[i] ← 0 else h[i] ← 1 O(1)
for step = 1 to log n do
forall i do
O(log n)
O(log n)
if next[i] ≠ NULL then
tmp[i] ← h[i]
O(1)
h[i] ← tmp[i] + h[next[i]]
next[i] ← next[next[i]]
fi
od
od
od
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 12 -
Maximumkeresés
function smax(A,n)
m a[1]
for i 2 to n do
m
max(m, A[i])
od
return m
end
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
O(n)
2013.04.08.
- 13 -
Párhuzamos maximumkeresés
function smaxp(A,n)
for i 1 to n/2 do
B[i]
max(A[2i-1], A[2i]) O(1)
od
if n = 2 then
return B[1]
else
return smaxp(B, n/2) O(log n)
fi
end
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
O(log n)
2013.04.08.
- 14 -
Párhuzamos maximumkeresés /2
• Melyik PRAM modell?
– EREW
• Mennyi munkát (w(n)) végzünk összesen n
elem esetén p(n) processzorral?
w(n) = p(n) * t(n)
p(n) = n/2
t(n) = O(log n)
w(n) = O(n log n)
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 15 -
Párhuzamos max #2
CRCW
function smaxp2(A,n)
for i 1 to n do B[i]
1 od O(1)
for j 1 to n do
for i 1 to n do
if A[i] < A[j] then B[i]
0 fi
od
od
for i 1 to n do
O(1)
if B[i] = 1 return A[i] fi
od
end
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
O(1)
2013.04.08.
- 16 -
Prefix algoritmus
function prefix(A, n)
B[1] a[1]
for i 2 to n do
B[i] B[i-1]+A[i]
od
return B
end
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
O(n)
2013.04.08.
- 17 -
Párhuzamos prefix algoritmus
function prefixp(A, n)
B[1] a[1]
if n > 1 then
for i 1 to n/2 do O(1)
C[i] A[2i-1]+A[2i] od
D prefixp(C, n/2) O(log n)
for i 1 to n/2 do O(1)
B[2i] D[i] od
for i 1 to n/2 do O(1)
B[2i-1] D[i-1]+A[2i-1] od
fi
return B
end
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
O(log n)
2013.04.08.
- 18 -
Roots of forest
P[i] = j, ha (i, j) egy szül felé mutató él
P[i] = i, ha i gyökér
h – a legmagasabb fa magassága
for i 1 to n do
S[i] P[i]
while S[i] <> S[S[i]] do O(log h)
S[i] S[S[i]]
od
od
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
O(log h)
2013.04.08.
- 19 -
Kezdeti állapot
Els lépés
Végállapot
PRAM összefoglalás
• Algoritmusok osztályozása,
komplexitásának vizsgálata.
• Párhuzamosíthatóság elvi határainak
felfedése.
• Új algoritmusok kifejlesztése
• CRCW gyorsabb mint a EREW?
– Bizonyítható, hogy CRCW maximum O(log n)szer gyorsabb mint az EREW.
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 23 -
Rendez hálózatok
• M veleti elemek:
– két számot kapnak, és rendezve kiadják azokaz
a kimenetükön.
a
b
min(a,b)
max(a,b)
– hálózatba kötve rendezésre képesek
– alapvet en az architektúra érdekes
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 24 -
Összefésülés (merge)
Jelölések:
– (c1,c2,...,cn) rendezetlen lista
– sort(c1,c2,...,cn) rendezett lista
– sorted(x1,x2,...,xn) igaz, ha a lista rendezett
– ha sorted(a1,...,an) és sorted(b1,...,bn) akkor
merge((a1,...,an),(b1,...,bn)) = sort(a1,...,an,b1,...,bn)
A mergem hálózat két db 2m elem listát fésül össze.
m=0
m=1
b1
a1
b1
min(a1,b1)
a2
b2
a1
max(max(a1,b1),min(a2,b2))
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
min(max(a1,b1),min(a2,b2))
max(a2,b2)
2013.04.08.
- 25 -
m=2
mergem-1
a1
b1
a3
b3
2m-1db
komparátor
a2
b2
a4
b4
Az els mergem-1 a páratlan elemeket, a második
mergem-1 a párosakat rendezi, majd a 2m-1db komparátor
ezeket összefésüli.
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 26 -
Mergem el állítása
• Adott:
– sorted(a1,...,a2n) és
– sorted(b1,...,b2n)
• Legyen:
– (d1,...,d2n) = merge((a1,a3,..,a2n-1),
(b1,b3,...,b2n-1)
– (e1,...,e2n) = merge((a2,a4,..,a2n),(b2,b4,...,b2n)
• Akkor:
– sorted(d1,min(d2,e1),max(d2,e1),...,
min(d2n,e2n-1),max(d2n,e2n-1),e2n)
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 27 -
Rendez hálózat
• Sort2 network
Sort3 network
merge1
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
merge1
sort2
Sort 1st half of the list
Sort 2nd half of the list
Merge the results
Recursively
merge2
2
merge1
sort2
sort2
2013.04.08.
- 28 -
Páros-páratlan rendez hálózat
n=8
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
n=7
2013.04.08.
- 29 -
„Bizonyítás”
• Legyen (ai)i=1,..,n a rendezend lista (0 és 1)
• Legyen k db 1-es a listában; j0 pedig az utolsó 1-es
helye
1 1
0 1
0 0 0
k=3
j0 = 4
• Figyeljük meg, hogy 1-es soha nem mozog balra.
• Ha j0 is páros, akkor az utolsó 1-es csak a következ
szinten mozdul, ha j0 páratlan, akkor az els n.
• Legfeljebb n szint kell, hogy a helyére érjen.
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 30 -
Példa n=6-ra
1
0
1 0
0
1
0 1
0
1
0
0
1 0
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
1
0
2013.04.08.
- 31 -
Rendezés egydimenziós tömbbel
• Legyen p db általános célú processzorból
egy egy dimenziós tömbünk:
P1
P2
P3
....
Pp
• Tegyük fel, hogy n osztható p-vel!
• Használjuk a páros-páratlan mintát
rendezésre!
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 32 -
M ködés
• Minden processzor n/p db elemet kap.
• Ezeket lokálisan rendezi
• Majd p lépésben felváltva el bb a páratlan, majd a
páros processzorok adatot cserélnek jobboldali
szomszédjukkal.
• Minden adatcserénél az adatokat összefésülik, és
baloldali processzor a kisebb elemeket (n/p
darabot), a jobboldali processzor pedig a nagyobb
elemeket tartja meg.
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 33 -
Példa
P1
P2
P3
P4
P5
P6
init
{8,3,12}
{10,16,5}
{2,18,9}
{17,15,4}
{1,6,13}
{11,7,14}
local sort
{3,8,12}
{5,10,16}
{2,9,18}
{4,15,17}
{1,6,13}
{7,11,14}
odd
{3,5,8}
{10,12,16}
{2,4,9}
{15,17,18}
{1,6,7}
{11,13,14}
even
{3,5,8}
{2,4,9}
{10,12,16}
{1,6,7}
{15,17,18}
{11,13,14}
odd
{2,3,4}
{5,8,9}
{1,6,7}
{10,12,16}
{11,13,14}
{15,17,18}
even
{2,3,4}
{1,5,6}
{7,8,9}
{10,11,12}
{13,14,16}
{15,17,18}
odd
{1,2,3}
{4,5,6}
{7,8,9}
{10,11,12}
{13,14,15}
{16,17,18}
even
{1,2,3}
{4,5,6}
{7,8,9}
{10,11,12}
{13,14,15}
{16,17,18}
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2013.04.08.
- 34 -
