Bevezet´ es
P´ elda
Automatikus p´arhuzamos´ıt´as – egy szisztolikus p´elda
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
´ Attekint´ es
Bevezet´es P´elda – konkr´et szisztolikus algoritmus Automatikus p´arhuzamos´ıt´asi m´ odszer – ¨ otlet
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
´ Attekint´ es
Bevezet´es P´elda – konkr´et szisztolikus algoritmus Automatikus p´arhuzamos´ıt´asi m´ odszer – ¨ otlet
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
´ Attekint´ es
Bevezet´es P´elda – konkr´et szisztolikus algoritmus Automatikus p´arhuzamos´ıt´asi m´ odszer – ¨ otlet
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
Motiv´aci´o
N¨ovekv˝o ig´eny a gyors adatfeldolgoz´asra Pl. n´eh´any sz´am´ıt´asig´enyes feladatra: id˝oj´ar´as modellez´es k´ep- illetve jelfeldolgoz´as szeizmol´ogiai sz´am´ıt´asok tengeri ´aramlatok modellez´ese ... megold´asi lehet˝os´egek: a hardver t¨ok´eletes´ıt´ese – fizikai korl´atok p´arhuzamos programoz´as
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
Gyors´ıt´as
n processzor = n-szeres sebess´egn¨ oveked´es? pl. “Proc.” sz´ ama 1 ty´ uk 10 ty´ uk
Id˝ o 10 nap alatt 1 nap alatt (10-szer gyorsabban)
Feladat 10 toj´as 10 toj´as
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
Gyors´ıt´as
n processzor = n-szeres sebess´egn¨ oveked´es? pl. “Proc.” sz´ ama 1 ty´ uk 10 ty´ uk
1 n˝o 9 n˝o
Id˝ o 10 nap alatt 1 nap alatt (10-szer gyorsabban) ∗∗∗ 9 h´ onap alatt 1—————– h´ onap alatt . . .
Feladat 10 toj´as 10 toj´as
1 gyerek
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´arhuzamoss´ag p´arhuzamoss´ag megval´os´ıt´asa: a feladatot kisebb r´eszekre bontjuk az egyes r´eszfeladatokat sz´etosztjuk a processzorok k¨oz¨ott, melyek p´arhuzamosan dolgozhatnak sz¨ uks´eg van a processzorok munk´aj´anak az ¨ osszehangol´as´ara a r´eszfeladat megold´asa lehet˝ oleg ne tartson r¨ ovidebb ideig, mint ami sz¨ uks´eges a feladat kioszt´as´ahoz felmer¨ ul˝o k´erd´esek: hogyan kapcsol´odnak egym´ashoz a processzorok (milyen p´arhuzamos architekt´ ura) hogyan osszuk sz´et a feladatokat az egyes processzorok k¨oz¨ott
Bevezet´ es
P´ elda
K¨ul¨onb¨oz˝o oszt´alyoz´asi krit´eriumok. . .
Szorosan ¨osszekapcsolt rendszerek (shared memory)
Gyeng´en ¨ osszekapcsolt (sz´et)osztott rendszerek (distributed memory)
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
processzorok kapcsolatrendszere – k¨ul¨onb¨oz˝o topol´ogi´ak
Figure: Az ¨ osszek¨ ot˝ o h´ al´ ozatok “tengere” [Par:02]
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
Szisztolikus architekt´ur´ak jellemz˝ok: azonos (´altal´aban egyszer˝ u) m˝ uveleteket v´egz˝ o processzorok (PE) szab´alyos strukt´ ura, lok´alis kapcsolat a szomsz´edos PE-k k¨ozt szinkron m˝ uk¨od´es (glob´alis ´ orajelre) glob´alis be-/ kimenet (a “sz´elen” lev˝ o PE-ken kereszt¨ ul)
PE PE PE PE PE
- Mem´ oria Figure: Line´ aris szisztolikus architekt´ ura
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” eg´eszek szorz´asa (szekvenci´alis alg.) Feladat: Adott k´et eg´esz sz´am: A = am−1 am−2 . . . a1 a0 , illetve B = bn−1 bn−2 . . . b1 b0 . Sz´am´ıtsuk ki: C = cm+n−1 cm+n−2 . . . c1 c0 = A × B. a- c b
a-× b + c (a + b + c)
Figure: Processzor, mely k´epes elv´egezni k´et sz´ amjegy “´ atviteles” szorz´ as´ at (illetve osszead´ ¨ as´ at)
A szekveci´alis algoritmus bonyolults´aga: O(m × n)
Pl. A = 321, B = 987: 321 × 987 2247 2568 2889 316827
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” (tetsz˝oleges pontoss´ag´u) eg´eszek szorz´asa (online szisztolikus alg.) L´ep´es: 0
y
$ 321 987
-
$
$ $ $
$ $
$ $
hy , r i = d[1 × 7] = h7, 0i
$
$
$ $
$ $ $
$ $
-
O(m + n)
xa xb 0 - ha hb0
y
0
ha1 hb1
-xa 0 -xb
hy , r i = d[xa×xb], if s = $ 6= xa
h$, $i h$, $i, if s = $ = xa
Eredm´eny: Alg. bonyolults´aga:
r za zb
... $ $
0
s
Processzorok sz´ama: Max{m, n}/2
d[a] = ha
a mod β, b ci β
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” (tetsz˝oleges pontoss´ag´u) eg´eszek szorz´asa (online szisztolikus alg.) L´ep´es: 1
y
7 032 098
-
1
0
$
1 7 1 7
$ $
hy , r i = d[0 + 7 × 2 + 1 × 8] = h2, 2i Eredm´eny:
$ $
$ $ $
$ $
...
$ $
r za zb
-
xa xb 0 - ha hb0
y
0
ha1 hb1
-xa 0 -xb
hy , r i = d[r + hb0 × xa + + ha0 × xb], if s = 1
h$, $i h$, $i, if s = $ = xa
7
Alg. bonyolults´aga: O(m + n)
$
0
s
Processzorok sz´ama: Max{m, n}/2
d[a] = ha
a mod β, b ci β
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” (tetsz˝oleges pontoss´ag´u) eg´eszek szorz´asa (online szisztolikus alg.) L´ep´es: 2
y
2 003 009
-
2
2
$
2 8 1 7
2 8
hy , r i = d[2 + 2 × 8 + 7 × 3 + 1 × 9] = h8, 4i Eredm´eny:
$ $
$ $ $
$ $
...
$ $
r za zb
-
xa xb 0 - ha hb0
y
0
ha1 hb1
-xa 0 -xb
hy , r i = d[r + ha1 × hb1 + + hb0 × xa + + ha0 × xb], if s = 2
h$, $i h$, $i, if s = $ = xa
27
Alg. bonyolults´aga: O(m + n)
$
0
s
Processzorok sz´ama: Max{m, n}/2
d[a] = ha
a mod β, b ci β
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” (tetsz˝oleges pontoss´ag´u) eg´eszek szorz´asa (online szisztolikus alg.) L´ep´es: 3
y
8 000 000
-
3
4
$
3 9 1 7
2 8
hy , r i = d[4 + 8 × 3 + 2 × 9 + 7 × 0 + 1 × 0] = h6, 4i Eredm´eny:
$
3 9
$ $ $
$ $
-
d[3 × 9] = h7, 2i
O(m + n)
xa xb 0 - ha hb0
y
0
ha1 hb1
-xa 0 -xb
hy , r i = d[r + hb1 × za + + ha1 × zb + + hb0 × xa + + ha0 × xb], if s = 3 d[xa×xb], if s = $ 6= xa
827
Alg. bonyolults´aga:
r za zb
... $ $
0
s
Processzorok sz´ama: Max{m, n}/2
d[a] = ha
a mod β, b ci β
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” (tetsz˝oleges pontoss´ag´u) eg´eszek szorz´asa (online szisztolikus alg.) L´ep´es: 4
y
6 000 000
-
4
4
7
0 0 1 7
2 8
hy , r i = d[4+8×0+1×0+7× 0 + 1 × 0+7] = h1, 1i Eredm´eny:
1
0 0
2 3 9
3 9
-
d[2 + 9 × 0 + 3 × 0] = h2, 0i
6827
Alg. bonyolults´aga: O(m + n)
r za zb
... $ $
0
s
xa xb 0 - ha hb0
y
0
ha1 hb1
-xa 0 -xb
hy , r i = d[r + hb1 × za + + ha1 × zb + + hb0 × xa + + ha0 × xb + y 0 ], if s = 4 d[r + hb0 × xa + + ha0 × xb], if s = 1
Processzorok sz´ama: Max{m, n}/2
d[a] = ha
a mod β, b ci β
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” (tetsz˝oleges pontoss´ag´u) eg´eszek szorz´asa (online szisztolikus alg.) L´ep´es: 5
y
1 000 000
-
4
1
2
0 0 1 7
2 8
hy , r i = d[1+8×0+1×0+ 7×0+1×0+ 2] = h3, 0i
2
0 0
0 0 0
3 9
-
d[0 + 0 × 0 + 9 × 0 + 3 × 0] = h0, 0i
Eredm´eny: 16827 Alg. bonyolults´aga: O(m + n)
r za zb
... 0 0
0
s
Processzorok sz´ama: Max{m, n}/2
xa xb 0 - ha hb0
y
0
ha1 hb1
-xa 0 -xb
hy , r i = d[r + hb1 × za + + ha1 × zb + + hb0 × xa + + ha0 × xb + y 0 ], if s = 4 d[r + ha1 × hb1 + + hb0 × xa + + ha0 × xb], if s = 2 d[a] = ha
a mod β, b ci β
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
P´elda – “Hossz´u” (tetsz˝oleges pontoss´ag´u) eg´eszek szorz´asa (online szisztolikus alg.) L´ep´es: 6
y
3 000 000
-
4
0 0 0
1 7
2 8
0
3
0 0
0 0 0
3 9
r za zb
...
0 0
0
s
-
xa xb 0 - ha hb0
y
0
ha1 hb1
-xa 0 -xb
hy , r i =
Eredm´eny: 316827 Alg. bonyolults´aga: O(m + n)
Processzorok sz´ama: Max{m, n}/2
d[a] = ha
a mod β, b ci β
Bevezet´ es
P´ elda
Automatikus p´arhuzamos´ıt´as – ¨otlet
Figure: Line´ aris szisztolikus r´ acs – indukt´ıv (rekurz´ıv) fel´ep´ıt´ese
hasonl´os´ag – a szisztolikus r´acs indukt´ıv fel´ep´ıt´ese, illetve – a feadat rekurz´ıv megfogalmaz´asa (funkcion´alis program argumentum´anak indukt´ıv dekompoz´ıci´ oja) k¨ oz¨ ott
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
Automatikus p´arhuzamos´ıt´as – ¨otlet
K´et l´ep´es: konkr´et architekt´ ura–t´ıpus el˝ ozetes tanulm´anyoz´asa c´el: tal´alni egy rekurz´ıv ¨ osszef¨ ugg´est, mely az illet˝ o t´ıpus´ u architekt´ ura m˝ uk¨od´es´et jellemzi ugyanezt a logik´at alkalmazzuk ford´ıtva: ha siker¨ ul a feladatnak egy olyan rekurz´ıv le´ır´as´at megadni, ami megfelel egy (vagy t¨obb) bizonyos architekt´ ura m˝ uk¨ od´es´et jellemz˝o le´ır´asnak ⇒ a feladatot (viszonylag) egyszer˝ u levet´ıteni az illet˝ o t´ıpus´ u architekt´ ur´ara.
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
Egy konkr´et architekt´ura–t´ıpus tanulm´anyoz´asa Adatfolyam egy online szisztolikus t¨ ombben, mely a bemenetet k = 2 l´ep´est k¨ovet˝oen kezdi tov´abb´ıtni.
az Y = F [X ] eredm´enylista (az els˝o 4 elem kiv´etel´evel) kisz´amolhat´o rekurz´ıvan X4 illetve F [X2 ] f¨ uggv´eny´eben
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
A ∗ B kifejez´es kifejt´ese kifejt´es szab´alyai (polinomok szorz´asa eset´en): skal´aris elem hozz´ad´asa egy polinomhoz:
a + (b ^ B) = (a + b) ^ B k´et polinom ¨osszead´asa:
(a ^ A) + (b ^ B) = (a + b) ^ (A + B) skal´aris elem szorz´asa egy polinommal:
a ∗ (b ^ B) = (a ∗ b) ^ (a ∗ B)
k´et polinom szorz´asa: (a ^ A) ∗ (b ^ B) =
(a ∗ b) ^ ((a ∗ B) + (b ∗ A) + (0 ^ (A ∗ B)))
Bevezet´ es
P´ elda
A ∗ B kifejez´es kifejt´ese (polinomok szorz´asa eset´en)
A∗B = = (a0 ^ A1 ) ∗ (b0 ^ B1 ) a0 ∗ B1 = ha0 ∗ b0 i^ + b0 ∗ A1 (A1 ∗ B1 ) 0^ a ∗ (b1 ^ B2 ) 0 = ha0 ∗ b0 i^ + b0 ∗ (a1 ^ A2 ) 0 ^ A1 ∗ B1 a0 ∗ B2 = ha0 ∗ b0 , a0 ∗ b1 + b0 ∗ a1 i^ + b ∗ A2 0 A1 ∗ B1
P´ arhuzamos´ıt´ as
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
= ...
= h a0 ∗ b0 ,
a0 ∗ b1 + b0 ∗ a1 , a2 ∗ b0 + a1 ∗ b1 + a0 ∗ b2 ),
a3 ∗ b0 + a2 ∗ b1 + a1 ∗ b2 + a0 ∗ b3 i^
^ ((a0 ∗ B4 ) + (b0 ∗ A4 )+
+(a1 ∗ B3 ) + (b1 ∗ A3 ) + (A2 ∗ B2 )) a kapott rekurz´ıv ¨osszef¨ ugg´es: H0 [A] ∗ T4 [B] H0 [B] ∗ T4 [A] T4 [A ∗ B] = + H1 [A] ∗ T3 [B] H1 [B] ∗ T3 [A] T2 [A] ∗ T2 [B]
Bevezet´ es
P´ elda
P´ arhuzamos´ıt´ as
Az ´atmenetf¨uggv´eny meghat´aroz´asa a kapott rekurz´ıv o¨sszef¨ugg´es alapj´an a kifejez´es elemeinek megfeleltet´ese az egyes regisztereknek: T2 [A] ∗ T2 [B] → y 0 T4 [A ∗ B] → y T4 [A] → xa, T4 [B] → xb T3 [A] → za, T3 [B] → zb H0 [A] → ha0 , H0 [B] → hb0 H1 [A] → ha1 , H1 [B] → hb1 Az els˝o n´egy elem kisz´am´ıt´as´at megad´ o¨ osszef¨ ugg´esb˝ ol hasonl´o m´odon kapjuk az ´atmenetf¨ uggv´eny y kisz´am´ıt´as´ara vonatkoz´ o r´esz´et az els˝o n´egy l´ep´esben (amikor a jobboldali szomsz´ed PE m´eg nem szolg´altat semmif´ele r´eszeredm´enyt).
