Arkitektura Paraleloak IF - EHU
Arkitektura Paraleloak
8. Begizten Paralelizazioa eta Atazen Banaketa- Sarrera- Begizten paralelizazioa- Sinkronizazio-mekanismoak- Optimizazio nagusiak- Iterazioen (atazen) banaketa- Atal paraleloak
Arkitektura ParaleloakIF - EHU
Beg. Par. 28
Paraleloan exekuta daitezkeen atazak identifikatu behar dira (dependentzien analisia).Prozesuak sinkronizatu behar dira.Prozesuak prozesadoreetara banatu behar dira. Adi: eraginkortasuna!
Helburua: programak P aldiz azkarrago exekutatzea; kasu partikular bat: begiztak.
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 38
Paralelismo motak (1)(a) Datu-paralelismoa
do i = 1, 1000 do i = 1001, 2000 do i = 2001, 3000A(i) = fun(i) A(i) = fun(i) A(i) = fun(i)
enddo enddo enddo
P0 P1 P2
do i = 1, 3000A(i) = fun(i)
enddo
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 48
P0 P1
Paralelismo motak (1)(b) Funtzio-paralelismoa
F1
F2
F3
F4
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 58
Paralelismo motak (2)
▪ ale xehea (fine grain) ataza “txikiak”komunikazio asko
▪ ale ertaina
▪ ale larria (coarse grain) ataza “handiak”
komunikazio gutxi
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 68
P0 P1
F1
F2
F3
F4
Atazen arteko dependentziak?
Sinkronizazioa- globala (hesiak)- gertaerak (puntutik
puntura)
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 78
Bi eredu:▪ Nagusi/Morroi
Hari (thread) nagusiak P hari sortzen ditu une jakin batean, paraleloan exekuta daitezen; ataza bukatutakoan, “hiltzen” dira.
▪ SPMD (Single-Program-Multiple-Data)Programaren P kopia (berdinak) exekutatzen dira. Atazak bereizteko, prozesuen identifikado-reak erabiltzen dira (pid).
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 88
Begizten paralelizazioa
Modu eraginkorrean. Programatzailea edo konpiladorea?
ale xehea / ertainabegiztaren iterazioen banaketadependentzien analisia
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 98
Eskuarki, eta salbuespenak salbuespen, kodearen paralelizazioa (dependentzien analisia, lan-banaketa…) programatzaileak berak egin behar du.Hori dela eta, begiztak eraginkorki paraleliza-tzeko ohiko aukerak analizatu behar ditugu.
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 108
Kodearen frakzio handi bat exekutatu behar da paraleloan; ez ahaztu Amdahl-en legea.
Kodearen paralelizazioak (bektorizazioak bezalaxe) begiztaren aginduen jatorrizko ordena aldatzen du. Beraz, aginduen arteko datu-dependentziak kontuan hartu behar dira.
Sarrera
Arkitektura ParaleloakIF - EHU
Beg. Par. 118
Adibidez:do i = 0, N-1A(i) = A(i) + 1
enddo
L0 +0 S0 L1 +1 S1 L2 +2 S2 ...
P0: L0 +0 S0P1: L1 +1 S1P2: L2 +2 S2… ...
Paraleloan
Sarrera
L2 L0 +2 L1 +0 +1 S2 S1 S0 ...
Arkitektura ParaleloakIF - EHU
Beg. Par. 128Sarrera: datu-depend.
dependentziaRAW i: A =
... j:= A
antidependentziaWAR i: = A
... j: A =
irteera-dependentziaWAW i: A =
... j: A =
i j i j i j
benetako dependentziak
izen-dependentziak
Arkitektura ParaleloakIF - EHU
Beg. Par. 138
do i = 2, N-21 A(i) = B(i) + 22 C(i) = A(i-2) + A(i+1)enddo
1
2
A, 2
A, 1
A(2) = B(2) + 2C(2) = A(0) + A(3)
A(3) = B(3) + 2C(3) = A(1) + A(4)
A(4) = B(4) + 2C(4) = A(2) + A(5)
A(5) = B(5) + 2C(5) = A(3) + A(6)
Begiztak + Dependentzia-grafoak+ Dependentziaren distantzia
Sarrera: datu-depend.
Arkitektura ParaleloakIF - EHU
Beg. Par. 148
do i = 2, N-311 A(i) = B(i) + 22 C(i) = A(i-2)3 D(i+1) = C(i) + C(i+1)4 B(i+1) = B(i) + 15 D(i+30) = A(i)enddo
1
2
3
4
5
A, 0
A, 2
C, 0 C, 1
D, 29
B, 1
B, 1
Sarrera: depend.-grafoak
Arkitektura ParaleloakIF - EHU
Beg. Par. 158
+ Iterazio-espazioa
do i = 2, N-1 do j = 1, N-2 1 A(i,j) = A(i,j-1) * 2 2 C(i,j) = A(i-2,j+1) + 1 enddoenddo
1
2A 2,-1
A 0,1
i
j
Sarrera: depend.-grafoak
Arkitektura ParaleloakIF - EHU
Beg. Par. 168
Dependentzia-proba automatikoa: begiztaren indizearen funtzio linealak soilik.
Sarrera: depend.-proba
do i = L1, L2 X(a*i+b) = = X(c*i+d)enddo
L1 L2
i
a*i+bc*i+d
d - bZKH(c,a)
Z → ez dago depend.
i1 i2
Arkitektura ParaleloakIF - EHU
Beg. Par. 178
Begizten iterazioak prozesadoreen artean banatu behar dira, baina, jakina, datu-dependentziak errespetatu behar dira.
Arazoa distantzia > 0 duten dependentziak dira, eta, batik bat, dependentzia-grafoan zikloak osatzen dituztenak.
Begizten paralelizazioa
Arkitektura ParaleloakIF - EHU
Beg. Par. 188
Begiztak beti exekuta daitezke P prozesadore erabiliz, dependentziak errespetatzeko behar den sinkronizazioa gehituta…
…baina horrek ez du esan nahi beti egin behar denik, kostu orokorra kontuan hartu behar baita: kalkulua + sinkronizazioa (komunikazioa).
Begizten paralelizazioa
Arkitektura ParaleloakIF - EHU
Beg. Par. 198
Helburuak: Begizten iterazioak prozesadoreetara
banatzea, “aldi berean” exekuta daitezen.
Ahal bada, prozesuen arteko sinkronizazioa erabili behar izan gabe (0 distantziako depen-dentziak).
Makinaren ezaugarrien arabera (komunikazio-sarea, lan-banaketa…), tamaina jakin bateko atazak sortzea.
Begizten paralelizazioa
Arkitektura ParaleloakIF - EHU
Beg. Par. 208
Agian, prozesadore kopuru mugatua erabili beharko da.
Adi eraginkortasunari (ad., cache memoriaren erabilera).
Begizten paralelizazioa
Arkitektura ParaleloakIF - EHU
Beg. Par. 218
P0 P1 P2 P3
> Adibideak
do i = 0, N-1A(i) = A(i) + 1B(i) = A(i) * 2
enddo
Begizten paralelizazioa
Arkitektura ParaleloakIF - EHU
Beg. Par. 228
P0 P1 P2 P3
?
do i = 0, N-2A(i) = B(i) + 1B(i+1) = A(i) * 2
enddo
Begizten paralelizazioa
> Adibideak
Arkitektura ParaleloakIF - EHU
Beg. Par. 238
P0 P0P1 P1
> Adibideak
do i = 0, N-3A(i+2) = A(i) + 1
enddo
Begizten paralelizazioa
Arkitektura ParaleloakIF - EHU
Beg. Par. 248
> Adibideak
do i = 0, N-1 do j = 1, M-1 A(i,j) = A(i,j-1) + 1enddo
enddo
P0 P1 P2 P3
Begizten paralelizazioa
i
j
Arkitektura ParaleloakIF - EHU
Beg. Par. 258
P0
P1
P2
P3
> Adibideak
do i = 0, N-1 do j = 1, M-1 A(i,j) = A(i,j-1) + 1enddo
enddo
Begizten paralelizazioa
i
j
Arkitektura ParaleloakIF - EHU
Beg. Par. 268
Aginduen arteko dependentziak 0 distantziakoak baldin badira, hau da, iterazioak independenteak badira, iterazioak nahi den moduan bana daitezke prozesadoreetara, sinkronizazioa erabili gabe: doall.
Iterazioen arteko dependentziak baldin badaude, baina denak “aurrerantz” badoaz, sinkronizazio-hesiak erabil daitezke: forall (edo doall + barrier).
Dependentzia-zikloak baldin badaude, puntutik pun-turako sinkronizazioa erabili behar da: doacross.
Begizten paralelizazioa
Arkitektura ParaleloakIF - EHU
Beg. Par. 278
Iterazioak independenteak dira, eta banaketa nahi den moduan egin daiteke: doall.do i = 0, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i) / A(i)
enddo
doall i = 0, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i) / A(i)
enddoall
1
2
3
C, 0
A, 0
i=0 1 2 3
Doall begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 288
Iterazioen arteko dependentziak daude, baina denak aurrerantz doaz: forall.
Dependentzia bakoitza hesi baten bidez sinkroniza daiteke: prozesuek zain geratuko dira agindu jakin bat denok exekutatu arte.
Behar dena baino sinkronizazio gehiago gehitzen da, baina oso metodo sinplea da.
Forall begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 298
do i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i-1) / A(i)
enddo
forall i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)HESIA (...)D(i) = C(i-1) / A(i)
endforall
i=1 2 3 4
hesia
1
2
3
C, 0
A, 0
C, 1
Forall begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 308
do i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i-1) / A(i)
enddo
i=1 2 3 4
hesia
doall i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)
enddoall[ HESIA (...) ]doall i = 1, N-1D(i) = C(i-1) / A(i)
enddoall
1
2
3
C, 0
A, 0
C, 1
Forall begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 318
Dependentziek zikloak osatzen dituzte: doacross, ekoizle/kontsumitzaile motako sinkronizazioa.
Dependentziak sinkronizatzeko, gertaera-bektoreak: post (gA,i) gA(i) := 1 wait (gA,i) itxaron gA(i) = 1 izan arte
gA(i) = 0 bada, oraindik ez da exekutatu sinkronizatzen ari den aginduaren i iterazioa.
Doacross begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 328
do i = 2, N-2A(i) = B(i-2) + 1B(i+1) = A(i-2) * 2
enddo
1
2
A,2B,3 1 1 1 . . .
2 2 2 . . . 1 1 1 2 2 2
i=2 3 4 5 6 7
doacross i = 2, N-2 wait (gB,i-3)A(i) = B(i-2) + 1post (gA,i)
wait (gA,i-2)B(i+1) = A(i-2) * 2post (gB,i)
enddoacross
Doacross begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 338
do i = 2, N-2A(i) = B(i-2) + 1B(i+1) = A(i-2) * 2
enddo
12 13 14
22 23 24 15 16 17
25 26 27
...
P0 P1 P2
doacross i = 2, N-2 wait (gB,i-3)A(i) = B(i-2) + 1post (gA,i)
wait (gA,i-2)B(i+1) = A(i-2) * 2post (gB,i)
enddoacross
1
2
A,2B,3
, 3
Doacross begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 348
do i = 0, N-2A(i) = B(i) + C(i)B(i+1) = A(i) / 2
enddo
doacross i = 0, N-2wait (gB,i-1)A(i) = B(i) + C(i)B(i+1) = A(i) / 2post (gB,i)
enddoacross
1
2
A,0B,1
12p w 1 2 p w 1 …
??
ADI: paralelizatzea ez da beti egokia
Doacross begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 358
P0
P1
P2
P3
Bi dimentsioko gertaera-bektoreakdo i = 0, N-2 do j = 0, N-2 A(i+1,j+1) = A(i+1,j) + 1 B(i,j) = A(i,j)
enddoenddo
doacross i = 0, N-2 do j = 0, N-2 A(i+1,j+1) = A(i+1,j) + 1 post (gA,i,j) wait (gA,i-1,j-1) B(i,j) = A(i,j) enddoenddoacross
Doacross begiztak
Arkitektura ParaleloakIF - EHU
Beg. Par. 368
Antidependentziak / Irteera-dependentziakProzesuen artean baldin badira, sinkronizatu egin behar dira. do i = 0, N-3A(i) = B(i+2) / A(i)B(i) = B(i) + C(i)
enddodoacross i = 0, N-3A(i) = B(i+2) / A(i)post (gB,i)wait (gB,i-2)B(i) = B(i) + C(i)
enddoacross
1
2
B,2
LD B(i+2)post...wait ST B(i)
Beste dependentziak
Arkitektura ParaleloakIF - EHU
Beg. Par. 378
If motako aginduak
do i = 1, N-1if (B(i) > 0) then
A(i) = A(i) + B(i) C(i) = A(i-1) / 2 endifenddo
doacross i = 1, N-1
if (B(i) > 0) then A(i) = A(i) + B(i) post (gA,i) wait (gA,i-1) C(i) = A(i-1) / 2
endif
enddoacross
else post (gA,i)endif1
2
A,1
0
If aginduak
Arkitektura ParaleloakIF - EHU
Beg. Par. 388
Nola sinkronizatu aginduak?
• gertaera-bektoreen bidez (post/wait)- hasieratzea- tamaina (memoria)- adi! partekatze faltsua
• kontagailuen bidez
Sinkroniz.-mekanismoak
Arkitektura ParaleloakIF - EHU
Beg. Par. 398
Sinkronizazio-kontagailu bat dependentzia bakoitzeko- prozesuek ordena hertsian gehitzen dute
kontagailua, agindu horren exekuzioa bukatu dela adierazteko.
- kA = j j arteko iterazio guztiak bukatu dira, baina j+1 iterazioa ez.
i = 0 1 2 3 4 5 6 7 8 9...
gA(i) = 1 1 1 0 1 0 1 1 0 0... kA = 2
Sinkroniz.-kontagailuak
Arkitektura ParaleloakIF - EHU
Beg. Par. 408
Nola sinkronizatu dependentzia bat kontagailu baten bidez:- i iterazioa exekutatu ondoren, itxaron egin
behar da kontagailua i-1 izan arte (hau da, agindu horren exekuzioa i-1 iteraziora heldu arte):
wait (kA,i-1) → itxaron kA = i-1 izan arte- gero, gehitu kontagailua, i iterazioa ere exekutatu dela adierazteko:
post (kA,i) → kA := kA + 1 (kA := i)
Sinkroniz.-kontagailuak
Arkitektura ParaleloakIF - EHU
Beg. Par. 418
doacross i = 3, N-1wait (gD,i-3)C(i) = C(i) * D(i-3)post (gC,i)
A(i) = C(i) + B(i)wait (gC,i-1)D(i) = C(i-1) / A(i)
post (gD,i)enddoacross
do i = 3, N-1C(i) = C(i) * D(i-3)A(i) = C(i) + B(i)D(i) = C(i-1) / A(i)
enddo
1
2
3
C, 0
A, 0 C,1
D,3 1 1 12 2 23 3 3 1 1 1 2 2 2 3 3 3
doacross i = 3, N-1wait (kD,i-3)C(i) = C(i) * D(i-
3)wait (kC,i-1)post (kC,i)
A(i) = C(i) + B(i)D(i) = C(i-1) /
A(i)wait (kD,i-1)
post (kD,i)enddoacross
Sinkroniz.-kontagailuak
Arkitektura ParaleloakIF - EHU
Beg. Par. 428
doacross i = 3, N-1C(i) = C(i) * D(i-3)wait (kC,i-1)post (kC,i)
A(i) = C(i) + B(i)D(i) = C(i-1) / A(i)
enddoacross
Sinkronizazioa minimizatu
P0
P01
2
3
C, 0
A, 0 C,1
D,3 1 1 12 2 23 3 3 1 1 1 2 2 2 3 3 3
do i = 3, N-1C(i) = C(i) * D(i-3)A(i) = C(i) + B(i)D(i) = C(i-1) / A(i)
enddo
Sinkroniz.-kontagailuak
Arkitektura ParaleloakIF - EHU
Beg. Par. 438
forall i = ...[ 1 ]hesia(...)
[ 2 ] [ 3 ]
hesia(...)
[ 4 ]endforall
doacross i = ...[ 1 ]post (gA,i)
wait (gA,i-1)[ 2 ] post (gC,i)
[ 3 ]
wait (gC,i-2)[ 4 ]
enddoacross
doacross i = ...[ 1 ]wait (kA,i-1)post (kA,i)
[ 2 ] wait (kC,i-1)
post (kC,i)
[ 3 ][ 4 ]
enddoacross
1
2
3
A, 1
C, 2B,0
A,0
4
Adibide bat
Arkitektura ParaleloakIF - EHU
Beg. Par. 448
0. Konstanteen definizioak eta indukzio-aldagaiak desegitea.
1. Berezkoak ez diren dependentzia guztiak ezabatzea. Esaterako,
do i = 0, N-1X = A(i) * B(i)C(i) = SQRT(X)D(i) = X - 1
enddo
doall i = 0, N-1X(i) = A(i) * B(i)C(i) = SQRT(X(i))
D(i) = X(i) - 1enddoall
X aldagaia pribatuabihurtu
Optimizazio nagusiak
ez da bektore bat erabilli behar, nahikoa da X aldagaia pribatua dela adieraztea
Arkitektura ParaleloakIF - EHU
Beg. Par. 458
2. Begiztaren fisioa. Seriean exekutatu behar den zati bat baldin badago, zatitu begizta bi partetan (edo gehiago), ahal dena paraleloan exekutatzeko.
do i = 1, N-1A(i) = A(i-1) / 2D(i) = D(i) + 1
enddo
do i = 1, N-1A(i) = A(i-1) / 2
enddo
doall i = 1, N-1D(i) = D(i) + 1
enddoall
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 468
3. Dependentziak ordenatzea (aurrerantz).
do i = 1, N-1A(i) = D(i-1) / 2D(i) = C(i) + 1
enddo
forall i = 1, N-1D(i) = C(i) + 1HESIA (...)
A(i) = D(i-1) / 2endforall
1
2D, 1
2………….12………1 2…….1
1…2.. 1…2.. 1…2..
??
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 478
4. Dependentziak lerrokatzea: peeling.
do i = 1, N-1A(i) = B(i)C(i) = A(i-1) + 2
enddo
1
2A, 1
doall i = 1, N-2A(i) = B(i)C(i+1) = A(i) + 2
enddoall
C(1) = A(0) + 2
A(N-1) = B(N-1)
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 488
do i = 2, N-1A(i) = B(i)C(i) = A(i-1) + A(i-2)
enddo
1
2
A, 2 A, 1
1’
2
A, 2 X, 1
1
C(2) = A(1) + A(0)C(3) = B(2) + A(1)
doall i = 2, N-3A(i) = B(i)X(i+1) = B(i+1)C(i+2) = X(i+1) + A(i)
enddoall
A(N-2) = B(N-2)A(N-1) = B(N-1)
do i = 2, N-1A(i) = B(i)X(i) = B(i)C(i) = X(i-1) + A(i-2)
enddo
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 498
5. Hari independenteak sortzea
do i = 0, N-3A(i+1) = B(i) + 1B(i+2) = A(i) * 3C(i) = B(i+2) - 2
enddo
B(2) = A(0) * 3C(0) = B(2) - 2
doall k = 0, 2 do i = pid, N-4, 3 A(i+1) = B(i) + 1 B(i+3) = A(i+1) * 3 C(i+1) = B(i+3) – 2 enddoenddoall
A(N-2) = B(N-3) + 1
1
2
3B,0
B,2 A,1 1 1 1 1 1 12 2 2 2 2 23 3 3 3 3 3
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 508
6. Sinkronizazioa minimizatzeado i = 2, N-1B(i) = B(i) + 1
C(i) = C(i) / 3A(i) = B(i) + C(i-1)D(i) = A(i-1) * C(i-2)E(i) = D(i) + B(i-1)
enddo
1
2
3
B,0
B,1
A,14
5
C,
1C,2
D,0
doacross i = 2, N-1B(i) = B(i) + 1
C(i) = C(i) / 3post (gC,i)
wait (gC,i-1)A(i) = B(i) + C(i-1)post (gA,i)
wait (gA,i-1)D(i) = A(i-1) * C(i-2)E(i) = D(i) + B(i-1)
enddoacross
1 2 3 4 51 2 3 4 51 2 3 4 5
i=234...
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 518
7. Bi dimentsioko begiztak: begizta-trukea.
do i do_par j
do_par i do j
do j do_par i
do_par j do i
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 528
Adibidez:
do i = 1, N-1 do j = 0, N-1
A(i,j) = A(i-1,j) + 1
enddoenddo
do i = 1, N-1doall j = 0, N-1
A(i,j) = A(i-1,j) + 1enddoall
enddo
j=0 1 2 3i=1
2
3
4
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 538
Adibidez:
doall j = 0, N-1do i = 1, N-1
A(i,j) = A(i-1,j) + 1enddo
enddoall
j=0 1 2 3i=1
2
3
4
do i = 1, N-1 do j = 0, N-1
A(i,j) = A(i-1,j) + 1
enddoenddo
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 548
do i = 1, 100 do j = 0, 2 A(i,j) = A(i,j) - 1 D(i) = A(i-1,j+1) * 3
enddoenddo
do j = 2, 0, -1
doall i = 1, 100 A(i,j) = A(i,j) - 1 D(i) = A(i-1,j+1) * 3
enddoallenddo
8. Bi dimentsioko begiztak: noranzko-aldaketa.
j=0 1 2 i=1
2
3
4
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 558
do j = 1, 2N-1 doall i = max(1,j-N+1), min(j,N) A(i,j-(i-1)) = A(i-1,j-(i-1)) + A(i,j-1-(i-1)) enddoallenddo
9. Skew
do i = 1, N do j = 1, N A(i,j) = A(i-1,j) + A(i,j-1) enddoenddo
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 568
10. Ohiko beste zenbait optimizazio:Alearen tamaina handitzeko eta paralelizazioaren gainkarga arintzeko.- Bi begizta batean bildu (esanahia mantentzen bada!): fusioa.- Bi dimentsioko begizta dimentsio bakarreko begizta bihurtu: kolapsoa edo koalestzentzia.- …
Optimizazio nagusiak
Arkitektura ParaleloakIF - EHU
Beg. Par. 578
Nola banatzen dira begizten iterazioak (atazak, oro har) prozesadoreen artean?Iterazio adinako prozesadore badago, agian bat prozesadoreko.
Baina iterazio baino prozesadore gutxiago badago? Banaketa (scheduling) izan daiteke:
estatikoa: programa konpilatzen denean.
dinamikoa: programa exekutatzen ari denean.
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 588
Helburua: banatzen diren atazen exekuzio-denborak berdintsuak izatea, hutsarteak saihesteko (load balancing).
Nolanahi ere den, adi dependentziei (sinkronizazioa), ale-tamainari, atzipenen lokaltasunari, eta banaketaren kostuari.
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 598
Banaketa estatikoaPrograma konpilatzen denean erabakitzen da zer exekutatuko duen prozesu bakoitzak. Beraz, erabakita dago exekuzioa hasi baino lehen.Prozesuek aldagai pribatu bana erabiltzen dute identifikadore gisa: pid (0..P-1).Oinarrizko bi aukerak: ondoz ondokoa eta tartekatua.
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 608
▪ Ondoz ondokoa 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
15 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3hasi = pid * N/Pbuka = (pid+1) * N/P – 1do i = hasi, buka
...enddo
do i = pid, N, P...
enddo
- Ez zaio gainkargarik gehitzen prozesuen exekuzioari.- Baina ez da prozesuen arteko lan-kargaren oreka
ziurtatzen.- Cache memoriako atzipenen lokaltasuna kontrola
daiteke.
▪ Tartekatua 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 618
Lan-kargaren orekado i = 1, 80if (A(i) > 0) kalkulatu()
enddo
1-2021-4041-6061-80
estatikoa (finkoa)
Tex
beste ataza baten
esleipen dinamikoa
1-10
21-3011-20
31-40Tex
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 628
Banaketa dinamikoaLan-karga orekatuta mantentzeko, “ataza ilara” bat antolatzen da. Prozesu batek ataza baten exekuzioa bukatzen duenean (begiztaren zati bat), beste bat hartzen du ilaratik. Oinarrizko bi aukera: banatzen diren begizta zatiak tamaina berdinekoak dira beti, edo, exekuzioa aurrera joan ahala, gero eta txikiagoak dira.
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 638
Iterazioak banan-banan banatzen dira, edo multzoka.
Self / Chunk scheduling
Gainkarga gehitzen zaio begiztaren exekuzioari.Alderatu behar dira exekuzio-denbora eta esleipenarena.
LOCK (S); nik = i; i = i + Z; Z = 1 selfUNLOCK (S);while (nik <= N-1)
endwhile
do j = nik, min(nik+Z-1, N-1) ...enddoLOCK (S) nik = i; i = i + Z;UNLOCK (S)
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 648
Banatzen diren begizta zatiak gero eta txikiagoak dira, bukaerara hurbiltzen den neurrian.
Guided / Trapezoid scheduling
▪Guided exekutatzeko falta den zatiaren parte proportzionala:
Zs = (N – i) / P (goiko zenbaki osoa)
edo, baliokidea dena, Zs = Zs-1 (1 - 1/P)
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 658
▪ Trapezoid zatien tamaina konstante batez txikiagotzen da: Zs+1 = Zs - k
esleipen-eragiketa
Z1
Zn
1 k2 i
kZ2
)(21
22 1
22111
1
1
n
nnnn
s
ns ZZN
ZZkNkZZZZnZZZ
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 668
Oro har, atazen exekuzio-denbora berdintsua izatea bilatzen du banaketa dinamikoak, baina:
- banaketaren kostua (overhead) kontuan hartu behar da, atazen exekuzioarekin alderatuta.- datu-atzipenen lokaltasuna eta partekatze faltsuaren arazoak ere kontuan hartu behar dira.
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 678
Adibide bat (1.000 iterazio independente, 4 prozesadore):▪ chunk (Z = 100)
100 100 100 100 100 100 100 100 100 100 (10)
▪ guidedfalta dira: 1000 750 562 421 … 17 12 9 6 4 3 2 1banatzen dira: 250 188 141 106 … 5 3 3 2 1 1 1 1
(22)
▪ trapezoid (Z1 = 76, Zn = 4 >> k = 3)76 73 70 67 … 16 13 10 7 4 (25)
Iterazioen banaketa
Arkitektura ParaleloakIF - EHU
Beg. Par. 688
Prozedura- edo funtzio-mailako paralelismoa:
F2
F3
F1
F4
F5
ForkF1F2
JoinFork
F3F4
JoinF5
doall k = 0, 1if (pid = 0) then F1if (pid = 1) then F2
endoall[hesia]doall k = 0, 1
if (pid = 0) then F3if (pid = 1) then F4
endoallF5
- Fork / Join eredua- Parallel sections
Atal paraleloak
Arkitektura Paraleloak IF - EHU
Beg. Par. | Atal Paraleloak
Prozedura- edo funtzio-mailako paralelismoa:
- Fork / Join eredua- Parallel sections
F2
F3
F1
F4
F5
ForkF1F2
JoinFork
F3F4
JoinF5
doall k = 0, 1if (pid=0) then F1if (pid=1) then F2
endoall[hesia]doall k = 0, 1
if (pid=0) then F3if (pid=1) then F4
endoallF5