Arkitektura Paraleloak

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


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


Beg. Par. 48

P0 P1

Paralelismo motak (1)(b) Funtzio-paralelismoa

F1

F2

F3

F4

Sarrera


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


Beg. Par. 68

P0 P1

F1

F2

F3

F4

Atazen arteko dependentziak?

Sinkronizazioa- globala (hesiak)- gertaerak (puntutik

puntura)

Sarrera


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


Beg. Par. 88

Begizten paralelizazioa

Modu eraginkorrean. Programatzailea edo konpiladorea?

ale xehea / ertainabegiztaren iterazioen banaketadependentzien analisia

Sarrera


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


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


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 ...


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


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.


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


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


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


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.



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).



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.



Beg. Par. 208

Agian, prozesadore kopuru mugatua erabili beharko da.

Adi eraginkortasunari (ad., cache memoriaren erabilera).



Beg. Par. 218

P0 P1 P2 P3

> Adibideak

do i = 0, N-1A(i) = A(i) + 1B(i) = A(i) * 2

enddo



Beg. Par. 228

P0 P1 P2 P3

?

do i = 0, N-2A(i) = B(i) + 1B(i+1) = A(i) * 2

enddo


> Adibideak


Beg. Par. 238

P0 P0P1 P1

> Adibideak

do i = 0, N-3A(i+2) = A(i) + 1

enddo



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


i

j


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


i

j


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.



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


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


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


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


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


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


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


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


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


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


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


Beg. Par. 388

Nola sinkronizatu aginduak?

• gertaera-bektoreen bidez (post/wait)- hasieratzea- tamaina (memoria)- adi! partekatze faltsua

• kontagailuen bidez

Sinkroniz.-mekanismoak


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


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)



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



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



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


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


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



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..

??



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)



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



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



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...



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



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



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



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



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



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.- …



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


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


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


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


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


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


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


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


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


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


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


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

Documents

Arkitektura Paraleloak