ariketak - gipuzkoa€¦ · parametroak; etaexekuzi o-denbora eta kalkulu-abiadura, bektoreak (eta...

Arkitektura Paraleloak 12-13

Konputagailu Paraleloak Abiadura handiko konputazioa

ARIKETAK

Konputagailuen Arkitektura eta Teknologia saila Informatika Fakultatea — Euskal Herriko Unibertsitatea

1. gaia: Bektore-konputagailuak ....................................................................... 3 2. gaia: Konputagailu paraleloak (oinarrizko kontzeptuak) .....................17 3. gaia: Datuen koherentzia SMP konputagailuetan .................................19 4. gaia: Prozesuen sinkronizazioa SMP konputagailuetan .......................25 5. gaia: Memoriaren kontsistentzia konputagailu paraleloetan ..............33 6. gaia: Komunikazio-sarea. Mezu-ematea. .................................................35 7. gaia: Datuen koherentzia DSM konputagailuetan ................................47 8. gaia: Begizten paralelizazioa eta banaketa .............................................51 9. gaia: Abiadura handiko konputagailuak. OpenMP, MPI (sarrera). ....57

Ariketa orokorrak .............................................................................. 59

Ariketak: Bektore-konputagailuak ▪ 3 ▪

1.1. Bektore-konputagailu batean, lau "programatxo" hauek exekutatu dira, eta exekuzio-denbora hauek neurtu dira (VS = 1, VL = Lmax):

Programak Exekuzio-denbora (≈) P1 LV V1,A(R1) 300 ns

P2 LV V1,A(R1) ADDV V2,V1,V0 325 ns

P3 LV V1,A(R1) ADDV V2,V1,V0 SV B(R1),V2

335 ns

P4 LV V1,A(R1) LV V2,B(R1) ADDV V3,V2,V1 SV C(R1),V3

650 ns

Bektore-konputagailu horren zer ezaugarri lor daitezke datu horietatik abiatuta? 1.2. Exekutatu egin behar da honako programa hau bektore-konputagailu batean:

LV V0,A(R1) LV V1,B(R1) MULV V2,V0,V1 LV V3,C(R1) ADDV V4,V2,V3 SV D(R1),V4

Konputagailuaren ezaugarriak

Aginduen segmentazio-eskema: B/D - Ir - AM - M - ... - M - Id B/D - Ir - A - ... - A - Id

Eragiketen latentziak: add → 3 ziklo; mul → 5 z.; mem → 7 z.

Memoriako busak: 2 Erloju-maiztasuna: 500 MHz

a. Kalkula ezazu programaren exekuzio-denbora N-ren arabera (exekuzio-taula bat bete), bi kasu hauetan: (1) aginduen exekuzioa kateatu egin daiteke; eta (2) aginduen exekuzioa ezin da kateatu. Ez kontuan hartu balizko gatazkak memoria-moduluak atzitzerakoan.

b. Aurreko bi kasuetarako, kalkula itzazu: kalkulu-abiadura maximoa (bektore luzeak); N1/2 eta N3/4 parametroak; eta exekuzio-denbora eta kalkulu-abiadura, bektoreak (eta bektore-erregistroak) 128 osagaikoak izanik.

c. Errepikatu ariketaren (a) atala, baina memoria atzitzeko bus bakarra izanik. d. Azkenik, eta taularik bete gabe, arrazoitu zein izango litzatekeen exekuzio-denboraren

ordena 4 bus baleude memoria atzitzeko (aginduak kateatuz, eta kateatu gabe). 1.3. Honako bektore-programa hau exekutatu behar da:

LV V1,A(R1) LV V2,B(R1) OP1 V3,V1,V2 LV V4,C(R1) OP2 V5,V4,V3 SV D(R1),V5

Aginduen segmentazio-eskema LV/SV → B/D Ir AM M(4)Id OP1 → B/D Ir A1 A1 A1 Id OP2 → B/D Ir A2 A2 Id

Beheko taulan, bi bektore-konputagailutan egindako exekuzioen emaitza partzial batzuk ageri dira. Osa itzazu datuak (zikloak) agindu guztietarako, eta, emaitzen arabera, adierazi kasu bakoitzerako: bektore-erregistroen luzera, memoriako bus kopurua, eta aginduen arteko kateaketa egiten denetz.

1. kasua 2. kasua 1. datua N. datua 1. datua N. datua

LV V1,A(R1) LV V2,B(R1) OP1 V3,V1,V2 LV V4,C(R1) OP2 V5,V3,V4 SV D(R1),V5

3 + 4 + 1 = 8 108 + 1 + 3 + 1 = 113 107 + 4 + 1 = 112

107 108 212 211

3 + 4 + 1 = 8

71 139 143 207

▪ 4 ▪ Arkitektura Paraleloak 12-13

1.4. Bektore-konputagailu batean, programa jakin bat exekutatu behar da, non, eskalarki exekutatu behar diren begiztekin batera, C = A + B eragiketarako bektore-kodea dagoen (A, B, C, bektoreak). Zenbatu egin da programa exekutatzeko behar izan den ziklo kopurua, eta honako datu hauek lortu dira:

N → 10 50 100 bektoreen luzera TBE → 80 304 584 exekuzio-denbora, ziklotan, kode eskalarra eta bektoriala batera

Konputagailuaren erlojua 800 MHz-ekoa da.

a. Marraz itzazu aurreko datuak grafiko batean, eta kalkula itzazu exekuzio-denbora (ns) eta kalkulu-abiadura (MFlop/s), N = 128 kasurako.

b. Aipatu den bezala, kode eskalarra eta bektoriala batera exekutatu da, eta programaren bektorizazio-faktorea f = 0,8 izan da. Gainera, konputagailu horretan K∞ = te / tb parametroa 10 da. Datu horietan oinarriturik, kalkula itzazu th eta tb parametroak (bektore-eragiketaren hasiera-denbora eta osagai bat prozesatzeko denbora, hurrenez hurren).

Zein da makina horretan lor daitekeen kalkulu-abiadura maximoa f = 1 denean? Eta N1/2? c. Aurreko datuen arabera, adierazi, arrazoituz, makina horren bus kopurua (LV/SV

unitateak), eta aginduak kateatu egiten diren edo ez. 1.5. Bektore-konputagailu baten prozesadore eskalarraren prozesatze-abiadura maximoa 500

Mflop/s da, eta bektore-prozesadorearena 2.500 Mflop/s. Makina horren lan-kargaren bektorizazio-faktorea, batez bestean, f = 0,7 da.

Hiru eguneratze eskaini dizkigute makina horretarako (kostu berdinekoak):

- konpiladore berria, gure programetan f = 0,85 erdiesten duena. - prozesadore eskalarraren bertsio berria, 1.000 Mflop/s abiadurakoa (max.). - bektore-prozesadorearen bertsio berria, 4.000 Mflop/s abiadurakoa (max.).

Hiru aukera horietatik, zeinek lortuko du kalkulu-abiadurarik handiena? 1.6. Bektore-konputagailu batean, honako programa hau exekutatu behar da:

LV V1,A(R1) B – D/Ir – AM – M(6) – Id ADDV V2,V1,V1 B – D/Ir – A(2) – Id LV V3,B(R1) MULV V4,V3,V2 B – D/Ir – A(4) – Id SV C(R1),V4

Aginduen segmentazio-eskema albokoa da. Aginduak kateatu egin daitezke, eta badaude bi bus memoria atzitzeko. Bektoreak 256 osagaikoak dira, eta bektoreen pausoa (stride) 1 da. Erloju-maiztasuna 500 MHz da.

a. Demagun ez direla gatazkak sortzen memoria-moduluak erabiltzean. Kalkula ezazu programaren exekuzio-denbora N-ren arabera (idatzi taula batean exekuzioko unerik garrantzitsuenak). Denbora horren arabera, kalkula itzazu R256, R∞ (Mflop/s) eta N1/2 parametroak.

b. Bektore-erregistroak 64 osagaikoak dira; beraz, bektore horiek prozesatzeko, begizta bat antolatu behar da. Begizta kontrolatzeko aginduen exekuzio-denbora tbeg = 10 ziklo da. Kalkula itzazu, berriz, aurreko ataleko parametroak.

c. Taula bat bete gabe, arrazoitu zein izango litzatekeen R∞ parametroaren balioa memoria atzitzeko bus bakarra izango balitz.

d. Aurreko bektore-programa begizta eskalar batzuekin batera exekutatu da, eta lortu den kalkulu-abiadura 241 Mflop/s izan da. Prozesadore eskalarra, limitean, bektore-prozesadorea baino 10 aldiz motelagoa da. Kalkula ezazu eskalarki exekutatu den programaren frakzioa.


e. Analiza ditzagun memoria-gatazkak. Exekutatu behar da orain honako programa hau:

LV V1,A(R1) ADDVI V2,V1,#1.5 DIVV V3,V2,V1 B – D/Ir – A(8) – Id SV A+1(R1),V3

Memoria 16 modulutan tartekatuta dago. A bektorea m0 modulutik aurrera dago gordeta memorian, eta pausoa (stride) 1 da. Kalkula ezazu programaren exekuzio-denbora N-ren arabera. Kontuan hartu memoria-moduluak erabiltzeko izan daitezkeen arazoak.

1.7. Honako begizta hau exekutatu behar da bektore-konputagailu batean:

do i = 1, N A(i) = 2.0 * A(i+2) + 1.0 enddo

Aginduen latentzia unitate funtzionaletan sartu baino lehen (B, D...) 4 ziklo da, eta unitate funtzionalen latentziak hauek dira: memoria, 5 ziklo; batugailua, 3 z.; biderkagailua, 4 z.

Kalkula ezazu exekuzio-denbora (N-ren arabera) bi kasu hauetan: (1) memoriarako bus bat dago, eta aginduak kateatu egin daitezke; eta (2) memoriarako bi bus dago, eta ezin da aginduak kateatu. Ez dago gatazkarik memoria-moduluetan.

Kasu bakoitzerako, kalkula ezazu lor daitekeen kalkulu-abiadura maximoa (Mflop/s) erlojuaren maiztasuna 600 MHz izanik. Zein izango da benetako kalkulu-abiadura N = 50 bada?

1.8. Bektore-konputagailu batek programa hau exekutatu behar du:

LV V1,A(R1) LV V2,B(R1) MULV V3,V1,V2 LV V4,C(R1) ADDV V5,V3,V4 SV D(R1),V5

Aginduen segmentazio-eskema LV/SV → B D/Ir AM M(5) Id MULV → B D/Ir A* A* A* Id ADDV → B D/Ir A+ A+ Id

Memoria tartekatuta dago 32 modulutan. A bektorearen aurreneko osagaia m0 moduluan dago, B bektorearena m30 moduluan, C bektorearena m7 moduluan, eta D bektorearena m0 moduluan. Behar adina bus dago memoria atzitzeko, eta aginduen exekuzioa kateatu egin daiteke. Bektoreak 64 osagaikoak dira, eta pausoa s = 1 da.

a. Bete ezazu ohiko exekuzio-taula, exekuzio-denbora N-ren arabera kalkulatzeko. Analizatu memoria-atzipenetan sor daitezkeen gatazkak eta, ondorioz, sortzen diren atzerapenak.

b. Bila ezazu kokapenik egokiena memorian lau bektoreentzat, memoria-atzipeneko gatazkak saihesteko. Kalkulatu, berriz, programaren exekuzio-denbora.

c. Kalkula itzazu, bi kasuetarako, N1/2, R∞ eta R64 parametroak (F = 800 MHz). 1.9. Bektore-prozesadore batek honako programa hau exekutatuko du:

LV V2,A(R1) MULV V1,V2,V2 ADDV V4,V4,V1 SV B(R1),V4 ADDV V5,V4,V1 SV C(R1),V5

Aginduen segmentazio-eskema

LV/SV → B/D Ir AM M(14) Id ADDV → B/D Ir A(4) Id MULV → B/D Ir A(6) Id

a. Analizatu programaren exekuzioa (bete exekuzio-taula) eta kalkula ezazu exekuzio-denbora. Memoria atzitzeko bus bakar bat dago, eta aginduak kateatu egin daitezke. Ez dago gatazkarik memorian. Unitate funtzional nahikoak badaude.

b. Erlojuaren maiztasuna 666 MHz da; kalkula itzazu: 1. R∞ (Mflop/s). 2. N1/4, N1/2 eta N3/4 balioak; gero, irudikatu N (% R∞) funtzioa. 3. Kalkulu-abiadura (Mflop/s), datu hauek kontuan hartuz: N = 100; programan kode

eskalarra ere badago, eta bektorizazio-faktorea 0,6 izan da; K∞ = te / tb = 6 da.


c. Memoria 64 modulutan banatuta dago, eta hiru bus dago memoria atzitzeko. Kalkulatu programako bektoreen kokapenik egokiena memorian, haien atzipena gatazkarik gabe gerta dadin. Pausoa s = 1 da.

1.10. Bektore-konputagailu sinple batek honako ezaugarri hauek ditu:

• Tzikloa = 5 ns • Tmem-atz = 40 ns • Memoria-moduluak = 4 • Kateaketarik ez

Makina horretan, begizta bat exekutatu behar da bektore baten osagaiei konstante bat gehitzeko (A = A + 1). Adierazi, arrazoituz, espero daitekeen kalkulu-abiadura maximoa (Mflop/s).

1.11. Honako programa hau exekutatuko da bektore-konputagailu batean:

LV V1,A(R1) ADDVI V2,V1,#2.0 SV B(R1),V2 LV V3,C(R1) MULV V4,V1,V3 ADDV V5,V2,V4 SV D(R1),V5

Aginduen segmentazio-eskema LV/SV → B D/Ir AM M(6) Id ADDV → B D/Ir A(3) Id MULV → B D/Ir A(5) Id

Memoria atzitzeko bi bus dago, eta memoria-eredua "load aginduak aurreratu" da. Memoria 16 modulutan tartekatuta dago, bektoreen luzera N = 64 da, eta pausoa s = 1. Aginduak kateatu egin daitezke.

Adieraz itzazu, exekuzio-taula batean, aginduen exekuzioko unerik garrantzitsuenak. Kalkula ezazu zein modulutatik aurrera kokatu behar diren bektoreak memorian, atzipen-gatazkak saihestearren.

Kalkula itzazu R∞ eta R64 (Mflop/s) parametroak. Erloju-maiztasuna 500 MHz da. 1.12. A = B × C + D + 1.0 bektore-eragiketa egiten duen programa exekutatu da bektore-

konputagailu batean, eta bi parametro hauek neurtu dira: N1/2 = 25 eta R∞ = 500 Mflop/s. Konputagailuaren erlojua 666 MHz-ekoa da.

Zein izango da programa hori exekutatzen lortuko den kalkulu-abiadura Mflop/s-tan, baldin eta bektoreen luzera 100 bada? Aginduen kateaketa onartzen dela kontuan hartuz, zenbat bus erabiltzen dira makina horretan memoria atzitzeko?

1.13. Honako programa hau exekutatu behar da bektore-prozesadore batean:

SV A(R1),V1 LV V2,B(R1) LV V3,C(R1) ADDV V1,V2,V3 MULV V4,V1,V1 SV D(R1),V4 ADDV V5,V1,V4 SV E(R1),V5

Aginduen segmentazio-eskema

LV/SV → B D/Ir AM M(5) Id ADDV → B D/Ir A(2) Id MULV → B D/Ir A(4) Id

Aginduak kateatu egin daitezke, eta memoriarako bi bus daude. Memoria 11 modulutan tartekatuta dago. Bektoreen pausoa s = 1 da, eta m0 modulutik aurrera daude gordeta memorian (N = 100).

a. Bete ezazu programari dagokion exekuzio-taula eta kalkula ezazu programaren exekuzio-denbora N-ren arabera.

b. Aurreko programako kalkulu-abiadura maximoa neurtu da, eta R∞ = 500 Mflop/s lortu da. Kalkulatu makina horren erlojuaren maiztasuna, eta bektoreen luzera minimoa kalkulu-abiadura maximo teorikoaren % 80a erdiesteko.


1.14. Bektore-(multi)konputagailu batek 8 bektore-prozesadore ditu. Konputagailuaren memoria 16 modulutan tartekatuta dago eta, memoriaren latentzia 4 ziklo da. Prozesadore bakoitzak bi bus ditu memoriarako, erabat independenteak. Erlojua 500 MHz-ekoa da, eta bektore-erregistroen tamaina 128 da. Aginduak kateatu egin daitezke, eta hau da haien segmentazio-eskema:

LV / SV → B D/Ir AM M(4) Id ADDV → B D/Ir A(2) Id

Honako begizta hau exekutatu da konputagailu horretan:

do i = 0, N-1 A(i) = A(i) + 2.5 enddo

A bektoreak 128 osagai ditu, eta memoriako m0 modulutik aurrera dago metatuta.

a. Bete ezazu exekuzio-taula bat (hasiera, kateaketak, itxarote-zikloak, etab.) programa horretarako, prozesadore bakar batean exekutatzen den kasurako.

b. Errepikatu ariketa, baina kasu honetan bi prozesadore erabiltzen direla kontuan hartuz. Hau da prozesadoreen arteko lan-banaketa: P0 prozesadoreak bektorearen osagai bikoitiak (0, 2, 4...) prozesatzen ditu, eta P1 prozesadoreak bektorearen osagai bakoitiak (1, 3, 5...).

c. Errepikatu berriro ariketa, baina zortzi prozesadoreko kasurako. Lan-banaketa antzekoa da: P0 prozesadoreak (0, 8, 16...) osagaiak prozesatzen ditu; P1 prozesadoreak (1, 9, 17...) osagaiak; P2k (2, 10, 18...) osagaiak; eta P7k (7, 15, 23...) osagaiak. Marraztu memoria-moduluen okupazioa denboran zehar.

d. Makina horretan, programen exekuzioaren kostua X euro erloju-zikloko eta prozesadore bakoitzeko da. Aurreko hiru emaitzetan oinarriturik:

• zein kasutan exekutatzen da programa denbora gutxiagoan? • zein da aukera bakoitzaren kostua eurotan? • kalkulatu <zenbat bider azkarrago / zenbat bider garestiago> erlazioa (b) eta (c)

kasuetarako (a) kasuarekiko. e. Aurreneko atalaren emaitzak kontuan hartuz, kalkula itzazu, programa horretarako,

kalkulu-abiadura maximo teorikoa eta benetan lortzen dena (Mflop/s).

1.15. Hiru grafiko hauetan, "balizko" bektore-konputagailu batez lortutako kalkulu-abiadurak ageri

dira, N-ren arabera, ehuneko ehunean bektoriza daitekeen begizta bat exekutatu ondoren.

0 50

100 150 200 250 300

0 50 100 150 200

R(Mflop/s)

N

0 50

100 150 200 250 300

0 50 100 150 200

R (Mflop/s)

N

0

100

200

300

400

500

0 50 100 150 200

R(Mflop/s)

N

a. Adierazi hiru portaera horietatik zein dago(z)kio benetako bektore-konputagailu bati eta zergatik. Grafikoetatik atera daitezkeen datuetan oinarriturik, balioetsi R∞ eta N1/2 balioak.

b. Exekutatu den programak bektore-eragiketa hau bete du: A = A × B + C × D. Erlojuaren periodoa 3,33 ns da. Kalkula ezazu programaren exekuzio-denbora, bektoreen luzera N = 128 izanik.

c. Zenbat memoria-bus dago makina horretan? Kateatu egiten da aginduen exekuzioa?


1.16. Analiza itzazu bederatzi begizta hauen aginduen arteko datu-dependentziak, eta sortu dagozkien dependentzia-grafoak. Gero, erabaki begiztak bektoriza daitezkeen ala ez. Baiezkoan, idatz ezazu bektore-kodea.

Oharrak. A, B, C... izenek bektoreen hasiera-helbidea (0 osagaia) adierazten dute, hau da, A → A(0); A+1 → A(1)... Helbideratze-unitatea hitza da. Errenkadaka gorde dira matrizeak. Bektore-erregistroak 128 osagaikoak dira.

▪ 1. begizta do i = 1, 100 A(2*i+1) = B(100-i) enddo

▪ 2. begizta do i = 1, 100 (1) A(i) = A(i-1) + 1.0 (2) B(i) = A(i+1) enddo

▪ 3. begizta j = -1 k = 20 do i = 1, 100, 2 j = j + 4 A(j) = A(k) + 2 B(i) = A(j-2) k = k + 3 enddo

▪ 4. begizta do i = 1, 100 (1) A(i) = B(i+1) + 2 (2) B(i-1) = A(i) + A(i+2) enddo

▪ 5. begizta do i = 1, 128 (1) A(i) = X(i) + P(i-1) (2) B(i) = A(i) + A(i+1) (3) P(i) = X(2*i) + 3.0 (4) P(i+1) = B(i) * 2.0 enddo

▪ 6. begizta A[100,100];

do i = 0, 99 do j = 2, 99 A(i,j) = A(i,j-2) * 2 enddo enddo

▪ 7. begizta A[100,100];

do i = 0, 99 k = 2 do j = 0, 97 A(i,k) = A(i,k-2) + A(i+1,j) k = k + 1 enddo enddo

▪ 8. begizta A,B[100,100];

do i = 1, 98 do j = 2, 99 (1) A(i,j) = A(i,j-2) + B(i-1,j-1) (2) B(i,j) = B(i-1,j) + B(i+1,j) enddo enddo

▪ 9. begizta A,B[100,100];

do i = 2, 98 k = 0 do j = 1, 16 A(i,k+1) = A(i,k+2) + A(i+1,k+1) B(i,k+1) = A(i-2,k) + 1 k = k + 1 enddo enddo

1.17. a. Analiza itzazu begiztaren dependentziak eta marraztu dependentzia-grafoa. Bektoriza

daiteke begizta? Baiezkoan, idatzi bektore-kodea.

do i = 2, 100 (1) D(i) = A(2*i+5) + 3 (2) A(2*i+3) = B(i+1) + C(i+1) (3) B(2*i) = A(3*i-4) * C(i) enddo


b. Begiztak bektorizatzean, ohikoa da bi begizta bat bihurtzea (begizten fusioa). Erabil daiteke teknika hori kasu honetan?

do i = 0, 99 A(i) = B(i) + C(i+1) enddo do i = 0, 99 C(i) = A(i+2) + 3 enddo

c. Bektoriza daiteke begizta hau? Baiezkoan, idatzi bektore-kodea.

do i = 1, 100, 2 A(i) = A(99-i) + B(2*i) endd

1.18. Bi begizta hauek exekutatu behar dira bektore-konputagailu batean:

j = 2 k = -1 do i = 1, 100 k = k + 2 A(100-i) = A(k)*B(i+1) + 3.0 C(j) = C(j+1) enddo

j = 2 k = -1 do i = 1, 100 k = k + 2 A(200-2*i) = A(k)*B(2*i+1) + 3.0 C(j+1) = C(j) enddo

a. Bektoriza daitezke begiztak? Zergatik? Baiezkoan, idatz ezazu bektore-kode ahalik eta eraginkorrena.

b. Bektoriza daitekeen begiztaren exekuzioa analizatu behar da, ezaugarri hauek dituzten lau bektore-konputagailutan:

busak kateaketa Tzikloa 1 ez 1 ns 1 bai 1,25 ns 2 bai 1,75 ns 3 ez 1,5 ns

Kode bektorialarekin batera, kode eskalarra ere exekutatu behar da. Analisia sinplifikatzeko, demagun kode eskalarrak 200 ziklo behar dituela eta kode bektorialaren hasiera-denbora 30 ziklo dela, lau kasuetan. Balioetsi programa osoa exekutatzeko behar den denbora, aurreko makinen artean onena aukeratzeko.

c. Aukeratutako makinarako eta bektore-koderako bakarrik, kalkula itzazu ohiko parametroak: R∞, N1/2 eta RN. Zein da programa osoaren kalkulu-abiadura, Mflop/s-tan, kode bektoriala eta kode eskalarra kontuan hartuz?

1.19. a. Analizatu begizta honen dependentziak, marraztu dependentzia-grafoa, eta, aukeran, idatzi

bektore-kodea.

N = 32 P = 70 R = -2 do i = 1, N R = R + 2 A(R) = A(i+P) + 4 B(R+6) = B(i+1) + A(R+2) enddo

b. Begizta-trukea ohiko bektorizazio-teknika bat da. Erabil daiteke begizta honetan? Zergatik?

do i = 1, N1 do j = 1, N2 A(i,j) = A(i-1,j+1) + A(i,j-1) enddo enddo


1.20. Bektore-prozesadore batek honako programa hau exekutatu behar du:

LV V0,B(R1) LV V1,C(R1) ADDV V2,V0,V1 ADDVI V3,V2,#2 SV A(R1),V2 SV C(R1),V3

Konputagailuaren ezaugarriak

Aginduen segmentazio-eskema: B/D - Ir - AM - M (6) - Id B/D - Ir - A(3) - Id Memoria: 16 modulu, 2 bus Erloju-maiztasuna: 500 MHz 128 osagaiko bektore-erregistroak Batugailu bat Aginduak kateatu egin daitezke

A, B eta C bektoreen pausoa s = 2 da, eta luzera N = 128.

a. Bete ezazu programari dagokion exekuzio-taula, eta erabaki non kokatu behar diren bektoreak memoria-gatazkak saihesteko. Kalkula itzazu lor daitekeen kalkulu-abiadura maximoa, maximo horren erdia lortu ahal izateko behar den bektore-luzera, eta benetan lortzen den abiadura.

b. Ariketa errepikatu gabe, analiza itzazu bi hobekuntza hauek: - bus bat gehiago - batugailu bat gehiago Adierazi lortuko diren abantailak kasu bakoitzean (N handia izanik) eta zergatia.

1.21. A = B × C + D bektore-eragiketa exekutatu behar da bektore-konputagailu batean; egindako

analisien arabera, eragiketaren exekuzio-denbora 30 + 2N ziklo izan beharko litzateke. Hala ere, analisi horietan ez da kontuan hartu bektore-erregistroen tamaina: 128 osagai, alegia; beraz, bektoreak luzeagoak badira, begizta bat antolatu beharko da (strip mining). Makina horren erlojua 500 MHz-ekoa da, eta begizta eskalarra kontrolatzeko behar den denbora tbeg = 10 ziklo da.

a. Kalkula ezazu R∞, kalkulu-abiadura maximoa (Mflop/s-tan), bektore-erregistroen tamaina kontuan hartu gabe.

b. Marraztu itzazu grafiko banatan TB, exekuzio-denbora, eta R, kalkulu-abiadura, N-ren arabera, kasu errealerako, hau da, erregistroen tamaina kontuan hartuz.

c. Kalkula ezazu R∞ berria. Zein da kalkulu-abiaduraren galera (%)? Ondoren, froga ezazu balio maximo hori N = Lmax luzerako bektoreekin lortzen dena dela.

1.22. Bi modutan exekuta daitezke programak bektore-konputagailu jakin batean: eskalarki, non

RE = 400 Mflop/s baita, eta bektorialki, non RB = 2.000 Mflop/s baita. Izan bedi f kodearen bektorizazio-faktorea, batez beste.

a. Sortu adierazpen bat konputagailu horretan lor daitekeen batez besteko kalkulu-abiadurarako (RBE), eta marraztu funtzio hori f-ren arabera, 0 < f < 1.

b. Kalkula ezazu behar den bektorizazio-faktorea RBE = 1.200 Mflop/s lortu ahal izateko (maximoaren % 60a).

c. f = 0,7 izanik, zein izan beharko luke bektore-prozesadoreko kalkulu-abiadurak, RB, baldin eta RBE = 1.200 Mflop/s lortu behar bada?

1.23. Programa hau exekutatu behar da bektore-konputagailu batean:

s = 3 k = 1 do i = 1, 100 k = k + 1 X(i) = P(i-1) + R(i-1) P(i) = R(k) + R(2*k-1) E(i) = X(s) / 2 R(i) = X(k-2) + P(i+1) s = s + 2 enddo

Analiza itzazu begiztaren dependentziak eta marraztu dependentzia-grafoa. Gero, erabaki programa bektoriza daitekeen. Baiezkoan, idatz ezazu bektore-kodea.


1.24. Begizta hau exekutatu behar da bektore-konputagailu batean:

do i = 1, 128 (1) A(i) = A(i+1) + 1 (2) B(i) = A(i) + B(i) (3) D(2*i+1) = A(i-1) + B(i+1) + C(i-1) (4) A(i+1) = 2 * B(i) (5) C(i) = B(i) + C(5) enddo

Analiza itzazu begiztaren dependentziak, eta marraztu dependentzia-grafoa. Gero, erabaki begizta bektoriza daitekeen, eta, baiezkoan, idatzi bektore-kodea.

1.25. "Bektore-konpiladore" batek sortu omen du, ezkerreko begiztarako, bektore-kode hau:

k = 4 do i = 1, 31 A(i) = B(i) + 2 A(i+2) = A(k-1) * A(i) + C(i) k = k + 2 enddo

MOVI R1,#0 MOVI VL,#31 MOVI VS,#1

LV V1,B(R1) ADDVI V2,V1,#2 SV A(R1),V2

LV V3,A-1(R1) LV V4,A(R1) MULV V5,V4,V3 LV V6,C(R1) ADDV V7,V5,V6 SV A+2(R1),V7

a. Bektore-kodean errore batzuk daude. Adierazi zein diren, zergatia, eta zuzendu itzazu. b. Zuzendu ondoren, programa 750 MHz-eko erlojua duen bektore-konputagailu batean

exekutatu da, eta honako parametro hauek lortu dira: R∞ = 750 Mflop/s eta N1/2 = 60. Kalkula ezazu programaren exekuzio-denbora bektoreen osagaien kopuruaren arabera.

Azken adierazpen horretatik abiatuta, ondoriozta itzazu prozesadore horren memoriarako bus kopurua eta aginduen exekuzioa kateatzen den ala ez.

1.26. Izan bedi begizta hau:

do i = 0, 63 do j = 0, 63 S(k,j) = S(k,j) + 2 * A(i,j) enddo enddo

Ezaugarri hauek dituen bektore-konputagailu batean exekutatu behar da begizta: bektore-erregistroak, 64 hitzekoak; memoria-bus bakar bat (LV/SV); aginduak kateatu egin daitezke; th = 40 ziklo (eragiketa horietarako); tbeg = 15 ziklo (begizta eskalarrak gehitzen duen ziklo kopurua); F = 800 MHz.

a. Idatzi bektore-kodea begiztarako, eta kalkula itzazu exekuzio-denbora, kalkulu-abiadura (MF/s) eta eraginkortasuna (%). S matrizearen k errenkada helbideratzeko desplazamen-dua R5 erregistroan dago.

b. Analizatu emaitzak eta erabaki non dagoen kalkulu-abiadura mugatzen duen arazoa (makina kontuan harturik). Hori dela eta, berridatzi kodea, arazoa konponduta, eta birkalkulatu (a) ataleko parametroak.

1.27. Konparatu egin behar dira ezaugarri desberdineko bi bektore-konputagailu hauek:

1. konputagailua

- F = 500 MHz - 64 hitzeko bektore-erregistroak - aginduen kateaketa - bi bus memoria atzitzeko (LV/SV)

- batugailu bat eta biderkagailu bat - th = 40 z tbeg = 15 z

2. konputagailua

- F = 500 MHz - 64 hitzeko bektore-erregistroak - aginduen kateaketa - bi bus memoria atzitzeko (LV/SV)

- 3 batugailu eta 3 biderkagailu - th = 120 z tbeg = 15 z


a. Zein da makina horiekin lor daitekeen kalkulu-abiadura gorena (peak performance)? b. Begizta hau exekutatu da:

do i = 0, 9999 A(i) = 5 * A(i) * A(i) * A(i) + 1 enddo

Kalkula itzazu exekuzio-denbora eta kalkulu-abiadura (Mflop/s) bi makinetan. c. Errepika ezazu aurrekoa, baina begizta honekin:

do i = 0, 99 A(i) = 5 * A(i) enddo

Zer ondorio ateratzen dituzu aurreko emaitzetatik? 1.28. Irudiko grafoetan, bi begizten datu-dependentziak ageri dira. Idatz itzazu grafoekin bat

datorren begizta bana, ahalik eta sinpleena. Gero, esan bektoriza daitezkeen ala ez. Baiezkoan, idatzi bektore-kodea. Matrizeak 100 × 100 osagaikoak dira.

1. kasua: iterazio-espazioa (agindu bakar bat). 2. kasua: dependentzia-grafoa zein iterazio-espazioa.

1.29. Irudietan, datu-dependentziak adierazten dituzten lau grafo ageri dira. Idatz itzazu grafo

horiekin bat datozen begiztak, eta erabaki bektoriza daitezkeen ala ez. Baiezkoan, idatzi bektore-kodea.

(a) (b) (c) (d)

1.30. Honako kode hau exekutatu behar da bektore-konputagailu batean:

LV V0,A(R1) MULVI V1,V0,#3.0 LV V2,B(R1) MULVI V3,V2,#2.0 ADDV V4,V1,V3 SV D(R1),V4

Prozesadoreko erlojua 1,25 ns-koa da, eta bektore-prozesadorearen eta prozesadore eskalarraren arteko abiadura-erlazioa K∞ = 5 da.

a. Aurreko programaren exekuzio-denbora 2N ordenakoa izan da. Adierazi, eta arrazoitu, konputagailu horren ezaugarri nagusiak: unitate funtzionalak, busak, kateaketa.

b. Demagun exekuzio-denbora TB = 30 + 2N izan dela. Zein da programa horrekin lortuko den kalkulu-abiadura Mflop/s-tan, bektoreak 128 osagaikoak badira?

c. Kode eskalarrekin batera exekutatuko da aurreko kodea. Kalkula ezazu f-ren balio minimoa (bektoriza daitekeen kode-frakzioa), gutxienez aurreko kalkulu-abiaduraren erdia lortu ahal izateko.

j

i

j

i

1

2

3

1

2

3

1

2

A, (1,–1)

1

2

2 1

3


1.31. Ebatzi oinarrizko ariketa hauek.

1. Bektore-konputagailu (BK) batek badu 5 UF, eta erlojua 500 MHz-ekoa da. Zein da konputagailu horrek lor dezakeen kalkulu-abiadura gorena (peak)?

2. Memoriako busak oso garrantzitsuak dira bektore-konputagailuetan. Diseinatzen ari garen

BK batean, memoria 32 modulutan tartekatuta dago; memoriako erantzun-denbora 12,5 ns da, eta erlojua 800 MHz-ekoa da. Zenbat memoriako bus jarriko zenuke sistema horretan?

3. Bektore-konputagailu baten memoria bytez byte helbideratzen da. Begizta jakin batean,

matrize baten diagonal nagusia prozesatzen da. Matrizea 64 biteko 128×128 osagaikoa da, eta errenkadaka gorde da, ondoz ondoko posizioetan. Zein da matrizearen diagonalak definitzen duen bektorearen pausoa?

4. Zein izan behar du VS erregistroaren edukiak begizta honen A bektorea irakurtzerakoan, B

bektorea irakurtzerakoan, eta C bektorea idazterakoan?

do i = 3, 100 k = k – 3 C(k) = A(2*j-1) + B(i-3) j = j + 5 enddo

5. Bektore-konputagailu baten memoria 16 modulutan tartekatuta dago, eta haren latentzia 4

ziklo da. Kode zati hau exekutatu behar da makina horretan (A bektorearen osagaiak ondoz ondoko memoria-helbideetan daude). Zenbat aldiz atzituko da memoriaren m12 modulua? Eta m14 modulua?

MOVI VL,#100 MOVI VS,#4 LV V2,A+2(R1) ; hasieran R1 = 0 da, eta A0 osagaia m0 moduluan dago

6. Bektore-konputagailu baten erloju-zikloa 2 ns da. Zein da kalkulu-abiadura maximoa

(Mflop/s) begizta hau exekutatzen denean, honako kasu hauetan?

do i = 0, N-1 Z(i) = (Z(i) + 1) * 2 enddo

a. Memoriako bus bat, eta kateaketarik gabe b. Memoriako bi bus, eta kateaketarik gabe c. Memoriako bus bat, eta kateaketa d. Memoriako bi bus, eta kateaketa

7. Honako begizta hau exekutatu behar da bektore-konputagailu batean:

do i = 1, N A(i) = B(i) + C(i) D(i) = A(i) * A(i) enddo

a. Konputagailuak bi bus ditu memoria atzitzeko, eta ez du aginduen exekuzioa kateatzen.

Adierazi, argudiatuz, exekuzio-denboraren ordena (optimoa, N-ren arabera). b. Begizta horren exekuzio-denbora neurtu da, N-ren bi balio jakinetarako, eta honako

emaitza hauek lortu dira: T(20) = 200 ns eta T(70) = 600 ns. Kalkula itzazu R∞ (MF/s) eta N1/2 parametroen balioak begizta eta makina horretarako. Zein da konputagailuaren erlojuaren maiztasuna?


8. Bi dimentsioko begizta hau exekutatu behar da bektore-konputagailu batean. Bektore-eragiketaren denbora TB = 20 + 2N ziklo gisa adieraz daiteke, eta kanpo begiztaren kontrola 15 ziklo iterazioko da. Begizta-trukea egingo bagenu, nolakoa litzateke exekuzioa?

do i = 0, 99 do j = 0, 9 A(i,j) = A(i,j) * B(i,j) enddo enddo

a. 10 aldiz azkarragoa b. 10 aldiz motelagoa c. 2 aldiz azkarragoa d. 2 aldiz motelagoa e. begizta horiek ezin dira trukatu

9. Bektoriza daiteke begizta hau? Ezezkoan, esan zergatik; baiezkoan, idatzi dagokion bektore-

kodea.

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

10. Erabil daiteke begizta-trukea bi kasu hauetan? Zergatik?

do i = 1, N-1 do j = 0, N-2 A(i,j) = A(i-1,j+1) / 2 enddo enddo

do i = 1, N-1 do j = 1, N-1 A(i,j) = A(i-1,j-1) / 2 enddo enddo

11. Dagoen moduan, begizta hau ez da oso egokia bektorizatzeko. Esan zergatik, eta alda ezazu

begizta bektorizazioa errazagoa izan dadin.

do i = 0, N-1 if (X) then A(i) = B(i) else A(i) = C(i) enddo

12. Irudian, begizta baten dependentzia-grafoak ageri dira.

Idatz ezazu grafoekin bat datorren begizta bat, ahalik eta sinpleena. Erabil itzazu 100×100 tamainako matrizeak. Gero, esan bektorizagarria den ala ez, eta, baiezkoan, idatz ezazu dagokion bektore-kodea.

13. BK batek 1.000 Mflop/s lor ditzake programa jakin batean bektoreak prozesatzen, baina

programa horren bektorizazio-faktorea f = 0,8 da (bektoreak oso luzeak dira). Zenbat Mflop/s lortuko ditu, prozesadore eskalarra 10 aldiz motelagoa bada bektoreak prozesatzen? Zenbat izan behar du f-k 700 Mflop/s eskuratu ahal izateko?

14. Irudiko grafoan, bi dimentsioko begizta baten balizko

dependentziak ageri dira, iterazio-espazioan marraztuta (do i = 0… / do j = 0…; bektoreak lerroka gordeta). Argi eta garbi, ez da zuzena. Zergatik?

15. Lau dimentsioko begizta baten aginduen artean, (i = 2, j = –1, k = 0, m = 4) distantziako

dependentzia bat dago. Zenbat begizta-truke (ordena-aldaketa) zilegi egin daitezke begizta horretan?

16. Egiazkoa ala faltsua?

▪ 2.000 Mflop/s lor dezakeen BKa, 1.000 Mflop/s lor dezakeena baino hobea da beti. ▪ Bektore-konputagailuak oso azkarrak dira kalkulu eskalarra egiten.

1

2 A(1,–1)

A(0,1)

j=0 1 2 … i=0

1

…


▪ Bektore luzeak kontuan hartuz, bektorizazio-faktorea f = 2/3 denean lortuko den kalkulu-abiadura, abiadura maximoaren 2/3 izango da. Aurrekoa ez da egia bektoreak oso luzeak ez badira.

▪ Dependentziak analizatzeko probak (ZKH) positibo ematen badu (zenbaki osoa), dependentzia bat markatu behar da dependentzia-grafoan.

▪ ZKH probak negatibo ematen badu (emaitza ez da zenbaki osoa), agian ez dago dependentziarik.

▪ Bektore-erregistroen tamainak mugatu egiten du BKen kalkulu-abiadura. ▪ Bektore-konpiladore on bat lagungarria da beti, baina, aukeran, hobe da dirua hardwarean

gastatzea. ▪ Memoriako banda-zabalera biziki garrantzitsua da bektore-konputagailuetan. ▪ Ondo egiten bada, bektoreak prozesatzen dituen programa oro bektoriza daiteke. ▪ Bektorizatzen denean, jatorrizko kodea desordenatu egiten da. 75-95 urteetan, desordena

modan zegoen eta BKek arrakasta handia lortu zuten. Gaur egun, aldiz, ordena inposatu egin da, eta, ondorioz, BKak desagertzen ari dira astiro-astiro.

▪ Egokia da BK batean unitate funtzional asko eta segmentatuta izatea, memoria modulu askotan tartekatuta izatea, eta memoriako bus asko izatea.

▪ Amdahl-en arabera, ezin da programa bat idatzi zeinaren bidez kalkulu-abiadura maximoa lortuko den.

1.32. Exekutatu behar dira, bektore-konputagailu batean, honako lau begizta hauek. Analiza itzazu

aginduen arteko datu-dependentziak eta marraztu dagozkien dependentzia-grafoak. Grafoetan oinarrituta, erabaki begiztak bektoriza daitezkeen ala ez. Baiezkoan, idatzi bektore-kodea.

▪ 1. begizta [bektore-erregistroak 128 osagaikoak dira] do i = 2, 1018 (1) B(i) = A(i) + 2 (2) C(i+5) = E(2*i) + 10 (3) D(i+5) = D(i-2) + C(i-1) (4) C(i)= B(i+2) * B(i) enddo

▪ 2. begizta k = 1 m = 2 do i = 3, 100 m = m + 3 A(i+1)= B(i) C(i) = D(i+1) * A(i) * A(m) D(m) = D(k+2) + 3 k = k + 2 enddo

▪ 3. begizta A[20,50];

do i = 0, 18 do j = 1, 49 A(i,j) = (A(i+1,j) + A(i,j-1)) / 2 enddo enddo

▪ 4. begizta A[128,8];

do i = 1, 125 do j = 0, 5 (1) A(i,j) = A(i-1,j+2) * 3 (2) B(i,j) = B(i+2,j) + A(i,j) enddo enddo

Ariketak: Konputagailu paraleloak (oinarrizko kontzeptuak) ▪ 17 ▪

2.1. Azaldu, zehatz eta labur, konputagailu paraleloen bi eredu nagusien ezaugarri behinenak. 2.2. Aplikazio jakin bat 32 prozesadoreko multiprozesadore batean exekutatu da. Kodearen % 10

32 prozesadoreetan exekutatu da; % 70, 16 prozesadoretan; eta gainerakoa, 4 prozesadoretan. Beste arazorik kontuan hartu gabe, kalkula itzazu lortutako azelerazio-faktorea (speed-up) eta eraginkortasuna (efficiency).

2.3. Programa batek bi zati ditu, f1 eta f2; bi zatiak (funtzioak) bata bestearen ondoren exekutatu

behar dira, eta haien exekuzio-denbora berdintsua da, T. Aurreneko zatia edozein prozesadore kopuru erabiliz exekuta daiteke paraleloan, eta ez dago gainkargarik; bigarrenarekin, ordea, ezin dira 8 prozesadore baino gehiago erabili. P prozesadoreko sistema bat erabili da programa hori exekutatzeko. Kalkula itzazu:

a. Azelerazio-faktorea P-ren arabera, eta, ondorioz, azelerazio-faktore teoriko maximoa. b. Erabili behar den prozesadore kopurua eraginkortasuna 0,5 izan dadin, eta kasu horretan

lortuko den azelerazio-faktorea. 2.4. 8 prozesadoreko makina paralelo bat erabiltzen da aplikazio bat exekutatzeko, Exekuzioan

zehar, 8 prozesadoreak batera 50 segundotan erabiltzen dira; 4 prozesadore, 20 segundotan; eta prozesadore bakarra, 30 segundotan. Prozesadoreen artean banatzen den karga orekatuta dago, baina kalkulu paraleloko kasuetan gainkarga bat izan da, exekuzio-denboraren % 10 hain zuzen ere.

Kalkula itzazu lortu den azelerazio-faktorea (speed-up) eta eraginkortasuna (efficiency). 2.5. Aplikazio jakin bat exekutatu behar da paraleloan, P prozesadore erabiliz. Paraleloan

exekutatzen denean, serieko exekuzioaren segundo bakoitzeko, komunikazio-prozesu bati ekin behar zaio, eta haren kostua honela adieraz daiteke: 40 + 16×P1/2 milisegundo.

Beste arazorik kontuan hartu gabe, kalkula itzazu lor daitekeen azelerazio-faktore maximoa eta hori lortzeko erabili behar den prozesadore kopurua. Marraztu itzazu exekuzio-denbora, azelerazio-faktorea eta eraginkortasuna, Pren arabera.

2.6. Aplikazio paralelo jakin baten zati bat arazorik gabe paraleliza daiteke, baina beste bat

seriean exekutatu behar da, nahitaez. 64 prozesadoreko makina bat erabiltzen da aplikazioa exekutatzeko.

a. Aplikazioaren portaera Amdahl-en legearen araberakoa da. Kalkula itzazu, batetik, seriean exekutatu behar den programaren frakzio maximoa, f, baldin eta eraginkortasunak gutxienez % 50 izan behar badu, eta, bestetik, lortuko den azelerazio-faktorea f = 0,9 denean.

b. Aplikazioaren portaera Gustafson-en legearekin bat dator. Kalkula ezazu lortuko den azelerazio-faktorea f = 0,9 denean.

2.7. Kalkulu-algoritmo jakin baten exekuzio-denbora prozesadore batean 24 ms da; kalkulu hori hainbat aldiz errepikatu behar da, eta, beraz, analizatu nahi dugu ea merezi duen cluster batean paraleloan exekutatzea. Bertsio paraleloan, kalkulua oso modu eraginkorrean banatu daiteke prozesadoreen artean, baina komunikazioa gehitu behar da: hasieran, datuak banatzeko, eta bukaeran, emaitzak biltzeko. Hala, 8 prozesadoreko konputagailu batean paraleloan exekutatzen denean, lortzen den eraginkortasuna % 50 da.

Emaitza hori hobetzeko asmoz, kalkulua "finago" (kalkulu gehiago) egitea erabaki da; ondorioz, prozesadore bakarreko exekuzio-denbora 10 aldiz handiagoa da orain. Zein izango dira lortuko ditugun azelerazio-faktorea eta eraginkortasuna algoritmoa 8 prozesadoretan exekutatzen denean?

Egin dugun analisiaren arabera, badakigu komunikazioaren kostua logaritmikoki hasten dela prozesadore kopuruarekiko. Zein izango dira lortuko ditugun azelerazio-faktorea eta eraginkortasuna 8 prozesadore erabili beharrean 64 prozesadore erabiltzen baditugu?


2.8. Aplikazio jakin baten exekuzio-denbora 32 segundo da. Exekuzioa azkartzeko, P prozesadoreko MPP makina bat erabili nahi da. Badakigu kalkulua idealki banatu daitekeela prozesadoreen artean, baina, paraleloan exekutatzeagatik, prozesuen arteko komunikazioak gainkarga bat sortzen du. 16 prozesadoretan exekutatu denean, lortu den azelerazio-faktorea 8 izan da; 32 prozesadoretan, ordea, 10,67.

a. Datu horietan oinarrituta, kalkula ezazu komunikazioaren kostua prozesadore kopuruaren arabera.

b. Kalkula ezazu lor daitekeen azelerazio-faktorerik handiena, eta erabili beharko dugun prozesadore kopurua eraginkortasuna % 25etik jaitsi ez dadin.

Ariketak: Datuen koherentzia SMP konputagailuetan ▪ 19 ▪

3.1. SMP motako multiprozesadore bat osatzeko, lau prozesadore konektatu dira bus baten bidez. Prozesadoreek bi hitzeko cache memoria bana erabiltzen dute. Blokeak hitz batekoak dira, cachearen egitura guztiz elkargarria da, eta datu-blokeen ordezkapen-politika zorizkoa da. Datuen koherentzia ziurtatzeko, zelatatze motako hardwarea eta Illinois koherentzia-protokoloa (MESI) erabiltzen dira.

Une jakin batean, memoria-sistemaren egoera honako hau da:

CM-P0 CM-P1 CM-P2 CM-P3 Memoria nagusia

bl eg dat bl eg dat bl eg dat bl eg dat @0 –1 @1 5

1 E 5 1 I –3 2 S 9 2 S 9 @2 9 @3 10 2 S 9 5 E 2 3 M 6 4 M 0 @4 10 @5 2

eta, segidan, memoria-eragiketa hauek exekutatzen dira:

rd0 (@1) wr0 (@1, 22) wr2 (@2, –11) rd1 (@4) rd2 (@5) rd0 (@0) rd3 (@0) wr1 (@1, 8)

[rd0 (@1): irakurketa CM-P0 cachean, helb = 1; wr0 (@1, 22), idazketa CM-P0 cachean, helb = 1, dat = 22]

Eragiketa bakoitzerako, adierazi cachean asmatu edo huts egin den, sortuko diren kontrol-seinaleak eta datu-trafikoa, eta cacheen zein memoria nagusiaren azken edukiak (eragiketa bakoitzerako, errepikatu aurrekoa bezalako taula bat).

3.2. SMP motako multiprozesadore batek lau prozesadore ditu bus baten bidez konektatuta.

Prozesadoreen cacheak bi blokekoak dira, blokeen tamaina hitz bat da, eta egokitasuna zuzenekoa da. Datuen koherentzia ziurtatzeko, baliogabetze motako Berkeley (MOSI) koherentzia-protokoloa erabiltzen da.


CM-P0 CM-P1 CM-P2 CM-P3 Memoria nagusia

bl eg dat bl eg dat bl eg dat bl eg dat @0 32 @1 –4

0 O 6 4 I 2 2 O 6 0 S 6 @2 10 @3 10

5 M 3 7 I –3 1 I 9 3 M 7 @4 2 @5 7

eta memoria-eragiketa hauek exekutatzen dira, bata bestearen atzetik:

rd1 (@0) rd2 (@5) wr3 (@0, 2) wr1 (@3, –5) wr3 (@0, 13) rd2 (@1) rd0 (@1) wr2 (@2, –9)

[rd1 (@0): irakurketa CM-P1 cachean, helb = 0; wr3 (@0, 2), idazketa CM-P3 cachean, helb = 0, dat = 2]

Eragiketa bakoitzerako, adierazi cachean asmatu edo huts egin den, sortuko diren kontrol-seinaleak eta datu-trafikoa, eta cacheen zein memoria nagusiaren azken edukiak.

3.3. SMP motako multiprozesadore batek bus baten bidez konektatutako lau prozesadore ditu.

Cacheak bi hitzeko bi blokekoak dira eta egokitasuna zuzenekoa da. Datuen koherentzia mantentzeko, Dragon protokoloa (MOES(I), eguneratzea) erabiltzen da.


CM-P0 CM-P1 CM-P2 CM-P3 Memoria nagusia bl eg dat bl eg dat bl eg dat bl eg dat @0-3 3 9 4 6

4 M 6 0 2 E 8 –1 @4-7 8 –1 7 6 3 S 7 6 @8-11 6 5 0 0

eta memoria-eragiketa hauek exekutatzen dira, segidan:

rd0 (@4) rd1 (@9) wr1 (@8, –1) wr3 (@7, 5) wr2 (@6, –3) rd1 (@0) wr3 (@3, 9) wr2 (@7, 0)

[rd0 (@4): irakurketa CM-P0 cachean, 4 helbidean; wr1 (@8, –1): idazketa CM-P1 cachean, 8 helbidean, dat = –1]

Eragiketa bakoitzerako, adierazi cachean asmatu edo huts egin den, sortuko diren kontrol-seinaleak eta datu-trafikoa, eta cacheen zein memoria nagusiaren azken edukiak.


3.4. Multiprozesadore baten cacheetako datu-blokeen kopiak kudeatzeko, bi estrategia erabiltzen dira: kopia bat aldatzen denean, gainerako kopiak baliogabetu edo eguneratu egiten dira. Zein da aukerarik onena? Oro har, aplikazioaren araberakoa da. Esaterako, kontuan hartu bi aplikazio hauek:

A aplikazioa (N prozesu paralelo)

Errepikatu K aldiz { P0 prozesuak X aldagaian idazten du; P1—PN–1 prozesuek aldagai hori

irakurtzen dute; }

B aplikazioa (2 prozesu paralelo)

Errepikatu K aldiz { P0 prozesuak M aldiz idazten du X

aldagaian; P1 prozesuak X aldagaia irakurtzen du; }

Bi kasuetarako, kalkula ezazu koherentzia mantentzeko sortuko den buseko trafikoa (1) baliogabetze-protokolo bat erabiltzen bada; eta (2) eguneratze-protokolo bat erabiltzen bada (bi kasuetan, write-back motako idazketa).

Hau da ekintza bakoitzean sortzen den trafikoa:

datuak helbideak kontrola - Cacheko hutsegitea: 64 byte 5 byte 1 byte - Baliogabetze-eragiketa: – 5 byte 1 byte - Eguneratze-eragiketa: 8 byte 5 byte 1 byte

Adibide gisa, hartu K = 10, N = 16 eta M = 10. 3.5. Aplikazio bat ari da exekutatzen SMP motako multiprozesadore batean. Une jakin batean,

sistemako lau prozesadorek cacheetan ez duten aldagai bera irakurtzen dute (1, 2, 3, 4 ordenan). Adierazi nola geratuko den aldagai hori duen datu-blokea cache bakoitzean eta sortuko den trafikoa, koherentzia-protokoloa hauetako bat izanik:

a. E, M, S eta I egoerak erabiltzen dituen baliogabetze-protokoloa. b. M, S eta O egoerak erabiltzen dituen eguneratze-protokoloa.

Errepikatu aurrekoa, baina beste kasu honetan: prozesadoreek idazketa bana egiten dute aldagaian. Idazketa-politika write-back da.

3.6. SMP motako multiprozesadore batean, honako memoria-eragiketa hauek exekutatzen dira,

segidan:

rd0 (@1) rd1 (@0) wr2 (@3, 2) wr1 (@0, 4) rd0 (@2) wr1 (@2, 5) wr2 (@1, 3) rd2 (@5)

Adibiderako, demagun cacheak bi blokekoak direla eta blokeak bi hitzekoak. Cacheen egokitasuna zuzenekoa da. Hasieran, cache guztiak hutsik daude eta memoriaren edukia 0 da, posizio guztietan.

Adierazi nola aldatuko diren cache memorien eta MNaren edukiak (eragiketaz eragiketa), baita sortzen diren kontrol-seinaleak eta trafikoa ere, bi kasu hauetan: (a) koherentzia-protokoloa MESI (Illinois, baliogabetu) da; eta (b) koherentzia-protokoloa MOES(I) (Dragon, eguneratu) da.

3.7. Ezaugarri hauek dituen koherentzia-protokoloa erabiltzen da multiprozesadore batean:

zelataria, eguneratze-protokoloa, eta write-back motako idazketa. Kontrol-automatak 2 egoera erabiltzen ditu datu-blokeetarako: O eta S.

a. Deskriba ezazu koherentzia-protokoloa trantsizio-taula eta grafo baten bidez; adierazi sortuko diren kontrol-seinaleak eta datu-transferentziak.

b. Demagun hitz bakarreko cache bana duten hiru prozesadore daudela sistema horretan. Hiru cacheak hutsik daude, eta memoriaren edukia hau da: M(@1) = 0, M(@2) = 7.

Adieraz itzazu cache bakoitzaren egoera eta edukia, eta M(@1)-en eta M(@2)-ren edukia, memoria-eragiketa hauek exekutatzen direnean, banan-banan:

rd1 (@1), rd2 (@1), rd3 (@1), wr1 (@1, 4), wr2 (@1, 5), rd2 (@2), rd1 (@2)


3.8. Cachean aldagai bat aldatu behar denean, write-back (WB) edo write-through (WT) idazketa-politikak erabil daitezke. Aldagaien erabileraren arabera, zenbait kasutan egokiagoa da idazketa mota bat, eta, beste batzuetan, ordea, bestea. Hori dela eta, hainbat koherentzia-protokolotan bi aukerak erabil daitezke, eta bata edo bestea aukeratu irizpide jakin baten arabera (apustu bat egiten da).

Adibide gisa, Write-Once koherentzia-protokoloa dugu, non WT erabiltzen baita aldagai bat lehenbiziko aldiz idazten denean, eta WB hurrengo idazketetan. Write-Once baliogabetze-protokolo bat da, eta I, E, M, eta S egoerak erabiltzen ditu. Ez du sh (shared) kontrol-lerroa erabiltzen (eta, beraz, ezin ditu E eta S egoerak bereizi kopia kopurua dela eta!).

Diseina ezazu koherentzia-protokolo hori: egoeren arteko trantsizioak, kontrol-seinaleak, datu-trafikoa...

3.9. Digital etxeko Alpha prozesadoreek zelatatze motako protokolo berezi bat erabiltzen zuten,

non bi idazketa-politikak (WT, WB) eta kopiak kudeatzeko estrategiak (INV, BC) nahasten ziren. Prozesadore horiek bi mailako cache memoria erabiltzen dute (barnekoa, CM1, eta kanpokoa, CM2), eta horren arabera erabakitzen da kopiekin zer egin bat aldatzen denean: kopia barneko cachean badago, eguneratu egiten da; bestela, bakarrik kanpoko cachean badago, baliogabetu egiten da. sh bezalako seinale batek kopia barneko cachean dagoen ala ez adierazten du: cm1 kontrol-lerroa. Beraz, kopia batzuk baliogabetu eta beste batzuk eguneratu egingo dira. Irudiko grafoan, koherentzia-protokoloari dagokion grafoa ageri da.

Analiza ezazu protokoloa, eta erantzun galdera hauei:

• Zer egoerak dira X eta Y? • Zer dela eta gertatzen dira 1, 2 eta 3 trantsizioak? Zer da 4? • Zein kasutan idatziko da bloke bat memoria nagusian? eta hitz bakar bat? • Zeren arabera erabiltzen da write-through edo write-back motako idazketa?

Laburpen gisa, idatz ezazu, taula batean, egoera batetik besterako trantsizioetan sortzen den buseko trafikoa.

3.10. Datuen koherentzia mantentzeko, R4000 prozesadoreak ezaugarri hauek dituen protokoloa

erabiltzen zuen: M, O, E, S eta I egoerak (baliogabetzea); write-back motako idazketa; sh kontrol-lerroa.

a. Adieraz ezazu protokolo horren portaera —egoeren arteko trantsizioak, sortzen diren kontrol-seinaleak, datu-trafikoa— taula zein grafo baten bidez.

b. Hiru prozesadoreko multiprozesadore batek koherentzia-protokolo hori erabiltzen du. Cacheak 4 hitzeko bloke bakarrekoak dira. Une jakin batean, hau da cacheen egoera (blokea / egoera / datuak):

CM0: 0 / M / 1, 3, 5, 7 CM1: 6 / S / 2, 4, 8, 0 CM2: 5 / E / 3, 3, 1, 1

Hiru memoria-eragiketa hauek exekutatuko dira, segidan, P2 prozesadorean: rd2 (@2), wr2 (@0, 10) eta rd2 (@25). Adierazi eragiketa horiek exekutatzean sortuko diren kontrol-seinaleak eta datu-trafikoa, eta nola aldatuko diren cacheen zein memoria nagusiaren egoera eta edukia.

PW (fault) = PR (fault) + PW (hit)

PW sh( ) PR BR

PR PR PW

PR PW sh (BC+BW*)

BR BC cm1

E

S

I

PW

Alpha

4

X

Y 2

PW nsh (BW) PR nsh (BR)

BC ncm1

PR sh (BR) PW nsh (BW*) BC ncm1 (BW)

1 3


3.11. Multiprozesadore batean, hiru SMP sistema lotzen dira bigarren mailako bus baten bidez; komunikazio-sarea, beraz, bi mailako bus-hierarkia bat da. Datuen koherentzia mantentzeko, zelatari hierarkikoa erabiltzen da (MSI egoerak).

Memoria-eragiketa hauek exekutatuko dira (denak datu-bloke berean eta ematen den ordenan): LD1, LD2, LD3, ST1, LD2, LD3, ST2, LD3, ST3 non LD/STx-k load/store eragiketa bat x multzoko prozesadore batean adierazten baitu (beti aldagai bera). Atzitzen den datu-blokea bigarren SMP sistemako memoriakoa da.

Adierazi taula batean eragiketa horiek exekutatzean nola aldatzen diren cacheen eta koherentziako kontroladoreen (KB eta KU) egoerak. Azaldu, laburki, gertatzen dena.

1. SMP 2. SMP 3. SMP h/a CM KU KB CM KU KB CM KU KB denbora LD1

Kalkula ezazu aurreko aginduak exekutatzeko behar den ziklo kopurua (koherentziari

dagokionean); bertako bloke baten atzipen-latentzia L ziklo da, eta kanpoko bloke batena 4L. Baliogabetze-ekintzen latentzia 4B da.

3.12. Erantzun galdera hauei, ahalik eta zehatzen.

1. Bloke bat cachean kargatzen denean, zeren arabera erabakitzen da E edo S egoeran jartzea, koherentzia-protokoloa MESI motakoa denean?

2. Datuen koherentzia ziurtatzeko, protokolo jakin batek lau egoera erabiltzen ditu: M, S, E eta

O. Gerta al daiteke, une jakin batean, datu-bloke baten kopia bakar bat izatea multiprozesadorean, O egoeran? Zergatik?

3. Aurreko kasu berean, gerta al daiteke S egoeran dagoen bloke bat memoria nagusian

dagoenarekin bat ez etortzea, hots, koherentea ez izatea? 4. MOESI protokolo batean (baliogabetzea), zein baldintzatan izan ditzakegu cacheetan datu-

bloke baten bi kopia M egoeran? 5. Datuen koherentzia mantentzeko MOES(I) motako eguneratze-protokolo bat erabiltzen

denean, igaro daiteke bloke bat O egoeratik M egoerara? Eta E egoeratik O egoerara? 6. Erabil daiteke beti write-back idazketa-politikaren "filosofia" MSI motako koherentzia-

protokoloetan? Eta MOSI motako protokoloetan? 7. Multiprozesadore jakin batean, memoria-bloke baten bi kopia daude cacheetan, biak S

egoeran. Hirugarren prozesadore batek bloke hori irakurri nahi du. Azaldu itzazu blokea eskuratzeko (nondik) aukera guztiak, eta bakoitzaren abantailak eta desabantailak. Eta bi kopien egoerak O eta S izango balira?

8. Koherentzia-protokolo jakin bat erabiliz, M egoeratik O egoerara igaro da cacheko bloke

bat. Zer dela eta gertatu da aldaketa hori? Zein izan da idazketa-politika? Eta trantsizioa O-tik S-ra bada?

9. Memoriako datu-bloke jakin bat egoera hauetatik igaro da cache batean: I → S → M → I.

Protokoloa baliogabetzekoa da. Gerta daitezke trantsizio horiek? Nola? Eta protokoloa eguneratzekoa balitz?


10. SMP makina batek zelatatze-protokolo bat erabiltzen du datuen koherentzia ziurtatzeko, eta, ahal denetan, idazketa-politika write-back da. Bi hitzeko datu-bloke jakin bat honako egoera hauetatik igaro da Pi prozesadorearen cachean [datuak / egoera]:

* – * / I → 3 – 4 / M → 6 – 4 / S a. Zein eragiketa exekutatu da lehenbiziko aldaketa gerta dadin? b. Zer gertatu behar da bigarren aldaketa izateko? c. Zer protokolo-mota erabili da? Zergatik? d. Bigarren aldaketa eta gero, zein izango da MNko edukia?

11. Bi prozesadoreko multiprozesadore batek zelatari bat erabiltzen du datuen koherentzia

ziurtatzeko. P1 prozesadorearen cacheko bloke bat egoera hauetatik igaro da: I → E → M → O → M → I. Zein egoeratan egon da datu-bloke hori P2 prozesadoreko cachean?

12. Zenbait multiprozesadoretan, cache memorien direktorioa bikoiztu egiten da. Zer dela eta? 13. Deadlock edo lasterketak saihesteko, blokeen egoera arruntez gain (E, M...), egoera

iragankorrak ere erabiltzen dira zelatatze-protokoloetan. Hori dela eta, handiagoa izan beharko du cacheetako direktorioak, bit gehiago sartzeko, egoera gehiago definitu ahal izateko?

14. Une jakin batean, datu-bloke bat bi cachetan dago kopiatuta, S egoeran. Une horretan, bi

prozesadoreek idatzi egiten dute bloke horretan. Azaldu, zehatz eta labur, nola konpontzen den lasterketaren arazoa zelatatze motako koherentzia-protokoloetan.

15. Hurrengo lau aukeretan, 2 hitzeko memoria-bloke baten balizko edukia eta egoerak

(zelataria), cacheetan zein memoria nagusian, ageri dira. Zuzenak dira? Ezezkoan, adierazi zergatia.

(a) C1: 0 / 2 E C2: — C3: — MN: 0 / 2 E (b) C1: 3 / 2 O C2: 0 / 2 S C3: 0 / 2 S MN: 0 / 2 (c) C1: 5 / 2 M C2: 3 / –9 M C3: — MN: 3 / 2 (d) C1: –1 / –1 E C2 –1 / –1 S C3: — MN: –1 / –1

16. Koherentzia-protokolo batek egoera hauek erabiltzen ditu: M, S, O, (I). Protokoloa

eguneratzekoa da; erabili behar da sh kontrol-lerroa? Eta protokoloa baliogabetzekoa balitz? Eman adibideak erantzuna argudiatzeko.

Ariketak: Prozesuen sinkronizazioa SMP konputagailuetan ▪ 25 ▪

4.1. LL eta SC aginduen bidez, ohiko agindu atomikoen portaera "simula" daiteke. Idatz itzazu agindu atomiko hauek bezala funtzionatzen duten kode zatiak, baina LL eta SC aginduak erabiliz:

a. Test&Set b. Swap c. Fetch&Inc d. Fetch&Add e. Compare&Swap

4.2. Erantzun galdera hauei modu zehatzenean.

1. Kode zati honekin sekzio kritiko bat osatu da, LL eta SC aginduak erabiliz. Ondo edo gaizki dago? Zergatik?

itxoin: LL R1,SAR BNZ R1,itxoin ; libre! sartu sekzio kritikoan

LD R2,i ; sekzio kritikoa ADDI R2,R2,#1 ST i,R2

MOVI R1,#1 SC SAR,R1 ; atera sekzio kritikotik BZ R1,itxoin ; ez duzu lortu, errepikatu RET

2. Eta beste sekzio kritiko hau?

itx1: MOVI R2,#1

itx2: LL R1,SAR BNZ R1,itx2 SC SAR,R2 ; itxi sarraila BZ R2,itx1 ; libre! sartu sekzio kritikoan

F&Inc i ; sekzio kritikoa

MOVI R2,#0 ST SAR,R2 ; utzi sekzio kritikoa (ireki sarraila) ...

3. Zertan lagundu dezakete denborizazioek txartelen metodoa erabiltzen duen lock errutina batean? Jarri adibide bat.

4. Aplikazio jakin bat paralelizatu egin da 16 prozesadorerako. Kodea analizatu eta zera ikusi da, jatorrizko exekuzio-denboraren % 10 prozesuak sinkronizatzen galtzen dela. Beste arazorik kontuan hartu gabe, kalkula ezazu espero daitekeen azelerazio-faktorea.

5. Sekzio kritiko baterako sarrera babestuta dago txartela/txanda teknika erabiltzen duen lock errutina batez. Prozesu batek errutina hori exekutatzen du eta txartela = 35 lortzen du; une horretan, txanda aldagaiaren balioa 30 da. Koherentzia-protokoloa baliogabetzekoa da. Sekzio kritikoan sartzeko txandaren zain dagoen bitartean, zenbat aldiz eskatu beharko du prozesu horrek txanda aldagaia duen datu-blokea, cache-hutsegiteak direla medio?

6. Egiazkoa edo faltsua? Arrazoitu erantzuna eta, behar izanez gero, zuzendu ezazu adierazpena. ▪ Agindu atomikoak exekutatzeko, hardwarearen laguntza behar da. ▪ Lagungarriak badira ere, kontu handiz programatzen bada, ez dago zergatik erabili behar

agindu atomikoak memoria partekatuko programa paraleloetan. ▪ LL eta SC aginduak atomikoak dira. ▪ Test-and-Test&Set aginduaren exekuzioa atomikoa da. ▪ Kode zati bat elkarrekiko esklusioan exekutatzen denean, buseko trafikoa minimizatzen da,

prozesadore bakarra izango dugulako kode hori exekutatzen. ▪ Sinkronizazio-hesi batean, ezin dira 16 prozesu baino gehiago sinkronizatu. ▪ LL eta SC aginduen bidez egindako lock funtzio soil batek eta txartelen metodoa

erabiltzen duenak ordena bereko trafiko-maila sortzen dute.


▪ Test&Set aginduaren bidez egindako lock errutina soila oso egokia da, baldin eta ez bada prozesuen arteko lehia handia espero sekzio kritikoan sartzeko.

▪ Ekoizle baten eta kontsumitzaile baten arteko sinkronizazioa adierazle baten bidez ez da oso egokia: adierazlea aldagai partekatua denez, batek idazten duenean besteak huts egingo du cachean, eta gero alderantziz; litekeena da, beraz, livelock arazoa agertzea: <idatzi – baliogabetu – idatzi – baliogabetu...> zikloan sartzea eta ezer erabilgarri egin gabe geratzea.

▪ Fetch&Increment aginduaren exekuzio-denbora ez da beti bera. ▪ Sinkronizazio-hesiak exekutatzen direnean, aplikazio paralelo baten prozesuak sinkroniza-

tzeko, balio bera erabili behar da beti, 0 edo 1, hesia itxita edo irekita dagoela adierazteko.

4.3. Sekzio kritiko berezi baterako lock / unlock errutinak diseinatu behar dira, sekzio kritikoan k prozesu arte onartu behar direlako. Erabil itzazu LL eta SC aginduak eta nahi duzun estrategia (idatzi behe-mailako kodea).

Aldatu gero lock errutina sekzio kritikoan egon daitezkeen k prozesuak denak batera sarrarazteko.

4.4. Ekoizle/kontsumitzaile motako aplikazio tipiko batean, kode hau exekutatu behar da

(buffer, prest: aldagai partekatuak; lag: aldagai pribatua):

Ekoizlea (bat) Kontsumitzaileak (hiru) for (i=0; i<99; i++) { SORTU(lag); JARRI(lag,buffer,prest); }

for (i=0; i<33; i++) { ATERA(lag,buffer,prest); KONTSUMITU(lag); }

Ekoizlea eta kontsumitzaileak buffer aldagaiaren bidez komunikatzen dira; hor uzten du ekoizleak lag aldagaiaren edukia, JARRI funtzioaren bidez, eta hortik hartuko du kontsumitzaileren batek, ATERA funtzioaren bidez. prest bi balioko aldagaia da: 1, kontsumitzeko zerbait badago, eta –1, ez badago.

a. Idatz itzazu JARRI eta ATERA funtzioak, behe-mailan; sinkronizaziorako aginduak LL eta SC dira.

b. Kontsumitzaileen arteko ordena hau ezarri nahi da: datuak banan-banan hartu behar dituzte, beti ordena berean. Horretarako, hiru posizioko sarraila-bektore bat erabili behar da, non prozesu bakoitzak abisatuko baitio hurrengoari noiz dagokion datu bat kontsumitzea. Idatz itzazu: (b1) sarraila-bektoreko posizioak prozesuei esleitzeko prozedura; eta (b2) ATERA funtzioa.

4.5. Aplikazio paralelo bat hiru prozesutan dago banatuta: ekoizle bat eta bi kontsumitzaile.

Ekoizleak datu bat sortu eta buffer batean uzten du (buf), eta hortik hartuko du datua kontsumitzaileren batek. Ekoizpena eta kontsumoa sinkronizatu ahal izateko, adierazle bat erabiltzen da (adi). Hona hemen hiru prozesu horien balizko kodea:

E ekoizlea

K1 kontsumitzailea K2 kontsumitzailea while (true) { while (adi==1) {}; datua = DATUA_SORTU(); LOCK(e1); adi = 1; buf = datua; UNLOCK(e1); }

while (true) { while (adi==0) {}; LOCK(k1); if (adi==1) DATUA_KONTS(buf); UNLOCK(k1); adi = 0; }

while (true) { while (adi==0) {}; LOCK(k2); if (adi==1) DATUA_KONTS(buf); UNLOCK(k2); adi = 0; }

Zuzena da aurreko kodea? Zuzena ez bada, zertan huts egingo du eta zergatik? Eraginkorragoa izan zitekeen? Idatz itzazu, eta arrazoitu, egin beharreko aldaketa guztiak.


4.6. Honako begizta hau exekutatu behar da P = 16 prozesadore dituen SMP konputagailu batean, paraleloan:

for (i=0; i<1024; i++) if (A(i)>0) A(i) = 3*A(i)*A(i) – 5*A(i) – 2

Begiztako iterazio guztiak independenteak dira, eta, beraz, edozein ordenatan eta edozein

prozesadoretan exekuta daitezke. Hainbat metodo dago iterazioak prozesadoreen artean banatzeko, estatikoak —begizta konpilatzen denean— zein dinamikoak —exekutatzen denean—. Dinamikoen artean, esaterako, honako hiru hauek ditugu:

a. Self-scheduling. Iterazioak banan-banan esleitzen dira exekuzioan zehar; horretarako, kontagailu bat erabiltzen da, non iterazioak noraino banatu diren adierazten den. Prozesadore bakoitzak kontagailuak une horretan adierazten duen iterazioa exekutatuko du; bukatutakoan, beste bat, eta beste bat... harik eta prozesadore guztien artean iterazio guztiak exekutatu arte.

Idatz ezazu prozesadore bakoitzak exekutatuko duen kodea (goi-mailako kodea eta behar dituzun sinkronizazio-funtzioak erabiliz).

b. Chunk scheduling. Aurreko estrategiaren antzekoa da, baina iterazioak ez dira banan-banan banatzen, ondoz ondoko hainbat iteraziotako multzotan baizik; adibide honetarako, N/P tamainako multzoak (N = iterazio kopurua, 1.024). Idatzi berriro kodea, eta azaldu abantailak eta desabantailak aurreko estrategiarekin alderatuta.

c. Guided self-scheduling. Estrategia hau ere antzekoa da, baina kasu honetan prozesadore bakoitzari honako iterazio kopuru hau esleitzen zaio: exekutatzeko geratzen den iterazio kopurua zati P. Idatzi prozesadore bakoitzak exekutatuko duen kodea, eta azaldu abantailak eta desabantailak aurrekoekin alderatuta.

4.7. Paraleloan exekutatu behar diren prozesuak sinkronizatzeko oinarrizko funtzioak aztertu ditugu: lock motako funtzioak eta hesiak. Kontuz egiten ez bada, erraza da funtzio horietan akatsak izatea. Hona hemen adibide pare bat.

Aurreneko kasuan, sekzio kritiko bat babesteko errutina bat, eta, bigarrenean, sinkronizazio-hesi bat idatzi dira; zoritxarrez, ez bata ez bestea ez dira zuzenak SMP motako makina baterako. Analizatu bi funtzioak eta esan zertan huts egiten duten.

A. Sekzio kritiko bat babesteko kodea (bi prozesu bakarrik; hasieran, txanda = flag = 0)

elkarrekiko esklusiorako errutina() { flag[pid] = 1; pid = prozesu-identifik., 0 edo 1 while (txanda != pid) { while (flag[(pid+1) % 2] == 1) {}; txanda = pid; } <sekzio kritikoa> flag[pid] = 0; }

B. Sinkronizazio-hesia

while (baldintza) { <kalkulua> HESIA (parametroak); } HESIA(int &k1; int p) F&A-k balio zaharra itzultzen du { if (Fetch&Add(k1,1) == p-1) k1 = 0; else while (k1 != 0) {}; }


4.8. Begizta hau exekutatu behar da, paraleloan, prozesadore asko duen multiprozesadore batean, iterazio bat prozesadore bakoitzean:

for (i=0; i<32; i++) { A[i+3] = fun1(B[i]); C[i] = fun2(A[i]); }

Idatz ezazu prozesadore bakoitzak exekutatuko duen kodea.

4.9. a. Kontsumitzaile eta ekoizle bana datu ilara zirkular baten bidez (ilara) komunikatzen dira. Ekoizleak datuak banan-banan sortu eta ilaran uzten ditu, baldin eta ilaran 6 datu edo gutxiago badago; bestela, zain geratzen da, ilaran tokia izan arte. Kontsumitzaileak ilaratik hartzen ditu datuak kontsumitzeko, binaka. Aldagai partekatu batek, zenbat, ilarako datu kopurua adierazten du. Bi erakusle, ie eta ik, erabiltzen dira libre dagoen eta okupatuta dagoen ilarako aurreneko posizioa adierazteko, hurrenez hurren.

Programa itzazu (goi-mailan) ekoizlea eta kontsumitzailea aplikazio horretarako. Erabil

itzazu nahi dituzun sinkronizazio-funtzioak, baina zehaztu argi eta garbi zertarako diren eta haien aldagaiak.

b. Berridatzi ekoizleari dagokion kodea ekoizle asko onartu ahal izateko. Gero, adierazi zertan aldatu beharko den kode hori, baldin eta ekoizle batek ezin badu beste datu bat ilaran sartu gainerakoek berea ilaran utzi arte.

c. Berridatzi kontsumitzaileari dagokion kodea kontsumitzaile asko onartu ahal izateko. Gero, aldatu berriro kontsumitzailea honako ordena-erlazio hau ezarri ahal izateko: prozesuek txandaka kontsumitu behar dituzte datuak, beti ordena berean.

4.10. Bi kontsumitzailek datuak kontsumitzen dituzte ilara batetik. Kontsumoa orekatua

mantentzeko, muga bat jarri da: datu gehien eta datu gutxien kontsumitu duten prozesuen arteko diferentzia ezin da 5 datukoa baino handiagoa izan. Aldagai hauek erabiltzea proposatzen da: ik, ilarako datuak eskuratzeko erakuslea; zenbat, ilarako datu kopurua; dif, kontsumitzaileen arteko kontsumo-diferentzia. Idatz ezazu kontsumitzaile bakoitzari dagokion kodea.

Erabil daiteke sortu duzun kodea, baldin eta kontsumitzaileak bi baino gehiago (asko) badira? Proposatu estrategiaren bat kasu horretarako.

4.11. Paraleloan exekutatu behar den aplikazio jakin batean ekoizle/kontsumitzaile egitura duen

zati bat dago, hiru prozesutan banatuta: bi ekoizle eta kontsumitzaile bat. Ekoizleek datuak sortzen dituzte, banan-banan (D_Sortu() funtzioa); datu bakoitiak DI1 ilaran uzten dituzte, eta bikoitiak DI2 ilaran. Kontsumitzaileak binaka hartzen ditu datuak kontsumitzeko, ilara bakoitzetik bat (D_Konts(...)).

E

ie ik

zenbat

DATUA_SORTU() DATUAK_KONTSUMITU(d1,d2)

ilara

K

ik

zenbat

DATUA_KONTSUMITU(dat)

ilara K0

K1

dif


Ilara bakoitzak kontagailu bat du, zenbat datu dauden jakiteko, eta bi erakusle, lehen eta azken datuak erakusteko.

Idatzi (goi-maila) ekoizle eta kontsumitzaile prozesuak. Azaldu argi eta garbi aldagai guztien izaera (partekatua edo pribatua) eta sinkronizazio-funtzioak.

Zein kasutan izango da eraginkorra egitura hori? Blokeatu egin daiteke sistema? 4.12. Programa hau exekutatu behar da SMP sistema baten 8 prozesadoreen artean:

batura = 0; for (i=0; i<1000; i++) batura = batura + A[i]; for (i=0; i<1000; i++) B[i] = B[i] / batura;

Prozesadore guztiek parte hartzen dute bi begiztetan, eta honela banatuko da lana: P0 → 0, 8, 16... iterazioak; P1 → 1, 9, 17... iterazioak, etab.

Idatz ezazu prozesadore bakoitzak exekutatuko duen kodea (goi-maila). Erabil itzazu, behar izanez gero, lock, hesiak eta abarreko sinkronizazio-funtzioak. Aldagai pribatu bana erabiltzen da prozesadoreak identifikatzeko (pid = 0..7).

4.13. Zuri-beltzeko irudi bat M × N pixeletan banatu da, eta Pix(i,j) matrizearen bidez adierazi

da; matrize horren osagaiek irudiaren pixelen gris-maila gordetzen dute, 0tik k–1eraino. Begizta hau exekutatzen da, prozesadore batean, irudiaren "grisetako histograma" lortzeko:

for(i=0; i<M; i++) for(j=0; j<N; j++) { Histo(Pix(i,j)) = Histo(Pix(i,j)) + 1; }

Eragiketa azkartzeko, P prozesadoreko multiprozesadore bat erabili nahi da. Hala, irudia

(Pix matrizea) P segmentutan banatu eta prozesadore bakoitzak segmentu bat prozesatuko du.

Idatz ezazu prozesadoreek exekutatuko duten kodea, eta kalkulatu lortuko den azelerazio-faktorea (speed-up). Erabili aldagai pribatu bana (pid = 0..P–1) prozesadoreak bereizteko.

4.14. Aplikazio jakin batean, N osagaiko bektore baten maximoa kalkulatu behar da, funtzio hau

erabiliz:

MAX = LORTU_MAX(hasiera-helbidea,luzera,pausoa)

Prozesua azkartzeko, P prozesadore erabili nahi da, bakoitzak bektorearen zati bat prozesa dezan (tamaina berdineko zatiak, N/P osagaikoak).

a. Idatzi eragiketa hori betetzeko kodea (berdina prozesadore guztietan); erabil itzazu nahi dituzun sinkronizazio-eragiketak, eta aldagai pribatu bana (pid = 0..P–1) prozesuak bereizteko.

b. LORTU_MAX funtzioaren kostua (exekuzio-denbora, esaterako) bektore-tamainaren araberakoa da (K osagaien arteko maximoa lortzeko, K), eta edozein sinkronizazio-eragiketaren kostua S da. Adierazi eragiketaren kostua P prozesuren artean egiten denean. Horretan oinarrituta, kalkula ezazu prozesu kopururik onena kostuaren ikuspuntutik, eta, N = 1.024 eta S = 10 izanik, lortuko den azelerazio-faktorea (maximoa).

N

M

Pix(i,j)

K

E1 DI1(i)

E2 DI2(i)


4.15. Hainbat aplikazio paralelotan (esaterako, hesi batean), prozesuek aldagai partekatu bat erabiltzen dute, k, non k := k + 1 eragiketa betetzen duten. Prozesu kopurua handia bada eta denek aldi bertsuan exekutatzen badute eragiketa hori, litekeena da eragiketaren latentzia handia izatea, aldagai partekatu hori atzitzean sortuko diren gatazkak direla medio.

Eragiketaren latentzia txikiagotu daiteke aldagai bakar bat erabili beharrean aldagai gehiago (P) erabiltzen badira, eta haiekin arbola-egitura bat osatzen bada.

Idatz ezazu nola eguneratu kontagailu bat P = 16 prozesuen artean estrategia horri jarraituz.

4.16. Honako begizta hau exekutatu behar da paraleloan, lau prozesadore erabiliz. Hori dela eta,

paraleloan exekutatuko diren lau ataza definitu dira, hauek:

for (i=0; i<1000; i++) for (j=0; j<1000; j++) { IRAKURRI(file1,&B1); IRAKURRI(file2,&B2); IRAKURRI(file3,&B3);

B4 = B1 + B2 + B3;

IDATZI(file4,B4); }

/* atX (X = 1,2,3) */

for (j=0; j<1000; j++) IRAKURRI(fileX,&BX[j]); /* at4 */

for (j=0; j<1000; j++) { B4[j] = B1[j] + B2[j] + B3[j]; IDATZI(file4,B4[j]); }

Oharra: IRAKURRI/IDATZI funtzioen bidez, fitxategi jakin batean dagoen matrize baten (i, j) osagaia irakurtzen/idazten da.

Idatz itzazu prozesadore bakoitzak exekutatu behar duen kodea jatorrizko begizta paraleloan

exekutatu ahal izateko; atazak sinkronizatzeko, hesiak bakarrik erabili behar dira. Gero, balioetsi exekuzio-denbora paraleloa eta lortuko den azelerazio-faktorea, parametro hauen arabera: IRAKURRI, 8 ziklo; B4ren kalkulua, 2 ziklo; IDATZI, 8 ziklo; hesia, 10 ziklo.

Azkenik, proposatu modu eraginkorrago bat jatorrizko begizta lau prozesadoreen artean exekutatzeko.

4.17. Aplikazio jakin batek A[N] bektorea prozesatzen du, eta ondorioz 0 bihurtu diren osagaien

kopurua itzultzen du (zk). Zero kopuruak ezarritako muga jakin bat (zk_min) gainditzen ez badu, bektorea berriro prozesatzen da, harik eta kopuru minimo hori gainditu arte.

zk = 0; while (zk < zk_min) { zk = PROZESATU_BEKT(A,N); }

Eragiketa paraleloan exekuta daiteke, P prozesadore erabiliz (pid = 0..P–1). Prozesu

bakoitzak bektorearen zati bat prozesatuko du eta zati horren zero kopurua kalkulatuko du; gero, emaitza partzial guztiak batu beharko dira, bektore osoaren zero kopurua lortzeko (ez dago dependentziarik bektore-osagaien prozesamenduan).

Idatz ezazu prozesu paraleloei dagokien kodea. Erabil itzazu nahi dituzun sinkronizazio-funtzioak (ez egin, baina azaldu erabiltzen dituzten parametroak).

PROZESATU_BEKT funtzioaren exekuzio-denbora bektorearen osagai kopuruarekiko proportzionala da; sinplifikatzeko, N. Bestalde, sinkronizazio-eragiketen kostua P gisa modela daiteke. Kalkula ezazu lortuko den azelerazio-faktorea, eta, horren arabera, prozesu kopuru optimoa, azelerazio-faktore handiena eskaintzen duena.


4.18. Ataza jakin baten exekuzioa hainbat prozesadoreren artean banatu ahal izateko, honako kode zati hau idatzi da SMP sistema baten prozesu bakoitzerako. Zuzena da? Erroreak badaude, zuzendu itzazu.

for (i=pid; i<pid/N; i++) { A[i] = fun(i); if (A[i]>0) batura = batura + A[i]; } B[pid] = batura * pid;

4.19. Aplikazio paralelo batean 20 aldagaiko funtzio logiko bat erabiltzen da, eta aldagaietako

zenbat konbinaziotarako ematen duen funtzioak 1ekoa (true) jakin behar da. Horretarako, honako begizta hau exekutatzen da:

for (i=0; i<220; i++) sol_kop += EGIAZTATU_FUN(i); EGIAZTATU_FUN(i) funtzioak 1ekoa itzultzen du, baldin eta i-ri dagokion kode bitarra

funtzio logikoaren soluzioa bada; bestela, 0koa itzultzen du. Begizta hori 16 prozesadoreren artean exekutatu behar da. Idatz ezazu prozesadore bakoitzak

exekutatuko duen kodea. Adierazi, zehatz-mehatz, erabiltzen dituzun aldagai guztien izaera, partekatuak edo pribatuak. Balioetsi lortuko den azelerazio-faktorea.

4.20. Honako eragiketa hau egin behar da paraleloan, P prozesadoreko SMP multiprozesadore

batean, N osagaiko C bektorearen osagaiekin: bektore-osagaien maximoa (MAX) kalkulatu, eta osagai guztiei gehitu.

Idatz ezazu kodea (SPMD eredua; pid, prozesuen identifikadorea). Erabil itzazu behar dituzun sinkronizazio-funtzioak, eta adierazi aldagai guztien izaera, partekatuak edo pribatuak.

4.21. Honako programa zati hau paraleloan exekutatu behar da, 10 prozesadoreko SMP batean:

printf("\n X-ren balioa: "); scanf("%d",&X);

for(i=0; i<1000; i++) for(j=0; j<1000; j++) if (A[i][j] < X) Pix = Pix + 1;

printf("\n Emaitza: Pix = %d ", Pix); Idatz ezazu prozesadoreek exekutatuko duten kodea. Iterazioen banaketa (scheduling)

estatikoa da, ondoz ondoko zatiak erabiliz, prozesuen pid identifikadoreen arabera. Erabil itzazu behar dituzun sinkronizazio-funtzioak (ez idatzi haien kodea). Adierazi aldagai guztien izaera, pribatuak edo partekatuak.

Ariketak: Memoriaren kontsistentzia konputagailu paraleloetan ▪ 33 ▪

5.1. Erantzun galdera hauei, ahalik eta zehatzen:

1. SMP motako sistema paralelo baten bi prozesadorek honako memoria-eragiketa hauek exekutatzen dituzte:

P1: LD A ... ST B ... LD B P2: ST C ... ST D ... LD E

Aginduak tartekatu egiten dira denboran zehar; tartekatze hauetatik, adierazi zein datozen bat kontsistentzia sekuentziala (SC) ereduarekin eta zein Total Store Ordering (TSO) ereduarekin.

a. LD A ST B ST D LD B ST C LD E b. LD A ST C ST D ST B LD B LD E c. ST C LD A LD E ST B ST D LD B d. LD A ST C LD B ST D LD E ST B e. ST C ST D LD A LD E ST B LD B

2. SMP motako multiprozesadore baten P1 eta P2 prozesadoreek datu-bloke bat partekatzen

dute, non A = 0 aldagaia dagoen. P1ek A = 3 idazten du; gero, aldaketa horretaz ohartu gabe, P2k A = 0 irakurtzen du. Gerta liteke hori, edo errore bat dago? Zergatik?

3. Multikonputagailu baten kontsistentzia-ereduak zera adierazten du:

a. Emaitzak prozesadore bakarrean sortzen diren ordena berean sortzen direla. b. Elkarren artean dependentzia duten aginduak desordenatu ezin direla. c. Memoria-eragiketak desordenatu egin daitezkeela atomikoak badira, baina, bestela, ez. d. Memoria-eragiketen exekuzio-ordenarako eta atomikotasunerako zenbait murriztapen.

4. Multiprozesadoreetako memoriaren kontsistentzia mantentzeko, fence motako aginduak

(membar, sync...) erabiltzen dira. Zertarako? a. Datu partekatuetarako atzipenak babesteko. b. Zenbait agindu berrordenatzea galarazteko (hardwareari edo konpiladoreari). c. Datuen koherentzia memoria banatuko sistemetan ere mantentzen dela ziurtatzeko,

memoria partekatuko sistemetan lortzen den modu bertsuan. d. Dependentzia guztiak dependentzia "gogorrak" (RAW) bezala tratatu ahal izateko.

5.2. Bi programa zati hauek multiprozesadore batean exekutatu behar dira, paraleloan (hasiera-

balioak, A = B = adi = 0):

P1 P2 (1) A = 3; (1) B = adi; (2) adi = 1; (2) C = A;

Frogatu ezazu ez dela posible P2 prozesadorean B = 1 eta C = 0 lortzea, baldin eta multiprozesadoreko kontsistentzia-eredua SC (sekuentziala) bada.

5.3. Bi programa zati hauek paraleloan exekutatu behar dira (aldagaien hasiera-balioa 0 da).

Print eragiketa atomikoa da, eta datu guztiak batera inprimatzen ditu (adi: print agindua memoria-irakurketa bat da).

P1 P2 (a) X = 1; (d) Z = 1; (b) Y = 1; (e) T = 1; (c) print X,T; (f) print Z,Y;

Aginduen ordena eta memoria-eragiketen atomikotasuna betetzen dira sistema osoan. Zerrendatu sei aginduen exekuzioaren ordena zilegi guztiak (a b c d e f, ...) eta lor daitezkeen irteerak (X T Z Y = 1 1 1 1, ...).

Eta atomikotasuna mantentzen ez bada, zertan aldatuko dira irteera-balioak?


5.4. Hiru programa zati hauek exekutatu behar dira, paraleloan, kontsistentzia-eredu sekuentziala (SC) erabiltzen duen makina paralelo batean (hasiera-balioak, 0):

P1 P2 P3

(1) A = 1; (1) B = 1; (1) C = 1; (2) print B,C; (2) print A,C; (2) print A,B;

Lor al daitezke emaitza hauek print aginduetan (B C – A C – A B)?

a. 0 0 – 1 0 – 1 1; b. 1 1 – 1 1 – 1 1; c. 0 0 – 0 0 – 0 0

SC ereduaren zein baldintza ez da betetzen irteera 0 1 – 1 0 – 0 1 bada? 5.5. Multiprozesadore batek TSO (Total Store Ordering) edo PSO (Partial Store Ordering)

kontsistentzia-ereduak erabiltzen ditu. Hiru kasu hauetatik, zein kasutan ziurtatuko litzateke kontsistentzia sekuentzialaren "semantika" programa zati horiek exekutatzean? Zergatik?

a. kasua: P1 P2 (1) A = 1; (1) while (B==0) {}; (2) B = 1; (2) print A; b. kasua: P1 P2 P3 (1) A = 1; (1) while (A==0) {}; (1) while (B==0) {}; (2) B = 1; (2) print A; c. kasua: P1 P2 (1) A = 1; (1) B = 1; (2) print B; (2) print A;

5.6. Ekoizle/kontsumitzaile motako aplikazio bat exekutatu behar da bi prozesadoretan, paraleloan

(adi adierazleak datu-ematea (dat) sinkronizatzen du):

Pi (ekoizlea) ... lag = DAT_SORTU(); while (adi == 1) {}; dat = lag; adi = 1; ...

Pj (kontsumitzailea) ... while (adi == 0) {}; lag = dat; adi = 0; DAT_KONTS(lag); ...

Programatzaileak makinaren kontsistentzia-eredua aukera dezake: sekuentziala (SC); Partial

Store Ordering (PSO); edo Weak Ordering (WO). Beharrezkoa bada, MFence motako aginduak erabil daitezke, memoria-atzipenen ordena hertsia ezartzeko.

Kontsistentzia-eredu bakoitzerako, eta adi eta dat aldagai partekatuen erabilera dela eta, esan ordena ezartzeko aginduak erabili behar diren, non, eta zergatik.

Ariketak: Komunikazio-sarea. Mezu-ematea. ▪ 35 ▪

6.1. Diseina ezazu urrats anitzeko sareak eratzeko erabiltzen den 2×2-ko kommutagailu sinple bat (bufferrik gabe).

6.2. 2×2 tamainako kommutagailu batez lau konexio-eskema desberdin lor daitezke. Kalkula

ezazu zenbat lor daitezkeen 3×3 eta 4×4 tamainako kommutagailuekin. Aurreneko kasurako (3×3), marraztu "sarrera→irteera" konexio horiek guztiak.

6.3. a. Hartu kontuan bi portuko kommutagailuak. Marraztu 8 nodoko Omega sarea, eta adierazi

bertan 2 prozesadoretik 7 prozesadorera joateko bidea. b. Zer konexio osatzen dira prozesadoreen artean, baldin eta kommutagailu guztietan lotura

hauetako bat gauzatzen bada? (1) iragan gurutzatu gabe; (2) iragan gurutzatuz. c. Sare horretan, honako komunikazio hauek egin behar dira une jakin batean, denak batera:

0 → 2; 1 → 3; 2 → 1; 3 → 4; 4 → 5; 5 → 7; 6 → 6; 7 → 0. Marraz itzazu egin behar diren sareko konexioak. Egin daitezke denak aldi berean?

d. Omega sarea osatzeko erabili behar diren osagaien kostua honela modela daiteke: kommutagailu bakoitza, A × k2, non k kommutagailuen portu kopurua (gradua) baita, eta lotura bakoitza, B. Bi osagai horiek direla eta, kalkula ezazu sarearen kostua prozesadoreko, kasu hauetan: P = 256 prozesadore; k = 2, 4, 16, eta 256.

6.4. Urrats anitzeko sare (dinamiko) batek "permutazioak" deituriko komunikazio-eskemak

onartzen ditu, non, aldi berean, prozesadore bakoitza memoria-modulu desberdin batekin (edo beste prozesadore batekin) konektatzen den; esaterako, P0 M2rekin, P1 M6rekin... Hala ere, Omega sareak ez du edozein permutazio onartzen. Egiazta itzazu hiru permutazio hauek egin daitezkeen ala ez, gatazkarik gabe, 8 nodoko Omega sare batean:

a. Biraketa: 0 → 1 → 2 → ... 6 → 7 → 0 b. Tartekatzea: (an–1, an–2, ..., a1, a0) → (an–2, ..., a1, a0, a n–1) (helbideak) c. Inbertsioa: (an–1, an–2, ..., a1, a0) → (a0, a1, ..., an–2, a n–1)

6.5. Kommutagailuen bidez, hainbat topologiatako

sareak sor daitezke; esaterako, irudiko sarea, butterfly izenekoa.

Nola aukeratzen da bidea sare horretan? Jarri adibide bat. Zeren "antza" dauka topologia horrek?

6.6. a. Marraz ezazu Omega sare bat 8 prozesadoretarako (2 graduko kommutagailuak). Une jakin batean, eta aldi berean, bi mezu sortzen dira: 4 prozesadoretik 6ra, eta 6tik 7ra. Marraztu, sarearen gainean, mezuek hartuko dituzten bideak. Arazorik balego, adierazi zein eta nola konpon daitekeen.

b. Demagun 1. mezuak (4 → 6) erabili behar duen kommutagailu bat, 2. urratsekoa, matxuratu dela. Ba al dago aukeraren bat komunikazioa gauzatu ahal izateko? Jarri adibide bat.

c. Zenbat kommutagailu eta zenbat lotura gehitu behar zaizkio aurreko sareari 16 prozesadoreko sare bat osatzeko?

d. Demagun komunikazio-sarea 3×3-ko toru bat dela. Adierazi aurreko mezuek (4 → 6 eta 6 → 7) sare horretan hartuko dituzten bideak (DOR erabiliz). Arazoren bat?

e. Mezu batek 0 prozesadoretik 8 prozesadorera joan behar du. Zein izango da mezu horren bideratze-erregistroa? Marraztu, sare baten gainean, mezuak hartuko duen bidea, bideratzea estatikoa eta "lehenik-X-gero-Y" motakoa izanik.

f. Matxuratu egin da mezuak erabili behar duen lehen lotura. Bete egin daiteke komunikazioa? Zein baldintzapetan?

0

2

4

6

1

3

5

7

0

2

4

6

1

3

5

7


6.7. Sare-topologiak analizatzeko eta konparatzeko, hainbat parametro topologiko erabil daitezke. Adibidez, zazpi topologia hauek konparatu nahi ditugu —hiperkuboa, 2D maila eta torua, 3D maila eta torua, eta 2 eta 4 graduko arbola sendoak— honako parametro hauek erabiliz —diametroa, batez besteko distantzia, lotura kopurua eta sare-erdibiketa—. Sare bakoitzerako, eman parametro horien adierazpen aljebraikoa, eta marraztu lau grafikotan haien portaera nodo kopuruaren arabera.

6.8. Kalkula ezazu nodo jakin batetik batez besteko distantziaren erdira baino hurbilago dauden

nodoen ehunekoa, 256 nodoko 2D toruan eta hiperkuboan. Eta batez bestekoa baino distantzia txikiago edo berdinera?

6.9. 64 nodoko komunikazio-sare batean, mezu bat bidali behar da 9 nodotik 52ra. Kalkula ezazu

mezuaren bideratze-erregistroa (routing record) eta zein tarteko nodotatik igaroko den, DOR erabiliz, sarea (a) hiperkuboa, (b) bi dimentsioko maila, eta (c) hiru dimentsioko torua izanik.

6.10. Aplikazio jakin bat exekutatu behar da 256 nodoko MPP batean, non komunikazio-sarea 2D

toru bat den. Makina horretan, honela banatzen dira aplikazioak sortzen dituen mezuak, distantziaren arabera:

distantzia: 1 2 3 4 >4 probabilitatea: 0,4 0,3 0,2 0,1 0

Kalkula ezazu aplikazio horrek sortzen dituen mezuen batez besteko distantzia. Distantzia jakin batera bidaltzen diren mezuak zoriz banatzen dira distantzia horretara dauden

nodoen artean. Prozesadore batetik igorrita, zenbat mezu gehiago hartzen dira 1 distantziara dagoen i nodoan 4 distantziara dagoen j nodoan baino?

6.11. Kalkula ezazu 64 nodoko sare baten erdibiketaren banda-zabalera, topología (a) hiperkuboa,

(b) 2D maila, eta (c) 2D torua izanik; loturak 16 bitekoak dira eta transmisio-zikloa 4 ns-koa da. Horretan oinarriturik, kalkula ezazu nodo bakoitzak sarean segundoko injekta dezakeen pakete kopuru maximoa (batez bestean); paketeak 128 bytekoak dira, eta komunikazioa zoriz egiten da.

6.12. Multiprozesadore baten 16 prozesadoreen arteko komunikazioa ahalbidetzeko, irudiko

komunikazio-sarea erabiltzen da: eraztun bat, non prozesadore bakoitza 3 prozesadorerekin konektatzen baita: alboetako biekin eta diametroaren beste muturrekoarekin.

Kalkula itzazu 16 nodoko sare horren diametroa eta batez besteko distantzia. Gero, eman bi parametro horiek prozesadore kopuruaren arabera (P, 2ren berretura).

6.13. 64 prozesadoreko konputagailu baten komunikazio-sarea hiperkubo bat da. Zein da bi prozesadoreren arteko distantzia maximoa? Zein da distantzia maximo horretara dagoen prozesadorea(k) 39 prozesadoretik abiatuta?

10 prozesadoretik 45 prozesadorera doan mezu baterako, adierazi bidearen distantzia eta igaroko dituen tarteko nodoak. Bideratzea DOR motakoa da (dimentsio handienetik hasita).


6.14. 64 prozesadoreko multikonputagailu batek hiperkubo bat erabiltzen du komunikazio-sare gisa. Loturak 2 Gb/s-koak dira. Kalkula itzazu:

a. Sareko nodo bakoitzeko lotura kopurua, eta sareko lotura kopuru osoa; eta sarearen diametroa eta batez besteko distantzia.

b. Sarearen erdibiketaren banda-zabalera (GB/s), eta, horren arabera, prozesadore bakoitzak segundoko injekta dezakeen 256 byteko pakete kopurua, trafikoa zorizkoa denean.

c. Komunikazio-sareen topologiaren "konplexutasuna" adierazten duten hainbat parametro dago; esaterako, hau: K = Erdibiketa / Lotura_kopurua. Konpara itzazu hiperkuboa eta ezaugarri bereko 2 dimentsioko torua parametro horren arabera.

d. Pakete bat 43 nodotik 28 nodora doa hiperkuboan. Eman pakete horren bideratze-erregistroa, zeharkatu beharreko distantzia, eta nondik igaroko den, bideratzea DOR izanik.

6.15. 24 prozesadoreko MPP baten komunikazio-sarearen topologia irudikoa da:

a. Kalkula itzazu sare horren diametroa, batez besteko distantzia, eta erdibiketaren lotura kopurua.

b. Azaldu nola kalkulatu behar den i prozesadoretik j prozesadorera doan pakete baten bideratze-erregistroa. Kasu partikular gisa, kalkula ezazu 7tik 23ra doan pakete batena, eta adierazi bideratze-erregistroa nola aldatuko den, mezua aurreratu ahala; bideratzea estatikoa da (DOR), "lehenik-X-gero-Y" motakoa.

c. Bideratzea estatikoa izanik, eta mezuak wormhole/cut-through moduan badoaz aurrera, gerta liteke komunikazio-deadlock bat sarean? Arrazoitu erantzuna.

6.16. Lehenbiziko konputagailu paraleloetan, ILLIAC IV izan

zen famatuenetako bat. Konputagailu horrek komunikazio-sare berezi bat erabiltzen zuen, irudikoa. Kalkula itzazu 16 nodoko sare horren batez besteko distantzia eta diametroa.

Frogatu daiteke sare hori isomorfoa dela eraztun arkudun batekin. ILLIAC IV sarearen konexio-eskema kontuan hartuz, marraztu berriz sarea, baina eraztun arkudun bat gisa.

Nola egin daiteke mezuen bideratzea sare horretan? Eman adibide bat

6.17. Irudiko sarean, nodo bakoitza (ertzetakoak izan ezik) 8

auzokoekin konektatuta dago. Kalkula itzazu sare horren diametroa eta batez besteko distantzia (4×4 kasurako).

Proposa ezazu bideratze-algoritmo bat sare horretarako. Eman ezazu adibide bat.

7

23

0 2 3 1

4 6 7

5

8 10

11

9

12 14

15

13


6.18. 4.096 prozesadoreko sistema paralelo baten komunikazio-sareko loturak byte (flit) batekoak eta 800 MB/s-koak dira. Prozesadoreen artean bidaltzen diren paketeak 64 bytekoak dira: 60 byte datuetarako eta 4 byte goiburukorako. Goiburukoaren aurreneko flit-a prozesatzeko, 2 ns behar dira.

a. Kalkula itzazu pakete baten latentzia maximoa eta batez bestekoa, trafikoa ez dagoenean, sare-topologia eta komunikazio mota hauetarako:

- hiperkuboa, 2D maila eta torua, 3D maila eta torua, 2 eta 4 graduko fat-tree. - store-and-forward, cut-through.

b. 800 byteko mezu bat bidali behar da, 3D toruan eta cut-through moduan, batez besteko distantziara dagoen nodo batera. Mezua paketetan banatzen da, eta paketeak bata bestearen atzetik bidaltzen dira, tartean 100 ns-ko denbora-tartea utzita. Kalkula ezazu mezuaren transmisio-latentzia.

c. Zein izango da mezu horren latentzia pakete-kommutazioa erabili beharrean zirkuitu-kommutazioa erabiltzen bada? Zunda-mezua flit batekoa da.

6.19. 512 prozesadoreko multikonputagailu baten komunikazio-sarea hiperkubo bat da, eta sareko

loturak 4 Gb/s-koak dira. Trafikoa ez dagoelarik, tamaina berdineko hainbat pakete bidali dira prozesadore batetik besteetara, eta honako denbora hauek neurtu dira:

Distantzia Transmisio-denbora sarean (ns)

2 136 4 146 8 166

Datu horien arabera, kalkula itzazu:

a. Paketeak transmititzeko erabili den teknika. Arrazoitu erantzuna. b. Goiburuko flit-a mezu-bideragailuetan prozesatzeko denbora (tr, bideratze-denbora); eta

bidali diren paketeen tamaina flit-etan (flit = byte). c. Hirugarren kasurako (d = 8), transmisio-denbora paketeak transmititzeko "beste teknika"

erabili izan bagenu. 6.20. Multikonputagailu baten komunikazio-sarea 8×8-ko toru bat da. Komunikazio-kanalak byte

batekoak dira (flit-aren tamaina, alegia). Paketeak 64 bytekoak dira. Paketeen bideratzea cut-through/wormhole motakoa da, eta bideragailu (router) bakoitzean behar den bideratze-denbora (tr) 2 ns da.

Analizatu egin da paketeen batez besteko latentzia sare horretan, trafikoaren arabera, eta grafiko hau lortu da. Trafikoa zorizkoa izan da (denboran eta helburuetan), eta sarearen erdibiketak zedarritzen duen maximoaren %-tan ematen da.

Grafikoko datuetan oinarriturik:

a. Kalkula ezazu komunikazio-loturen banda-zabalera, gigabit/s-tan. b. Zein izango litzateke paketeen batez besteko latentzia trafikorik ez dagoenean,

komunikazioa store-and-forward moduan egingo balitz?


c. Sarearen erdibiketatik ondoriozta daitekeen trafiko maximoa ez da askotan erabilgarria, paketeen latentziak handiegiak direlako. Grafikoko datuak kontuan hartuz, kalkula ezazu prozesadore bakoitzak sarean injekta dezakeen byte kopuru maximoa murriztapen hau ezarrita: paketeen latentzia, batez bestean, ezin da trafikorik ez dagoeneko latentzia baino % 15 handiagoa izan.

6.21. 64 prozesadoreko (8×8) maila baten loturak 2 Gb/s-koak dira. Sare horren mezu-

bideragailuen erantzun-denbora (paketeak prozesatzeko) 4 ns da. Flit-ak (bideratzea egin ahal izateko informazio kantitaterik txikiena) 2 bytekoak dira. Programa jakin bat exekutatzen ari dela, 256 byteko pakete bat bidali behar da, 14 nodotik 50era. Trafikoa dela eta, badakigu paketeak zain geratuko direla bidean zehar, bufferretan, eta itxarote-denbora osoa honela modela daiteke: 50×d ns (d, distantzia).

a. Kalkula itzazu paketearen bideratze-erregistroa eta aurreko eragiketaren latentzia, bi kasu hauetan: (1) store-and-forward eta (2) cut-through.

b. Aztertu egin da aurreko programaren exekuzioa, eta portaera hau ikusi da: batez bestean, 2 ms-ko kalkuluak egin ondoren, prozesadore bakoitzak pakete bat bidaltzen du, eta erantzunaren zain geratzen da. Komunikazioko latentziak aurreko atalean kalkulatutakoak dira. Paketeak heldu ahala erantzuten dira, denbora galdu gabe. Kalkula ezazu komunikazioak sortzen duen denbora-galera edo gainkarga (overhead) komunikazio mota bietan, SF eta CT. Zein ondorio ateratzen duzu emaitzetatik?

6.22. Komunikazio-sare bat hierarkikoa da sare-hierarkia bat osatzen bada, agian topologia

desberdinak erabiliz hierarkia-maila bakoitzean. Esaterako, honako hau: 6 urratseko hainbat Omega sare (2×2-ko kommutagailuak) 4 dimentsioko hiperkubo bat osatuz. Hau da, prozesadoreak multzotan banatu dira: multzo bakoitzaren barnean, Omega sare bat erabiltzen da, eta, multzoen artean, hiperkubo bat.

Omega sareetako P0 nodoa multzoen arteko konexioak egiteko erabiltzen da (multzo bakoitzeko P0 nodoak ez dira benetako prozesadoreak, baizik eta hiperkuboa osatzeko erabiltzen diren gune bereziak). Sare hori dela eta:

a. Zenbat prozesadore konekta daitezke multzo baten barnean, hots, Omega sare bakoitzean? Eta sare osoan? Zenbat dimentsio izango luke nodo kopuru bereko hiperkubo batek? Zein izango litzateke balizko hiperkubo horren erdibiketaren banda-zabalera, loturak 50 MB/s-koak izanik?

b. Zein da sarearen diametroa? Zenbat prozesadore daude, batetik abiatuta, distantzia horretara? Eta zein da sarearen batez besteko distantzia?

c. Sare horretan exekutatzen den aplikazio jakin baten komunikazio-patroiak honako komunikazio-probabilitate hauek ditu, distantziaren arabera:

Omega sarean: 0,6 hiperkuboan, 1 distantziara: 0,25 hiperkuboan, 2 distantziara: 0,10 hiperkuboan, 3 distantziara: 0,05 harantzago: 0

Kalkula ezazu komunikazio-patroi horren batez besteko distantzia. d. Sareko loturak 4 bytekoak dira (flit bat), eta transmititzen diren paketeak 256 bytekoak

dira (goiburukoa barne). Kalkula ezazu, ziklotan, (c) ataleko batez besteko distantziara doan pakete baten latentzia, bi kasu hauetan: (1) store-and-forward, eta (2) cut-through (flit bat transmititzeko, ziklo bat; goiburukoa analizatzeko, ziklo bat).

e. Proposa ezazu bideratze-algoritmo bat mezuak iturburutik helburura bide motzenetik eramateko. Jar ezazu adibide bat.


6.23. 64 prozesadoreko multikonputagailu baten komunikazio-sarea 2 dimentsioko toru bat da. Une batean, P(0, 1) prozesadoreak A eta B bektoreen biderketa eskalarra egin behar du: ∑ai×bi. Bi bektoreak 4 osagaikoak dira, eta honela daude banatuta osagaiak sisteman zehar:

a0, b0 → P(1, 6) a1, b1 → P(3, 6) a2, b2 → P(6, 1) a3, b3 → P(1, 2)

Eragiketa honela egiten da. Emaitza behar duen prozesadoreak, P(0, 1)-ek, mezu bat bidaltzen dio a0 eta b0 osagaiak dituen prozesadoreari; ondorioz, prozesadore horrek a0×b0 eragiketa egingo du, eta emaitza a1 eta b1 dituen prozesadoreari bidaliko dio; horrek a1×b1 gehituko dio emaitza partzialari, eta hurrengoari bidaliko dio; eta abar. Azken prozesadoreak azkeneko batuketa egin, eta emaitza bidaliko dio eragiketa eskatu zuen P(0, 1) prozesadoreari. Erantzun galdera hauei:

a. Zein dira aipatu sarearen gradua, lotura kopurua eta diametroa? Eman distantzia maximora dauden bi prozesadore. Zenbat prozesadore daude, batetik abiatuta, distantzia maximora? Eta sarea 7×7 tamainakoa balitz?

b. Bidaltzen diren paketeak 8 bytekoak dira kontrolekoak direnean, eta 32 bytekoak datuak badaramatzate. Komunikazio-kanalak byte batekoak dira, flit-aren tamaina, alegia. Mezuen goiburukoa flit batekoa da. Bideratze-denbora bideragailuetan 10 ns da, eta loturak 200 MB/s-koak dira. Bideratze estatikoa erabiltzen da, DOR motakoa.

Bestalde, mikrosegundo bat behar da prozesadore bakoitzean behar diren eragiketetarako (paketeak hartu, prozesatu, biderketa egin, pakete berria sortu).

Eragiketa betetzeko erabilitako paketeek "eraztun" bat korrituko dute, P(0, 1) prozesado-retik abiatuta P(0, 1) prozesadorean bukatzeko. Kalkula itzazu sortuko diren paketeen bideratze-erregistroak, eta marraztu, sarean, paketeek hartuko dituzten bideak.

Aurrekoan oinarrituta, kalkula ezazu eragiketa horren denbora osoa, bi kasu hauetan: (1) komunikazioa store-and-forward motakoa da; (2) komunikazioa wormhole motakoa da.

c. P(1, 6) eta P(2, 6) prozesadoreak lotzen dituen lotura matxuratu egin da. Egin daiteke oraindik aurreko eragiketa? Nola? Zein da "kostua"?

6.24. 512 prozesadoreko konputagailu paralelo jakin baten komunikazio-sarea hiru dimentsioko toru

bat da (8×8×8), eta loturak 10 Gb/s-koak dira. Kalkula itzazu sare horren parametro hauek:

▪ Diametroa eta batez besteko distantzia. ▪ Erdibiketaren banda-zabalera (GB/s) eta, ondorioz, prozesadore bakoitzak segundoko

bidal dezakeen 128 byteko pakete kopuru maximoa, modu egonkorrean eta trafikoa zorizkoa izanik.

▪ 0 nodotik 404 nodora doan pakete baterako, bideratze-erregistroa, ibiliko den distantzia, erabiliko dituen tarteko nodoak, eta nola eguneratuko den bideratze-erregistroa pauso bakoitzean, bideratzea DOR izanik.

Sareko 0 eta 404 nodoetako prozesadoreetan, begizta hauek exekutatzen dira:

0 nodoa 404 nodoa

do i = 1, 50 do i = 1, 50 <kalkulatu> <itxaron datuak 0tik> <bidali datuak 404ra> <kalkulatu> <itxaron datuak 404tik> <bidali datuak 0ra> enddo enddo

P0ren eta P404ren artean bidaltzen diren paketeak 128 bytekoak dira, eta sareko loturak byte (= flit) batekoak dira. Mezu-bideragailuen bideratze-denbora 3 ns da.

Prozesadore bakoitzean egiten diren kalkuluek, gehi paketeak sortzeko eta hartzeko exekutatzen diren funtzioek, 1 μs irauten dute, batez bestean. Badakigu, halaber, paketeak gelditu egiten direla sarean, trafikoa dela eta, 50 ns bidaia bakoitzean batez beste.

Datu horiek erabiliz, kalkula ezazu begizten exekuzio-denbora bi kasu hauetan: komunikazioa (a) store-and-forward moduan egiten da; eta (b) cut-through moduan egiten da. Zenbatetan (%) laburtzen da denbora (a) kasutik (b) kasura?


6.25. Goi-mailako enpresa batek 1.024 prozesadoreko konputagailu paralelo bat erosi behar du, eta, hori baino lehen, makinei buruzko txosten bat eskatu dio informatikako departamenduari. Bi makina ari dira aztertzen, egitura eta kostu desberdinekoak:

makina topologia komunikazioa tr (routing time) loturak (B) kostua

HAL-2020 hiperkuboa store-and-forward 4 ns 4 Gb/s 2 Matrix++ maila 2D cut-through 6 ns 4 Gb/s 1,5

Konputagailuan exekutatuko diren aplikazioak hiru motakoak dira, komunikazioa dela eta:

▪ A1: nodo bakoitza alboko auzoekin bakarrik komunikatzen da (d = 1). ▪ A2: komunikazioa zorizkoa da, denboran zein espazioan (d = batez bestea). ▪ A3: trafikoa dentsoa da, komunikazioa oso maiz eta distantzia luzeetara egiten baita

(d = diametroa).

a. Makina bakoitzerako, kalkula itzazu distantziako parametroak eta erdibiketaren banda-zabalera.

b. Sarea hutsik dagoela, kalkula ezazu 16 byteko pakete baten latentzia edo komunikazio-denbora, makina eta aplikazio bakoitzerako (flit bat = byte bat).

c. Arrazoitu, argudio teknikoak erabiliz, zein makina gomendatuko zenukeen erosteko, eta zergatik, aplikazio mota bakoitzerako. Horretan oinarrituta, eta kontuan harturik hiru aplikazioak garrantzia eta konputazio-kostu berdintsukoak direla, adierazi azkenean aukeratuko duzun makina.

6.26. Origin 2000 Silicon Graphics-eko multiprozesadore arrakastatsuenetako bat izan da. Makina

horren prozesadore kopurua handia denean, komunikazio-sarea arbola bat da, non arbolaren hostoak hiperkuboak osatzen dituzten 16 prozesadoreko multzoak baitira.

Irudian, sare horren adibide bat ageri da (bakarrik hiperkuboetako bi nodori dagozkien arbolak ageri dira; sare osoa lortzeko, arbolak prozesadore guztietarako errepikatu egin behar dira).

a. Izan bedi 64 prozesadoreko makina bat. Kalkula itzazu sarearen diametroa eta batez besteko distantzia. Zenbat prozesadore dago distantzia maximora, batetik abiatuta? Zein dira?

b. Kontuan har ezazu irudian ageri diren prozesadoreen helbideak; esaterako, 000000-tik 001111-era prozesadoreak H0 hiperkubokoak dira. Defini ezazu bideratze-funtzio orokor bat paketeak helburura eramateko. Bideratze horren arabera, zein nodotatik igaroko da 001001 prozesadoretik 101111 prozesadorera joan behar duen pakete bat?

c. Bidali egin da mezu bat 000000-tik 011011-era. Kalkula ezazu mezu horren latentzia ezaugarri hauen arabera: bideratze-denbora bideragailuetan, 3 ns; loturen banda-zabalera, 250 MB/s; 128 byteko mezuak (flit = byte); transmisio modua: (a) SF eta (b) WH.

d. Arbolako goi-mailako (L2) bideragailuen banda-zabalera (lotura guztiak batuta) 2,5 GB/s da. Komunikazioa zoriz egiten da. Kalkulatu prozesadore bakoitzak segundoko injekta dezakeen 128 byteko mezu kopuru maximoa.

0–15 proz. 48–63 proz.

ARBOLAK→

L11 L12

L2

32–47 proz. 16–31 proz.

H0 H1 H2 H3


6.27. 64 prozesadoreko konputagailu paralelo batek erabiltzen duen komunikazio-sarea maila karratu bat da. Sare horren lau izkinetako prozesadoreak sarrera/irteera eragiketetarako baino ez dira erabiltzen. Hala, adibidez, prozesadore batek mezu bat inprimatu nahi badu, izkinetako prozesadore batera bidaliko du mezua, eta, han, inprimagailura bidaliko da.

a. Kalkula itzazu paketeek zeharkatu beharko duten distantzia maximoa eta batez bestekoa "inprimagailura" heltzeko. Orokortu distantzia horiek k1×k2 tamainako sare baterako.

Zein izango litzateke sarrera/irteerako lau prozesadoreen kokapenik egokiena sarean, baliabide hori erabili behar duten mezuen distantziak minimizatu nahi badira? Zein dira, kasu horretan, distantzia maximoa eta batez bestekoa?

b. (2, 4) prozesadoreak mezu bat inprimatu nahi du. Adierazi paketearen bideratze-erregistroa, eta nondik igaroko den.

c. Inprimatu nahi den aurreko mezua 10.000 bytekoa da. Komunikazioa pakete-kommutazioa teknikaren bidez egiten da, eta paketeak 120 + 8 bytekoak dira (datuak + kontrola; flit = byte). Mezu-bideragailuen latentzia 4 ns da, eta sareko loturak 200 MB/s-koak dira. Hau da komunikazio-protokoloa: bidali egiten da lehenbiziko paketea; paketea helburuan hartu denean, onarpen-pakete berezi bat (ACK, 8 byte) bidaltzen da atzera; prozesua errepikatzen da harik eta pakete guztiak bidali arte.

Kalkula ezazu mezu osoa bidaltzeko denbora, komunikazioa (1) store-and-forward; eta (2) cut-through motakoa izanik.

d. Eta bidea eraikitzeko zirkuitu-kommutazioa erabiliko balitz? (zunda-mezua, 8 byte, store-and-forward moduan mugitzen da).

6.28. Komunikazio-sarearen baliabideak homogeneoki erabiltzen ez badira edo mezuak eremu

jakin batzuetan pilatzen badira, bideratze moldakorra estatikoa (DOR) baino egokiagoa izan daiteke. Ikus dezagun adibide bat.

Aplikazio berezi bat exekutatu behar da 6×6-ko maila batean; komunikazio-patroia "matrize iraulia" izenekoa da: (i, j) koordenatuetako nodoa (j, i) koordenatuetako nodoarekin baino ez da komunikatzen. Bideratzea estatikoa da, "lehenik-X-gero-Y" motakoa. Marraz itzazu, mailan bertan, aplikazio horrek sortuko dituen pakete guztien bideak; adierazi asko erabiltzen den lotura pare bat, eta batere ez erabiltzen den beste pare bat. Ondorioz, azaldu, adibide baten bidez, zertan hobetuko den sarearen erantzuna —mezuen latentzia eta emaria (throughput)—, baldin eta bideratze moldakorra erabiltzen bada.

6.29. Sistema paralelo baten komunikazio-sareak gauza izan behar du, neurri batean behintzat,

sareko zenbait osagai matxuratuta izan arren mezuak helburuetara garraiatzeko. Kontuan hartu 6×6-ko maila bat, non DOR bideratze estatikoa erabiltzen den. (3, 3) eta (3, 4) nodoen arteko lotura matxuratu egin da eta hutsegiteei buruzko informazioa lokala da (tokiko nodoan). Nola gauzatu daiteke komunikazioa (3, 0) eta (3, 5) nodoen artean?

6.30. Irudian, 8×8 prozesadoreko maila bat ageri da. Mezuen ibilbidean zehar, bideratze

moldakorra erabiltzen da; mezuen blokeoak (deadlock) saihesteko, turn model delako teknika erabiltzen da (west-first aldaera). Irudian ageri denez (marra batez), sareko hainbat lotura ezin dira erabili, okupatuta daudelako edo beste edozein zio dela medio.

a. Azter itzazu ageri diren paketeen bideak (M1, M2 eta M3), eta esan, arrazoituz, zilegi diren ala ez. Zilegi ez badira, eman proposamen egoki bat. Zilegi badira, marraz ezazu beste aukera bat.

b. Marraz ezazu bide laburrago bat M2 mezurako. c. Marraz itzazu bide minimoak mezu hauetarako: → (3, 5) nodotik (1, 2) nodora → (7, 5) nodotik (6, 5) nodora → (4, 0) nodotik (3, 0) nodora.

(0, 0) (0, 7)

(7, 0) (7, 7)

M1

M3

M2


6.31. Bi dimentsioko maila bateko bi prozesadoreren artean, luzera minimoko bide asko dago. DOR bideratze estatikoa erabiltzen denean, bide horietatik bakar bat aukeratzen da. Bideratze moldakorra erabiliz, ordea, edozein bide aukeratu daiteke, dela hutsegiteak gainditzeko dela trafikoa saihesteko.

2D maila batean, luzera minimoko zenbat bide daude A(a1, a0) eta B(b1, b0) nodoen artean? Marraztu bide horiek guztiak bideratze-erregistroa [3, 2] den kasurako. Kasu jakin horretan erabiltzen diren loturetatik, zein loturak sortuko luke arazo gehien matxuratuko balitz?

6.32. Ohiko komunikazio-patroi bat multicast izenekoa da. Prozesadore batek mezu bera bidaltzen

du K prozesadoretara. K mezu bidali beharrean, helbide anitzeko mezu berezi bakarra bidaltzen da, eta mezu hori "errepikatu" egiten da tarteko bideragailuetan, harik eta helburu guztietara heldu arte.

Multicast eragiketa hau exekutatu behar da 8×8-ko maila batean:

(2, 4) → (0, 0), (0, 1), (0, 5), (1, 0), (1, 6), (3, 0), (4, 4), (4, 6), (5, 0), (5, 2), (6, 4) Marraztu mezuek hartuko dituzten bideak, bi kasu hauetan: (a) erabiltzen den lotura kopuruak

(trafikoa, beraz) minimoa izan behar du; eta (b) ibilbideen distantziek (paketeen latentziak, alegia) minimoa izan behar dute. Bideratzea DOR motakoa da.

6.33. Konputagailu paralelo baten komunikazio-sarearen portaera ilara-teoriaren bidez analiza

daiteke. Bideragailuetako ilarak modelatzeko eredu sinple bat M/M/1 izenekoa da, zeinean bi parametro hauek erabiltzen baitira:

µ: sistematik segundoko ateratzen den pakete kopurua (zerbitzu-denboraren alderantzizkoa).

λ: sistemara segundoko heltzen den pakete kopurua.

Bi parametro horietatik abiatuta, eta ilara-teoria erabiliz, honako informazio hau lor daiteke:

• bideragailuaren erabilera: ρ = λ / µ • ilaran k pakete itxaroten egoteko probabilitatea: P(k) = (1–ρ) ρk • ilaran dagoen pakete kopurua, batez bestean: N = ρ / (1–ρ) • pakete bat bideragailuan egongo den denbora: T = (1/µ) / (1–ρ)

Komunikazio-sare jakin baten mezu-bideragailuen zerbitzu-denbora (paketeak bideratzeko eta hurrengo bideragailura transmititzeko) 125 ns da, eta 1.600.000 pakete heltzen dira segundoko mezu-bideragailuetara (batez bestean).

Ilara-teoriari jarraituz, kalkula itzazu sare horretarako: (1) Bideragailuen erabilera; (2) Bideragailuetan egongo den pakete kopurua, batez bestean; (3) Pakete ilarak gainezkatzeko probabilitatea, 3 paketetarako tokia baino ez badago; (4) Batez besteko itxarote-denbora bideragailuetan, eta, ondorioz, pakete baten latentzia d = 8 distantziara doanean. Azkenik, marraz ezazu grafiko batean nola aldatzen den paketeek bideragailuetan egon behar duten denbora ρ-ren arabera, paketeen heltze-erritmoa aldatzean. Azaldu portaera.

6.34. MPP jakin batek 4.096 prozesadore ditu, 3 dimentsioko maila batean lotuta. Komunikazio-

sareko loturak 2 Gb/s-koak dira, paketeak 64 bytekoak dira (byte = flit), eta paketeen aurreneko flit-a prozesatzeko denbora 4 ns da. Komunikazioa cut-through motakoa da (DOR).

a. Kalkula itzazu sarearen erdibiketaren banda-zabalera, distantzia maximoa eta batez bestekoa. 378 nodotik abiatuta, zein da paketeek korritu dezaketen distantzia maximoa? zein nodo dago (edo daude) distantzia horretara? Sarea simetrikoa ez denez, distantziak nodoen posizioen araberakoak dira; zein da distantzia maximo guztien minimoa? sareko zein nodok dute distantzia maximo hori?

b. Mailaren dimentsio bakoitzeko kateak eraztun bihurtzeko behar diren loturak gehitzeko aukera analizatzen ari gara; horrela, maila toru bihurtuko litzateke. Sare berriaren batez besteko distantzia txikiagoa izango da, baina eraztunetan blokeoak (deadlock) gerta


daitezke, eta, ondorioz, bideratze-prozesuak konplexuagoa izan behar du; hau da, denbora gehiago beharko da paketeak bideratzeko. Zehazki, sare horretarako, zein da onar daitekeen tr parametro berriaren balio maximoa torua maila baino egokiagoa izan dadin, komunikazioen latentzia dela eta?

6.35. Erantzun galdera hauei.

1. Zein da 32 nodoko Omega sarearen batez besteko distantzia? Eta diametroa? Zein da ondorioa?

2. 32 prozesadoreko Omega sare batean, zein nodorekin konektatzen da 24 nodoa perfect shuffle komunikazio-patroia erabiliz?

3. Zein da oinarrizko desberdintasuna Omega eta, esaterako, hiperkuboa edo torua sareen artean?

4. Multikonputagailu txiki batek kubo bat osatzen duten 8 nodo ditu. Nodo bakoitzak 5 prozesadore ditu, lau kalkulurako eta bat komunikazioetarako, crossbar batez haien artean konektatuta. Lotura guztiak 1 Gbit/s-koak dira. Kalkula itzazu multikonputagailu horren komunikazio-sarearen batez besteko distantzia eta erdibiketaren banda-zabalera.

Makina horretarako, idatz ezazu X (x4, x3, x2, x1, x0) eta Y (y4, y3, y2, y1, y0) nodoen artean doazen paketeetarako bideratze-algoritmoa; adibide gisa, erabili bideratze-algoritmo hori 01001 prozesadoretik 11010 prozesadorera doan pakete baterako.

5. 32×32 nodoko toru batean, zein da 900 nodotik 257 nodorako distantzia? Sare hori duen konputagailuan aplikazio jakin bat exekutatzen da, eta sortzen diren mezuak honela banatzen dira: % 50, auzoetara; % 30, batez besteko distantziara; eta % 20, distantzia maximora. Kalkula ezazu aplikazio horren paketeen batez besteko distantzia.

6. Prozesadore kopuru bereko bi sare desberdin konparatu behar ditugu: 3D maila bat eta 2D toru bat. Gainerako parametroak berdinak izanik, zein prozesadore kopurutatik aurrera da hobea sare baten erdibiketaren banda-zabalera bestearena baino?

7. Multikonputagailu baten komunikazio-sareko loturak 1 Gbit/s-koak dira, eta komunikazioa store-and-forward motakoa da. 32 byteko pakete baten transmisio-denbora, distantzia 6 izanik, 1,56 µs da. Zenbat aldiz azkarragoa izango litzateke transmisioa, egoera berean, komunikazioa cut-through motakoa balitz? (trafikorik gabe; 8 biteko flit-ak, eta flit bateko goiburukoa).

8. Multikonputagailu baten komunikazio-sistemak denbora hauek (ns-tan) behar ditu L = 128 byteko pakete bat d = 10 distantziara bidaltzeko, loturen banda-zabalera B = 1 Gbit/s izanik: paketea sortzeko (igorlea), 200 + 10×L; paketea transmititzeko, 5×d + L/B; paketea onartzeko (hartzailea), 200 + 10×L.

Handitu egin da loturen transmisio-abiadura 4 Gbit/s arte. Zenbat aldiz azkarragoa izango da orain <igorle/hartzaile> komunikazio-prozesu osoa? Arrazoitu lortutako emaitza.

9. Komunikazio-sare jakin batean, kanal birtualak erabili behar dira. Beraz, a. Bideratze dinamikoa erabili ahal izango da sarea maila edo hiperkubo bat bada, baina ez

toru bat bada. b. Gehitu behar da lotura bat kanal birtual bakoitzeko. c. Pakete-bufferrak multzo edo klasetan egituratu behar dira, eta loturen erabilera

multiplexatu. d. Sarearen topologiaren arabera, zenbait kasutan (toruak) loturak gehitu beharko dira, eta

beste batzuetan (mailak) ez.


10. Zer distantzia dago 13 eta 44 nodoen artean 6 dimentsioko hiperkubo batean? Zenbat nodo daude distantzia horretara 13 nodotik abiatuta?

11. Multikonputagailu batek wormhole motako komunikazioa erabiltzen du. Sareko trafikoa altu xamar dela, paketeen latentzia % 20 handiagoa da, trafikoa ez dagoeneko kasuarekin alderatuta. Cut-through motako komunikazioa erabiliko balu: a. Latentzia berdintsua izango litzateke, bi komunikazio-moduak baliokideak dira eta. b. Latentzia handiagoa litzateke, wormhole moduan hobeto erabiltzen direlako sareko

baliabideak, sarea hutsik ez dagoenean. c. Latentzia txikiagoa litzateke, paketeak segmentatuta doazelako aurrera cut-through

moduan. d. Latentzia txikiagoa litzateke, gelditzen diren paketeak bideragailuko bufferretan

gordetzen direlako, oztopoa ez izateko. e. Aurreko ondorioak ez dira zuzenak.

12. Egiazkoa edo faltsua? Zergatik? ▪ Trafikoa zorizkoa denean, multikonputagailu baten komunikazio-sarea asetzeko behar den

trafikoa altuagoa da komunikazioa CT moduan denean WH moduan denean baino. ▪ Kanal birtualak osatzeko, ilaratan banatu behar dira bideragailuko bufferrak, ilara bat

kanal birtual bakoitzeko (eta, agian, bufferrak gehitu). ▪ Kanal birtualak erabiltzen direnean, paketeak bideratzeko denbora (routing-denbora)

txikiagoa da, saihesten baita mezuak geldituta geratzea. ▪ Turn model bideratze-estrategiaren bat da, zeinaren bidez bideratze moldakorra eta

blokeorik gabekoa lortzen baita mailetan (ez, aldiz, toruetan). ▪ Sareak kudea dezakeen mezu kopurua, ase egin gabe, zuzenki proportzionala da paketeek

zeharkatzen duten distantziarekin (hazi egiten da distantziarekin).

13. 128 prozesadoreko multikonputagailu baten komunikazio-sarea hiperkubo bat da. Komunikazioa cut-through motakoa da, parametro hauen arabera: loturen banda-zabalera, 0,5 Gbit/s; paketeak bideragailuetan prozesatzeko denbora, 3 ns; flit bat = byte bat.

P42 nodotik 128 flit-eko pakete bat bidali behar da P115 nodora. Paketea sortu eta sarean sartzeko, 1 µs behar da, eta beste hainbeste denbora erabili behar da helburuan paketea hartzeko. Kalkula ezazu komunikazio-denbora osoaren zein ehuneko dagokion paketearen garraio fisikoari (ez dago trafikorik sarean).

14. Multikonputagailu baten komunikazio-sareak west-first motako bideratze moldakorra erabiltzen du paketeak bideratzeko. Irudiko bi kasuetarako, kalkula itzazu, eta marraztu, zenbat bide minimo desberdin erabil ditzakeen pakete batek P1etik P2ra joateko.

15. Multikonputagailu baten komunikazio-sarearen portaera analizatu da, informazio-jariorako hiru aukera desberdin erabiliz. Paketeen latentzia neurtu da, trafikoaren arabera, eta irudiko emaitzak lortu dira.

Zein teknika erabili da, kasu bakoitzean, informazio-jarioa kontrolatzeko? Zergatik? Argudiatu erantzunak.

P1

P2

P2

P1

Late

ntzi

a (s

)

Trafikoa (B/s)

(a)

(b) (c)


16. 256 prozesadoreko konputagailu batek Omega sare bat erabiltzen du komunikazioetarako. Kommutagailuak 4×4 tamainakoak dira (4 sarrera eta 4 irteera). Zenbat kommutagailu behar dira sarea osatzeko? Zer motako "sare" da, berez, kommutagailu bakoitza? Zergatik? Mezu bat bidali behar da 156 prozesadoretik 122 prozesadorera; zein irteera-portu erabiliko da urrats bakoitzeko kommutagailuetan helburura heltzeko?

17. Komunikazio-latentzien analisi makroskopikoaren arabera, mezuen latentzia proportzionala da tamainarekin, L, baina badago hasiera-denbora bat (th). Cluster sinple baten komunikazio-sarearen banda-zabalera neurtu da, mezuen tamainaren arabera, eta irudiko emaitza lortu da. Grafikoan oinarrituta, kalkulatu L1/2 parametroa; ondoren, eta kontuan hartuta byte bat transmititzeko denbora 7 ns dela, kalkula ezazu pakete txikiak (byte batzuk) transmititzeko denbora minimoa.

18. Multikonputagailu baten komunikazio-sarea aztertzen denean, bi parametro kontuan hartu ohi dira: paketeen latentzia, eta sarearen emaria edo throughput-a. Marraztu eta azaldu nolakoa den bi parametro horien portaera sareko trafikoaren arabera (sare tipiko batean eta trafikoa zorizkoa denean).

19. Zer da "0 kopiako" komunikazio-protokolo bat? Zertarako eta zergatik erabiltzen dira protokolo horiek?

20. Zenbait baldintzapetan, bideratze moldakorrak (dinamikoak) estatikoak baino emaitza hobeak lortzen ditu. Hala ere, arazoak ere sor ditzake. Azaldu, zehatz-mehatz, abantaila eta desabantaila nagusiak, eta desabantaila horiek nola konpon daitezkeen.

21. Dakizunez, multikonputagailu baten sarearen erdibiketaren banda-zabalerak muga teoriko bat ezartzen dio sare horrek onar dezakeen trafiko maximoari (trafikoa zorizkoa izanik). Sare errealen analisietan lortutako emaitzek, aldiz, sareko asetze-puntua askoz lehenago erdiesten dela erakusten dute, tipikoki aurreko trafiko maximoaren % 25 - % 50 tartean, bideratze-mekanismoaren arabera. Azaldu, labur eta zehatz, fenomeno horren zergatia.

22. Definitu, zehatz-mehatz eta labur, kontzeptu hauek (eta eman euskarazko itzulpena): • adaptive routing • bandwidth • bisection bandwidth • blocking network • broadcast • circuit switching • communication pattern • cut-through • directed network • DOR • fat tree • hypercube • latency • mesh • message deadlock • message passing • message router • multistage network • packet • permutation • routing record • store-and-forward • switch • throughput • torus • virtual channel • wormhole

0

20

40

60

80

100

120

140

160

100 1000 104 105 106

Lortutako banda-zabalera

(MB/s)

L, mezuen tamaina (byte)

Ariketak: Datuen koherentzia DSM konputagailuetan ▪ 47 ▪

7.1. Multiprozesadore batek baditu 2.048 prozesadore. Prozesadore bakoitzeko memoria nagusia 1 GB-koa da eta cachea 2 MB-koa; datu-blokeak 256 bytekoak dira. Datuen koherentzia mantentzeko, direktorioak erabiltzen dira.

Kalkula ezazu koherentzia-direktorio osoaren tamaina, bytetan eta MNaren ehuneko gisa, hiru kasu hauetan:

a. Memoria nagusiaren ondoko direktorioa: full bit vector motakoa, 2 bit blokeen egoerak adierazteko.

b. Memoria nagusiaren ondoko direktorioa: limited bit vector motakoa (10 kopia gehienez), 2 bit blokeen egoerak adierazteko.

c. Cacheetan banatutako direktorioa: esteka bikoitzeko zerrendak, 6 bit blokeen egoerak adierazteko cachean, eta 2 bit memoria nagusiaren ondoko direktorioan.

7.2. CC-NUMA motako konputagailu baten komunikazio-sarea 8×8-ko maila bat da. Datu-

koherentziarako direktorioa MNari atxikita dago. P0 prozesadoreak hutsegite bat izan du cachean aldagai bat irakurtzean; aldagaia P37 prozesadoreko memoriakoa da, eta aldatuta dago P50 prozesadoreko cachean.

Eragiketa hori betetzeko hiru aukera ageri dira irudian. Kalkula ezazu P0 prozesadoreko eragiketaren latentzia, irudiko hiru komunikazio-estrategietarako. Kontuan hartu parametro hauek: komunikazioa cut-through motakoa da, eta flit-a eta sareko loturak byte batekoak dira; koherentzia-mezuak 6 edo 70 bytekoak dira (kontrola edo datuak); sareko loturak 250 MB/s-koak dira, eta 3 ns behar dira sareko bideragailuetan paketeak bideratzeko; sarean ez dago trafikorik; 75 ns behar dira pakete bat sarean injektatzeko (iturburuan), eta beste 75 ns pakete saretik ateratzeko (helburuan).

1. eskaera/erantzuna 2. intervention forwarding 3. reply forwarding

7.3. MPP baten koherentzia-informazioa cache memorietan banatuta dago, esteka bikoitzeko

zerrendak osatuz; komunikazio-protokoloa eskaera/erantzuna motakoa da. Komunikazio-sarea 8×8-ko maila bat da.

Une batean, datu-bloke jakin baten lau kopia dago cacheetan: (0, 0) → (2, 6) → (4, 1) → (7, 7) prozesadoreetan; datu-blokea (0, 0) prozesadoreko memoriakoa da, eta kopiak koherenteak dira. Kopia bat duen prozesadore batek idatzi egiten du bloke horretan. Kalkula ezazu, aurreko ariketako datuak erabiliz, koherentzia-eragiketak beharko duen denbora (minimoa):

a. Idazketa (0, 0) prozesadorean egiten denean. b. Idazketa (4, 1) prozesadorean egiten denean.

7.4. MPP baten datuen koherentzia mantentzeko, full bit vector motako direktorioa erabiltzen da

(bit bat egoera adierazteko –dirty–). Une jakin batean, P0 prozesadoreak cachean duen aldagai batean idazten du; aldagaia P8 prozesadoreko memoriakoa da, eta, une horretan, bi kopia daude sisteman, S egoeran, P0 eta P1 prozesadoreen cacheetan.

Idazketa egiten ari delarik, P1ek ere idazten du bloke bereko aldagai batean, eta P2k bloke bereko aldagai bat irakurtzen du. Hiru eragiketa horiek ordena honetan heltzen dira direktoriora: P0ren idazketa; gero, P1ena; eta, azkenik, P2ren irakurketa.

Adierazi prozesadoreen artean trukatuko diren mezuak, elkarrizketak <eskaera/erantzuna> motakoak izanik. Labur, zertan aldatuko da aurrekoa elkarrizketak reply forwarding motakoak badira?

L

H

R 1. Eskaera

4. Erantz. (Blokea) 3. Erantz. (Blokea)

2. Eskaera

L

H

R 1. Eskaera

3b. Blokea (egun.)

3a. Erantz. (Blokea)

2. Eskaera

L

H

R 1. Eskaera

2. Erantz. 4b. Blokea (egun.)

4a. Erantz. (Blokea)

3. Eskaera


7.5. DSM motako multikonputagailu jakin batean, SCI koherentzia-protokoloa erabiltzen da datuen koherentzia ziurtatzeko (koherentzia-informazioa cacheetan banatuta, esteka bikoitzeko zerrendak, baliogabetzea). Une batean, P6ko MNko datu-bloke baten hiru kopia daude prozesadoreen cacheetan, koherenteak, P2n (lehena), P4n, eta P7n (azkena). Adieraz ezazu nola aldatuko den koherentzia-informazioa hiru eragiketa hauek exekutatzen direnean, bata bestearen atzetik, datu-bloke horren gainean: rd4, rd5, wr7.

7.6. MPP batek SCI motako koherentzia-protokolo bat erabiltzen du (esteka bikoitzeko zerrendak,

baliogabetzea). Une jakin batean, memoria-eragiketa hauek sortzen dira prozesadoreetan, denak P2ko memoria-bloke beraren gainean (zenbakiak prozesadorea adierazten du): LD1, LD2, LD3, ST1, LD2, LD3, ST2, LD3, ST3.

a. Adierazi, taula batean, nola aldatzen den datu-blokearen kopia-zerrenda: egoerak eta erakusleak (hasieran, ez dago kopiarik).

b. Azaldu zehazkiago koherentzia-hardwarearen ekintzak ST1 agindua exekutatu behar denean. Balioetsi koherentzia-eragiketa horien exekuzio-denbora; prozesadoreek kate bat osatzen dute P0–P1–P2–... eta koherentzia-mezuen latentziak distantziarekiko proportzionalak dira (d × T).

7.7. 64 prozesadoreko CC-NUMA motako konputagailu batek 6 dimentsioko hiperkubo bat

erabiltzen du komunikazio-sare gisa. Prozesadore bakoitzak 512 MB-ko memoria eta 1 MB-ko cachea erabiltzen ditu, eta datu-blokeak 64 bytekoak dira.

Datuen koherentzia mantentzeko, direktorio bat erabiltzen da, memoria nagusiari atxikia (full bit vector, 3 biteko egoerak, baliogabetzea, MESI, reply forwarding).

a. Kalkulatu zenbat memoria behar duen makina horren direktorioak (osoa). b. Une jakin batean, P0 prozesadoreak idatzi egin behar du cachean ez duen aldagai batean.

Aldagai horren helbidea P12 prozesadoreko memoriari dagokio, eta une horretan blokearen bi kopia daude sisteman, P27 eta P44 prozesadoreetan. Adierazi, pausoz pauso, nola ebatziko den cacheko hutsegitea (bidaliko diren mezuak, haien edukia, egoerak, etab.).

c. Demagun honela modela daitekeela pakete baten komunikazio-denbora sisteman (sinplifikatuta): T = 200 + 2 × (D × L) ns, non D distantzia eta L paketearen luzera bytetan diren, hurrenez hurrez. Bi motako mezuak bidaltzen dira: "txikiak", 6 bytekoak, eta "handiak", 70 bytekoak. Kalkula ezazu aurreko eragiketa betetzeko beharko den denbora.

d. Nahiz eta direktorioak uste duen aldagai horren kopia bat dagoela P44 prozesadorean, kopia hori ez da existitzen. Posible al da egoera hori? Baiezkoan, zertan aldatuko litzateke prozesadore horren erantzuna? Zergatik?

7.8. 64 nodoko CC-NUMA motako multiprozesadore batek 8×8-ko toru bat erabiltzen du

komunikazio-sare gisa. Prozesadore bakoitzak 1 GB-ko memoria nagusia eta 512 kB-ko cachea ditu, eta datu-blokeak 128 bytekoak dira. Datuen koherentzia ziurtatzeko, SCI motako protokolo bat erabiltzen da (esteka bikoitzeko zerrendak, baliogabetzea).

a. Zein da makina horren koherentzia-direktorioaren tamaina (osoa)? Egoerak adierazteko, 2 bit erabiltzen dira memoria nagusi ondoko direktorioan, eta 4 bit cacheetan.

b. Kopiarik gabeko egoeratik abiatuta, honako eragiketa-segida hau sortzen da prozesadoreetan (helbideratzea byteka da): rd1(@1); rd2 (@2); wr1 (@2, 4); rd25 (@10); rd31 (@1250); rd54 (@25); wr19 (@533, 6); wr25 (@33, 0).

1. Marraztu, aginduz agindu, 0 datu-blokeko kopia zerrenda nola osatzen den. 0 blokea P0 prozesadoreko memoria nagusiari dagokio. Erabili ezazu hau bezalako eskema grafikoa.

MNko dir.

Pi egoera

Cacheetako dir.

Pj egoera

Pk egoera

Ariketak: Datuen koherentzia DSM konputagailuetan ▪ 49 ▪

2. Azken eragiketarako, wr25 (@33, 0), adierazi koherentzia mantentzeko egingo diren eragiketak (trukatuko diren mezuak, zeinen artean, mezuen edukia, blokearen eta zerrendaren egoera, etab.).

3. Honela modela daiteke prozesadoreen arteko komunikazio-denbora makina horretan: T = 100 + 2 × (4D + L) ns —D, distantzia; L paketearen tamaina bytetan—. Kontrol-mezuak 10 bytekoak dira, eta datuak daramatzatenak (bloke bat) 140 bytekoak. Kalkula ezazu azken eragiketaren exekuzio-denbora (koherentzia dela eta; mezuak denbora galdu gabe erantzuten dira).

7.9. CC-NUMA motako 128 prozesadoreko multikonputagailu batek hiperkubo bat erabiltzen du

komunikazio-sare gisa. Prozesadore bakoitzak 1 GB-ko memoria nagusia eta 512 kB-ko cachea ditu; blokeak 128 bytekoak dira. Datuen koherentzia mantentzeko, direktorioak erabiltzen dira: full bit vector, reply forwarding, baliogabetzea, 4 biteko egoerak.

a. Kalkula ezazu koherentzia-direktorio osoaren tamaina makina horretan. Zenbatetara (%) txikiagotuko litzateke direktorioaren tamaina limited bit vector izeneko teknika erabiliko bagenu, blokeetako kopia kopuru maximoa bost izanik? Bost kopiako direktorioa erabiltzen bada, zer egin beharko litzateke, baldin eta aplikazio batek bloke baten sei kopia (edo gehiago) beharko balitu?

b. Une jakin batean, P0 prozesadoreko memoria nagusiko bloke baten kopia bakarra dago sistema osoan, P10 prozesadorean eta E egoeran. Une horretan, P50 prozesadoreak bloke hori irakurri behar du, eta, aldi bertsuan, P100 prozesadoreak idatzi egin behar du bloke beraren gainean (bere eskaera aurrekoa baino geroxeago heltzen da direktoriora, baina aurreko eragiketa bukatu baino askoz lehenago). 1. Adierazi eskematikoki, grafo baten bidez eta mezu bakoitzaren azalpen labur batez,

prozesadoreen artean bidaltzen diren mezuak eta nola aldatzen den blokearen egoera prozesadoreetan zein direktorioan, bi eragiketak, irakurketa eta idazketa, bukatu arte.

2. Balioetsi P100 prozesadoreak beharko duen denbora idazketa-eragiketa burutzeko. Sinplifikatzeko, hartu T = 120 + 4×D + L ns (mezuak denbora galdu gabe prozesatzen dira). Pakete txikiak 4 bytekoak dira eta luzeak 132 bytekoak.

3. Azkenik, izan bedi honako egoera hau aurreko koherentzia-eragiketetan. P50 prozesadoreak baliogabetze-mezu bat hartuko du une jakin batean, P100 prozesadoreko idazketa dela eta; hori gertatzen denean, ordea, P50 prozesadoreak ez du oraindik hartu eskatu zuen datu-blokea. Litekeena da hori gertatzea? Zergatik? Nola konponduko da egoera hori?

7.10. Erantzun, zehatz-mehatz, galdera hauei:

1. Cacheetan banatzen den koherentzia-informazioa antolatzeko, esteka bikoitzeko zerrendak erabiltzen dira SCI koherentzia-protokoloan; bi esteka horiek zerrendako aurreko eta hurrengo kopiak erakusteko erabiltzen dira. Hala ere, badago esteka bakarreko zerrendak ere erabiltzea. Adieraz ezazu nola egingo den Roll-Out eragiketa esteka bakarreko zerrendak erabiltzen dituen koherentzia-protokolo batean.

2. DSM konputagailu baten prozesadore batean, huts egin da cachean ST A,R2 agindua exekutatzean. A aldagaia duen datu-blokearen egoera direktorioan (full bit vector) honako hau da: 10110 | S. Zein izango da bloke horren azken egoera direktorioan, eragiketa bukatutakoan?

3. Adierazi, labur eta eskematikoki, zer egin behar den datuen koherentzia ziurtatzeko Origin 2000 motako makina batean, prozesadore batek idatzi egiten badu cacheko datu-bloke batean, honako egoera hauetako batean: (a) E egoeran; (b) S egoeran; eta (c) M egoeran.


4. DSM konputagailu baten prozesadore batek idatzi egin behar du cachean duen aldagai batean. Aldagai hori duen blokearen egoera Head–Dirty da. Zein eragiketa, eta zein ordenatan, exekutatu behar dira? Zein izango da blokearen azken egoera, cachean zein memoria nagusian?

5. SCI koherentzia-protokoloa erabiltzen da DSM sistema batean. P1 prozesadoreari dagokion datu-bloke bat P2ko eta P3ko cacheetan kopiatu da. Blokearen koherentzia-informazioa direktorioan (MNan) Fresh | P2 da. Zein izango da koherentzia-informazioa P3ren cachean?

Egoera horretatik abiatuta, P3k bloke horren aldagai batean idazten du. Hori egin ahal izateko, zenbat mezu bidaliko dira, guztira, prozesadoreen artean?

6. 64 nodoko DSM multikonputagailu baten koherentzia-sistemak ezaugarri hauek ditu: baliogabetzea, full bit vector, reply forwarding. Une jakin batean, P0 prozesadoreak A aldagaia (P5eko memoriakoa) idazten du. Adierazi grafikoki eragiketa betetzeko trukatuko diren mezuak, nola geratuko den datu-blokea cacheetan eta direktorioan (egoera eta edukia), eta abar, bi kasu hauetan: a. Blokea E egoeran dago P0ko cachean, eta 100…0 | E egoeran direktorioan. b. Blokea S egoeran dago P0ko cachean, eta 110…0 | S egoeran direktorioan.

7. 64 nodoko DSM multikonputagailu batek SCI koherentzia-protokoloa erabiltzen du: zerrenda estekatuak cacheetan, baliogabetzea. Une jakin batean, P0 prozesadoreak A aldagaia (P5eko memoriakoa) idazten du. Adierazi grafikoki eragiketa betetzeko trukatuko diren mezuak, nola geratuko den datu-blokea cacheetan eta direktorioaren hasieran, eta abar, bi kasu hauetan: a. Blokea Only–Fresh | * - * egoeran dago P0ko cachean, eta Fresh | P0 egoeran zerrendako

hasieran (direktorioan). b. Blokea Tail–Valid | P1 - * egoeran dago P0ko cachean, eta Gone | P1 egoeran zerrendako

hasieran (direktorioan).

8. MPP baten datu-koherentzia "Origin" motako direktorioen bidez ziurtatzen da. Cacheetan dauden aldagaiekin egin daitezkeen eragiketak direla eta (irakurketa/idazketa, asmaztea/hutsegitea) (1) Zein kasutan erabili behar da koherentzia-direktorioa? (2) Direktorioa erabili behar den kasuetan, zein kasutan bidali behar dira mezuak sarean zehar?

9. P prozesadoreko cc-NUMA makina batean, prozesadoreek 1 GB RAM eta 1 MB cache bana dituzte. Datuei buruzko koherentzia-informazioa banatuta dago, MNaren ondoan dagoen direktorioan eta cacheen direktorioetan. Koherentzia-informazioari dagokionean, zera esan daiteke:

a. MNaren ondoko direktorioa cache memoriarena baino 2×P aldiz txikiagoa da. b. MNaren ondoko direktorioa cache memoriarena baino 500 aldiz txikiagoa da. c. MNaren ondoko direktorioa cache memoriarena baino 500 aldiz handiagoa da. d. MNaren ondoko direktorioa cache memoriarena baino 2×P aldiz handiagoa da.

Ariketak: Begizten paralelizazioa eta banaketa ▪ 51 ▪

8.1. Aplikazio jakin bat exekutatu behar da, paraleloan, hiru prozesadoreko SMP makina batean. Horretarako, 14 ataza identifikatu dira; hauek dira atazen "kostuak" (exekuzio-denborak) eta haien arteko dependentziak:

Atazak A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14

Kostua 2 8 2 4 5 1 3 2 2 1 2 1 3 2

Depend. – – – – A1 – A6 A3 A5 A9 A7 A1,A5 A7 A8

Erabaki nola banatu ataza horiek hiru prozesadoreetara, azelerazio-faktorerik handiena

eskuratu ahal izateko.

8.2. Aztertu begizta hauek, egin itzazu dependentzia-grafoak, eta erabaki zein den paraleloan

exekutatzeko aukerarik egokiena (idatzi kodea).

▪ 1. begizta do i = 0, 98 (1) A(i) = A(i) + 1 (2) B(i+1) = A(i) * 2 (3) C(i) = A(i) + B(i+1)/2 enddo

▪ 2. begizta do i = 1, 99 (1) A(i) = A(i) + C(i-1) (2) B(i) = A(i) * 2 (3) C(i) = B(i) - 1 enddo

▪ 3. begizta do i = 1, 97 (1) A(i) = A(i) + C(i-1) (2) B(i) = A(i) * 2 (3) C(i+2) = B(i) - 1 enddo

▪ 4. begizta do i = 0, 97 (1) C(i) = A(i) * A(i) (2) B(i) = A(i) + C(i+2) enddo

▪ 5. begizta do i = 2, 99 (1) A(i) = C(i) + 1 (2) B(i) = B(i) * 2 (3) D(i) = B(i) - A(i-1) (4) F(i) = D(i-2) enddo

▪ 6. begizta do i = 2, 98 (1) A(i) = A(i) + 1 (2) B(i) = A(i-1) + C(i-2) (3) C(i+1) = B(i-2) * 2 enddo

▪ 7. begizta do i = 1, 99 (1) A(i) = B(i) - 2 (2) C(i) = A(i) * 3 + D(i-1) (3) D(i) = A(i-1) enddo

▪ 8. begizta do i = 2, 99 (1) A(i) = A(i) + D(i-1) (2) B(i) = B(i) * 2 (3) C(i) = A(i-1) * 2 + F(i-2) (4) D(i) = C(i) + B(i) (5) F(i) = G(i) * G(i) enddo

▪ 9. begizta do i = 2, 49 do j = 0, 99 (1) A(i,j) = B(i-2,j) (2) B(i,j) = A(i-1,j) + 1 enddo enddo


8.3. Begizta hau exekutatu behar da 10 prozesadoreko konputagailu paralelo batean. Analiza ezazu nola paralelizatu begizta ahalik eta modurik eraginkorrenean, eta idatzi prozesadoreek exekutatuko duten kodea (banaketa estatikoa, ondoz ondokoa; pid = 0..9 aldagai pribatua prozesuak identifikatzeko).

do i = 2, 101 do j = 0, 199 (1) A(i,j) = A(i,j+2) * 2 (2) B(i,j) = B(i-2,j) * 3 enddo enddo

8.4. Exekutatu behar da honako begizta hau lau prozesadoreko sistema paralelo batean:

do i = 1, 40 <kodea> enddo

Iterazio guztiak independenteak dira, eta haien exekuzio-denbora T(i) = i da (hau da, lehenbiziko iterazioa 1, bigarrena 2, eta abar.)

Iterazioak banatzeko estrategia hauek kontuan harturik, kalkula itzazu programa paraleloaren exekuzio-denbora eta azelerazio-faktorea:

a. Estatikoa: 1. ondoz ondokoa 2. tartekatua b. Dinamikoa: 1. autobanaketa (self & chunk scheduling), Z = 1 eta Z = 5 2. autobanaketa gidatua, Zs = (N – i) / P 3. trapezoidala, Z1 = 9, k = 1

Banaketa dinamikoko eragiketa bakoitzaren kostua "1" da. 8.5. Aukera asko ditugu begizta baten iterazioak banatzeko, estatikoki zein dinamikoki. Esaterako,

doubling izeneko estrategia erabil daiteke, zeinaren bidez prozesadore bakoitzari i eta N–i iterazioak (edo zatiak) esleitzen zaizkion. Banaketa hori oso egokia da "matrize × bektore" eragiketaren kasu jakin batean, matrizea triangeluarra denean (hots, diagonalaren gainetik dena 0 denean), modu orekatuan banatzen duelako lana prozesadoreen artean.

do i = 0, N-1 do j = 0, i-1 C(i) = C(i) + M(i,j) * B(j) enddo enddo

Idatz ezazu P prozesadoreko SMP makina baten prozesadoreek exekutatuko duten kodea

aurreko begizta doubling motako banaketa estatikoa erabiliz exekutatu ahal izateko. 8.6. Begizta hau exekutatu behar da multiprozesadore batean, paraleloan:

do i = 2, 99 (1) A(i) = A(i) * 2 (2) B(i+1) = A(i) + C(i-1) (3) C(i) = 2 * C(i) + 3.0 (4) D(i) = C(i) / 5 (5) E(i+1) = D(i) + F(i) (6) F(i+1) = E(i-2) - 1.2 enddo

a. Analiza itzazu begiztaren dependentziak, eta idatzi begizta paraleloa, erabili behar diren sinkronizazio-funtzioak gehituta.

b. Paralelizatu berriz begizta, baina orain sinkronizazio-funtzioak erabili gabe. Zenbat bider azkarrago exekutatuko da begizta serieko kasuarekin alderatuta (gutxi gora behera)?


8.7. Begizta hau exekutatu behar da lau prozesadoreko multiprozesadore batean:

do i = 1, 63 do j = 4, 63 A(i,j) = A(i-1,j) * A(i,j-4) enddo enddo

Adierazi nola exekuta daitekeen begizta paraleloan, modurik eraginkorrenean, eta idatzi

kodea (goi-maila); iterazioen banaketa estatikoa da.

8.8. Analiza itzazu begizta honen dependentziak, eta adierazi paralelizatzea merezi duen ala ez,

nola eta zergatik. Baiezkoan, idatzi kodea; erabil itzazu gertaera-bektoreak sinkronizazio-mekanismo gisa.

do i = 2, 98 (1) A(i+1) = X(i) + 2 (2) B(i) = B(i) + 1 (3) C(i) = B(i-2) + A(i+1) + D(i-1) (4) D(i) = X(i) * X(i) (5) E(i) = D(i) + C(i) enddo

8.9. Analiza itzazu begizta honen dependentziak, eta, aukerarik badago, paralelizatu begizta

sinkronizazio-funtziorik erabili gabe.

k = 3 do i = 1, 100 (1) A(i) = A(i) / 3.0 (2) B(2*i) = C(i+2) + X(i) (3) C(i+1) = B(k) + 3.0 / A(i) (4) D(i) = C(i) * C(i) k = k + 2 enddo

8.10. Exekutatu behar da, konputagailu paralelo batean, honako begizta hau:

do i = 3, 102 (1) A(i) = F(i) + 1 (2) B(i) = C(i-1) * 2 if (H(i)>0) then (3) C(i) = A(i-2) + D(i-2) (4) F(i) = A(i) / B(i) + F(i-1) endif enddo

a. Sortu dependentzia-grafoa eta erabaki begizta paraleliza daitekeen. Idatzi kode paraleloa;

erabil itzazu gertaera-bektoreak sinkronizaziorako. Gero, adierazi aurreko kodean egin behar diren aldaketak sinkronizazio-kontagailuak erabili behar badira.

b. Paraleliza daiteke kodea sinkronizazio-mekanismo gisa hesiak erabiliz? Nola? Eta sinkronizazioa erabili gabe? Nola?

c. Begizta 4 prozesadoreren artean exekutatu behar da, banaketa dinamikoa erabiliz (guided self-scheduling motakoa). Idatz ezazu kodea aurreko aukeretatik zure ustez egokiena den kasurako, eta kalkula itzazu esleipen-eragiketako kopurua eta bakoitzean banatuko den iterazio kopurua.


8.11. Sistema paralelo batean exekutatu behar da begizta hau:

do i = 1, 24 (1) A(i) = B(i) + D(i-1) (2) C(i) = C(i) * 2 (3) D(i) = C(i-1) + F(i) (4) if (F(i) = 0) then E(i+1) = D(i-1) - 1 enddo

a. Paralelizatu begizta, sinkronizazio-eragiketetarako kontagailuak erabiliz. b. Paraleliza daiteke kodea sinkronizazio-eragiketak erabili gabe? Nola?

8.12. Honako begizta hau exekutatu behar da konputagailu paralelo batean:

do i = 1, 24 do j = 1, i (1) A(i,j) = B(i,j) + 1 (2) C(i,j) = A(i-1,j) * 2 enddo enddo

a. Sor ezazu dependentzia-grafoa, eta erabaki nola paralelizatu begizta ahalik eta modurik eraginkorrenean. Idatzi kodea lau prozesadoreko kasurako; iterazioen banaketa dinamikoa da: tamaina finkoko (lau iterazioko) zatiak (chunk scheduling).

b. Zenbat aldiz exekutatuko da iterazioak banatzeko eragiketa? Kalkula ezazu exekuzio paraleloan lortuko den azelerazio-faktorea; kalkuluak egiteko, erabil itzazu datu hauek: begiztako agindu baten exekuzio-denbora = 1; sinkronizazio-eragiketen exekuzio-denbora (sekzio kritiko sinple bat, esaterako) = 10.

8.13. Exekutatu behar da 8 prozesadoreko SMP makina batean honako begizta hau:

do i = 2, 10000 (1) A(i) = B(i-1) + 1 (2) B(i) = B(i) * 2 (3) C(i) = B(i-2) - 3 enddo

Idatz ezazu prozesadore bakoitzak (pid = 0..7) exekutatuko duen kodea; iterazioen banaketa estatikoa da, ondoz ondokoa.

8.14. Aplikazio jakin batean, honako kode zati hau exekutatu behar da:

do i = 0, 499 if (B(i)>0) then X = X + FUN(A(i),B(i)) enddo

do i = 0, 999 do j = 0, 99 C(i,j) = C(i+2,j) + X enddo enddo

Aurrekoa exekutatzeko, P = 10 prozesadore erabili nahi dira, eta, horretarako, kode paraleloa

idatzi behar da, ahalik eta eraginkorrena (paralelismo-maila altuena eta sinkronizazio-beharra txikiena dituena). Atazen banaketa dela eta, lehenbiziko begizta dinamikoki banatu behar da prozesadoreen artean, tamaina finkoko zatiak erabiliz (10 iterazio, chunk scheduling); bigarrena, ordea, estatikoki (ondoz ondoko iterazioak).

Idatz ezazu prozesadore bakoitzak paraleloan exekutatuko duen kodea (goi-maila). Prozesadoreek identifikadore bana dute, pid, 0tik 9ra. Erabil itzazu behar dituzun sinkronizazio-funtzioak, eta adierazi nolakoak diren erabiltzen dituzun aldagaiak, pribatuak edo partekatuak.


8.15. Begizta hau bektore-konputagailu batean zein konputagailu paralelo batean exekutatu behar da:

do i = 0, 99 do j = 1, 998 (1) A(i,j+1) = A(i,j-1) + B(i,j) (2) B(i,j) = B(i,j) * B(i,j) * A(i,j+1) enddo enddo

Analiza itzazu aginduen arteko dependentziak, eta marraztu dependentzia horiek iterazio-espazioan. Gero, eta ahal den neurrian:

a. Adierazi nola bektoriza daitekeen begizta, eta idatzi dagokion bektore-kodea. A eta B matrizeak 100×1000 tamainakoak dira, eta A edo B helbideek matrize bakoitzeko (0, 0) osagaia erakusten dute.

b. Adierazi nola paraleliza daitekeen begizta, ahalik eta modurik eraginkorrenean, eta idatzi prozesadore bakoitzak exekutatuko duen kodea (goi-maila); erabil ezazu zatikako banaketa dinamikoa (chunk scheduling) iterazioak banatzeko, 10 iterazioko zatiak, hain zuzen ere.

Konputagailu paraleloak 8 prozesadore ditu, eta badakigu begiztako iterazioen exekuzio-denbora berdintsua dela. Egokia al da aurreko banaketa-metodoa begizta horretarako? Zergatik? Aukera egokiagoren bat?

8.16. Erantzun zehatz-mehatz galdera hauei:

1. Bi aukera ditugu gertaeren bidezko sinkronizazioa gauzatzeko: gertaera-bektoreak erabiltzea eta kontagailuak erabiltzea. Adierazi metodo bakoitzaren abantailak eta desabantailak.

2. Bi prozesu sinkronizatzeko, gertaera-bektore bat erabiltzen ari da. Une jakin batean, hau da bektore horren edukia: i = 0 1 2 3 4 5 6 7 8 9...

gA(i) = 1 1 1 1 0 1 0 0 1 1... Erabili izan bagenu sinkronizazio-kontagailu bat sinkronizazioa ziurtatzeko, zein izango

litzateke haren balioa une horretan?

3. Begizta baten iterazioak (edo, oro har, atazak) prozesadoreei esleitzeko, banaketa edo scheduling dinamikoko bi estrategia mota dago. Zertan bereizten dira? Zer bilatzen du horietako bakoitzak?

4. Begizta hau paraleloan exekutatu behar da, bost prozesadoreren artean. Iterazio guztiak independenteak dira, eta iterazioen banaketa dinamikoa da, chunk scheduling motakoa (Z = 4 iterazio). Idatz ezazu prozesadore bakoitzak exekutatuko duen kodea.

for (i=0; i<1000; i++) fun(i); /* funtzio edo prozedura bat */

Gutxi gora behera, iterazioak banatzeko eragiketen (sekzio kritikoaren) kostua fun(i) funtzioaren kostuaren % 50 da. Beste arazorik kontuan hartu gabe, zenbatekoa izango da lortuko den azelerazio-faktorea (speed-up)?

5. Begizta bat exekutatu behar da sistema paralelo heterogeneo batean, non lau prozesadore A motakoak diren eta beste laurak B motakoak. Prozesadore bakarra erabiliz, begiztaren exekuzio-denbora 1 s da A motako prozesadoreetan, eta 0,5 s B motako prozesadoreetan. a. Banatu ezazu estatikoki N iterazioko begizta sistemako zortzi prozesadoreen artean,

eraginkortasunik handiena eskuratu ahal izateko. b. Idatzi kodea self-scheduling motako banaketa egiteko, eta adierazi aukera horren

abantailak/desabantailak aurreko soluzioarekin erkatuta.

6. Begizta baten 100 iterazio independente exekutatu behar dira, paraleloan, lau prozesadoreren artean. Iterazio bakoitzaren exekuzio-denbora 1 s da, kasu batean izan ezik, 20 s irauten duena. Kalkula itzazu lortuko den azelerazio-faktorea eta eraginkortasuna hiru kasu hauetan:


a. Iterazioen banaketa estatikoa da, ondoz ondokoa (tamaina bereko zatiak). b. Iterazioen banaketa estatikoa da, tartekatua (tamaina bereko zatiak). c. Iterazioen banaketa dinamikoa da, banan-banan (kalkula itzazu kasurik txarrena eta

onena); lanak esleitzeko eragiketa baten kostua, 50 ms.

7. Paraleliza ezazu begizta hau, ahalik eta modurik eraginkorrenean, 40 prozesadoreko makina baterako. Erabil ezazu banaketa estatikoa, ondoz ondokoa. Kalkulatu lortuko den azelerazio-faktorea.

do i = 0, 19 do j = 0, 199 A(i,j) = A(i,j) + 1 B(2*i+1,j) = B(2*i,j) * 2 enddo enddo

8. Hiru dimentsioko begizta jakin batek edozein dimentsiotan paraleliza daiteke sinkronizazioa erabili behar izan gabe. Exekutatu behar da begizta hori 8 prozesadoreko SMP makina batean. Egokiena zera da: a. Barneko begizta paralelizatzea, ale-tamaina handia izan dadin. b. Kanpoko begizta paralelizatzea, prozesadore bakoitzak exekutatuko dituen atazak

handiak izan daitezen. c. Hiru begiztak paralelizatzea, ataza independente asko izateko prozesadoreen artean

banatzeko. d. Seriean exekutatzea, prozesadore gutxi ditugulako 3 dimentsioko begizta baterako. e. Aurreko erantzunak ondo daude, eta soluziorik egokiena multiprozesadorearen

koherentzia-protokoloaren arabera da: baliogabetzekoa edo eguneratzekoa.

9. Begizta-iterazioen banaketa (scheduling) dela eta, esan egiazkoak edo faltsuak diren, eta zergatik, adierazpen hauek: a. Banaketa estatiko tartekatuak ahalbidetzen du lokaltasuna datuak atzitzeko. b. Dependentziak ez dituen (doall) begizta baterako onena zera da: banaketa dinamikoa,

zatien tamaina gero eta txikiagoak izanik. c. Iterazioen exekuzio-denbora antzekoa bada eta dependentziarik ez badago, egokiena

banaketa estatikoa da. d. 100 iterazio 4 prozesadoreen artean exekutatu behar badira, banaketa egokiena

dinamikoa da, zatiak 20 iteraziokoak izanik. e. 100 iterazio 4 prozesadoreen artean exekutatu behar badira eta guided self-scheduling

(geratzen denaren parte proportzionala) erabiltzen bada, lehenbiziko prozesadoreak 25 iterazio exekutatuko ditu, eta agian besteen artean gainerako 75 iterazioak banatuko dira.

10. Begizta baten iterazioak banatzeko, Fetch&Add (i,10) agindua exekutatzen da. Beraz, a. Banaketa estatikoa da, tartekatuta, tartekatze-maila 10 izanik. b. Self-scheduling motako banaketa da. c. Prozesadoreen artean banatzen diren begizta-zatien tamaina 10naka txikiagotzen da

(trapezoid scheduling). d. Banaketa dinamikoa da, tamaina berdineko (10) zatiak erabiliz. e. Aurreko adierazpen guztiak gaizki daude.

11. Begizta hau exekutatu behar da, 4 prozesadoreko SMP batean: do i = 0, 7 kalkulatu(i) enddo

iterazioa: 0 1 2 3 4 5 6 7 denbora: 1 6 20 15 7 13 12 6

a. Iterazioen banaketa estatikoa da, binaka tartekatua. Kalkula itzazu lortuko diren azelerazio-faktorea eta eraginkortasuna Adierazi prozesadore bakoitzak exekutatuko dituen iterazioak.

b. Errepikatu aurrekoa beste banaketa honetarako: self-scheduling. Esleipen-eragiketen kostua 1 da. Zein da gehitutako gainkarga osoa (%a)?

Ariketak: Abiadura handiko konputagailuak. OpenMP, MPI (sarrera). ▪ 57 ▪

9.1. www.top500.org helbidean, konputagailu paralelo azkarrenen zerrenda argitaratzen da, bi urteetan behin. Zerrendan ageri denez, 1993ko konputagailurik azkarrenak 59,7 GF/s-ko kalkulu-abiadura eskuratu zuen; 2009 urtean, azkarrenak 1,105 PF/s-ko kalkulu-abiadura lortu zuen.

Abiaduraren eboluzioa denboran zehar (orain arte, behintzat) Moore-ren legearen arabera doala kontuan harturik, kalkula ezazu (a) zenbat hilabete behar diren konputagailu paraleloen kalkulu-abiadura bikoizteko, eta (b) aurreikus daitekeen konputagailurik azkarrenaren kalkulu-abiadura 2017 urteko zerrendan.

9.2. www.top500.org helbidean, hainbat datu lor daitezke konputagailu azkarrenen ezaugarriei

buruz (statistics atalean). Datu horietan oinarrituta, kalkula itzazu parametro hauek: 1. 500 sistema paralelo horien batez besteko prozesadore kopurua, 2.048tik 8.192raino

prozesadore dituzten sistemen ehunekoa, eta sistema horiekin lortzen den kalkulu-abiadura, batez bestean.

2. Prozesadore bakoitzaren batez besteko kalkulu-abiadura gorena (Rpeak) GF/s-tan, eta benetan lortzen dena (Rmax), GF/s-tan eta maximoaren ehuneko gisa.

3. 500 makina horien bektore-prozesadoreen eta prozesadore eskalarren batez besteko kalkulu-abiadura. Ondorioren bat?

4. MPP eta cluster arkitekturako sistemen batez besteko prozesadore kopurua, eta kalkulu-abiadura maximotik lortzen duten ehunekoa. Ondorioren bat?

5. Konexio-sarea dela eta, Gigabit Ethernet eta Infiniband erabiltzen duten sistemen kopurua (%), eta sistema horien balizko abiadura maximotik lortzen den ehunekoa. Ondorioren bat?

Egin ezazu kalkulu bera, baina Cray Interconnect izeneko sarearekin. Ondorioa? Lor itzazu sare horren ezaugarri nagusiak (topologia, komunikazio-mekanismoak, loturen banda-zabalera, mezu-bideragailuen ezaugarriak...)

9.3. Zer da cluster bat? Donostia International Physics Center-en kalkulua egiteko behar duten

1.024 prozesadoreko (nukleoko) cluster aurreratu bat osatu behar duzu. Azaldu, labur-labur, erabiliko dituzun osagaiak, arkitektura eta abar, eta nola programatuko duzun.

9.4. Aplikazio jakin bat paraleloan exekutatu behar da, hainbat prozesutan banatuta. Hasieran,

prozesu batek sarrera-balio bat eskatzen du. Zer egin behar da gainerako prozesuek ere balio hori jakin dezaten, baldin eta (a) konputagailua SMP motakoa bada; eta (b) konputagailua MPP motakoa bada? Zer egingo dute gainerako prozesuek sarrera-balioa irakurri bitartean?

9.5. Earth Simulator Japoniako bektore-superkonputagailu ospetsua da, 2002-2004 urteetan

top500 zerrendako lehena izandakoa. Makina horren erabiltzaile batek hiru modutan lan egin dezake: (a) bektore-prozesadore bakarra erabiliz; (b) SMP motako nodo bat erabiliz, non 8 bektore-prozesadore dauden; eta (c) SMP nodo batzuk erabiliz, DSM motako makina bat balitz bezala.

Esan, zehatz eta labur, programatzaileak erabiliko dituen programazio-tresna nagusiak modu horietako bakoitzean.

9.6. Mezu-ematea erabiltzen duten komunikazio-sistemak MPI bezalako komunikazio-

funtzioen liburutegiak erabiliz programatu ohi dira, zeinetan bi komunikazio-funtzio bereizi ohi diren: puntutik punturakoak eta kolektiboak edo globalak. Erabil ezazu nahi duzun sintaxia, eta jarri mota bakoitzeko adibide bat.


9.7. Aplikazio bat exekutatzen ari da memoria banatuko sistema paraleloa batean. Une jakin batean, P1 eta P2 prozesuek dat1 eta dat2 datuak trukatu behar dituzte, eta horretarako (sasi)kode hau exekutatzen dute (MPI-ren antzekoa):

P1 P2 … … Bidali_sinkr(P2ra,dat1,…) Bidali_sinkr(P1era,dat2,…) … … … … Hartu_sinkr(P2tik,dat2,…) Hartu_sinkr(P1etik,dat1,…) … …

Zuzena da? Zergatik? Argudiatu erantzuna. 9.8. Lau prozesadoreko memoria banatuko sistema paralelo batean, P0 prozesadoreak lau

osagaiko bektore bat du memorian, eduki honekin: A = [1, 2, 3, 4]. P0k Scatter motako eragiketa bat egiten du A bektorearekin. Gero, prozesadore guztiek gehitu (+1) egiten dute harturiko informazioa. Azkenik, bi eragiketa hauek exekutatzen dituzte prozesadore guztiek (helburua P0 da): (1) A bektorearen Gather bat, eta (2) B = Reduce(A,+) motako eragiketa.

Adierazi A eta B aldagaien azken balioak P0 prozesadorean. 9.9. Memoria banatuko makina batean exekutatu den aplikazio jakin batean, A aldagaien

erredukzioa exekutatu da, B-ren gainean: MPI_Reduce(A,B,MPI_SUM,...). Aplikazioa memoria partekatuko makina batean exekutatu beharko balitz, nola egingo genuke eragiketa hori? Idatzi kodea.

9.10. a. OpenMP-ko kode zati hau paraleloan exekutatu da SMP motako makina batean, baina

ez du ondo funtzionatu. Zergatik? Nola konpondu behar da?

#pragma omp parallel for shared(A,B,C,sum) private(i) for (i=0; i<N; i++) { C[i] = A[i] + B[i+1]; sum = sum + C[i]; } ...

b. MPI-ko kode zati hau paraleloan exekutatu da memoria banatuko cluster batean, eta ez du ondo funtzionatu. Zergatik? Nola konpondu behar da?

if (pid == 0) then { scanf (“%f”, &C); MPI_Bcast(&C, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD); } B = B + C; ...

9.11. Cluster batek 32 nodo ditu, eta nodo bakoitzak 8 nukleo edo core. Nodoetako 8 nukleoek

bertako memoria partekatzen dute, baina nodoetako memoria pribatua da. a. Esan zein APIk erabiliko zenituzke makina horretan aplikazio paraleloak sortzeko. b. Kode zati hau exekutatu behar da makina horretan:

… printf("\n Idatzi K --> "); scanf("%d",&K); for (i=0; i<N; i++){ X = X + f(i,K) } printf("\n X = ", X); …

Berridatzi kode hori paraleloan, nodo bakar bateko nukleoen artean exekutatzeko. c. Errepikatu aurrekoa baina nodoen artean, paraleloan, exekutatu ahal izateko.

Ariketa orokorrak ▪ 59 ▪

10.1. Begizta hau bektore-prozesadore batean eta konputagailu paralelo batean exekutatu behar da:

k = 3 do i = 2, N+1 (1) A(i) = B(i-2) * A(i) (4 ziklo) (2) B(k) = B(i) / 4 (3 ziklo) (3) C(i) = E(i-1) - 1 (3 ziklo) (4) D(2*k-1) = A(i-1) + C(i) + A(k+3) (6 ziklo) (5) E(i) = C(i+1) (2 ziklo) k = k + 1 enddo

a. Analiza itzazu aginduen arteko dependentziak, eta marraztu dependentzia-grafoa.

b. Dependentzia-grafoan oinarrituta, adieraz ezazu begizta bektoriza daitekeen eta nola. Egin badaiteke, dena edo zati bat, idatz ezazu dagokion bektore-kodea.

Bektore-konputagailuak memoria atzitzeko hiru bus ditu eta ez dago gatazkarik memoria-moduluak erabiltzerakoan; aginduak kateatu egin daitezke, eta unitate funtzional asko dago. Datu horiek kontuan hartuz, balioetsi zenbat bider azkarrago exekutatuko den begizta bektore-konputagailuan prozesadore eskalarrean baino (speed-up). Begiztan bertan adierazten dira aginduen exekuzio-denborak (ziklotan) prozesadore eskalarrean.

c. Gero, analiza ezazu nola paraleliza daitekeen begizta ahalik eta modurik eraginkorrenean. Idatzi kodea goi mailan, eta, beharrezkoa bada, erabili gertaera-bektoreak sinkronizaziorako. Ezinbesteko kasuetan bakarrik erabili behar da sinkronizazioa; edozein teknika erabil daiteke sinkronizazioaren beharra minimizatzeko: fisioa, peeling, trukea...

Konputagailu paraleloak 16 prozesadore ditu. Berridatzi begizta paraleloa(k), baina orain gehitu dagokien banaketa (scheduling). Adibide jakin horietarako zure ustez emaitzarik onenak emango dituzten banaketa-metodoak erabili behar dituzu.

Azkenik, balioetsi zenbat bider azkarragoa izango den exekuzioa sistema paraleloan prozesadore bakarrekoan baino. Kalkuluak egiteko, kontuan hartu 6 ziklo sinkronizazio-eragiketa bakoitzeko.

10.2. Algoritmo hau memoria partekatuko sistema batean exekutatu behar da, paraleloan:

... printf(“Sartu X-ren balioa”); scanf (“%d”, &X);

sarrera

for (i=0; i<N; i++) A[i] = A[i-1] * X;

for (i=0; i<N; i++) B[i] = B[i] * A[i] + X;

min = MAXINT; for (i=0; i<N; i++) if (B[i]<min) min = B[i];

for (i=0; i<N; i++) B[i] = B[i] – min;

kalkulua

for (i=0; i<N; i++) printf(“%d \n”, B[i]); ...

irteera

a. Idatz ezazu prozesadore bakoitzak exekutatuko duen kodea (goi-maila, SPMD eredua). Erabil itzazu nahi dituzun sinkronizazio-funtzioak (lock, barrier, wait…). Begiztak paraleloan exekutatu behar badira, erabil ezazu banaketa estatikoa, ondoz ondoko zatiak banatzen dituena. Prozesuek aldagai pribatu bana erabiltzen dute identifikadore gisa: pid (0tik P–1era). Adierazi, argi eta garbi, aldagaien izaera: pribatuak edo partekatuak.

b. P prozesadoreko makina batean exekutatu behar da kodea. Begiztetako goi-mailako aginduen exekuzio-denbora antzekoa da, eta, beraz, N iterazioko begizta bakoitzaren


exekuzio-denbora N gisa modela daiteke. Bestalde, sinkronizazio-eragiketa baten exekuzio-denbora P gisa modela daiteke.

Kalkula ezazu (hurbilpen bat) lortuko den azelerazio-faktorea (sarrera/irteera eragiketak kontuan hartu gabe). Marraztu azelerazio-faktorea P-ren arabera N = 1.024 kasurako eta kalkula ezazu balio maximoa. Zein izango da azelerazio-faktorea P = 4 kasurako? eta P = 32 kasurako? Nola ulertu behar dira emaitzak?

c1. Kodea exekutatu duen makina 4 prozesadoreko SMP bat da, eta lau prozesadoreek X aldagaia erabiliko dute. Adierazi X aldagaia duen datu-blokearen egoeraren eboluzioa prozesadoreen cacheetan; koherentzia MESI motako zelatari baten bidez ziurtatzen da.

c2. Demagun makina paraleloa 32 prozesadoreko cc-NUMA bat dela, eta koherentzia-protokoloa SCI dela. Errepikatu (c1) ataleko analisia eta adierazi nola eratuko den kopien zerrenda (egoerak Home nodoan eta cacheetan) X aldagaiaren lehenengo 4 kopietarako (P0, P6, P2, eta P29 prozesadorekoak hain zuzen ere; X-ren memoria-posizioa P0ri dagokio).

c3. Errepikatu aurrekoa, Origin makinetako koherentzia-protokoloa duen makina baterako.

10.3. Memoria pribatuko konputagailu batek 64 prozesadore ditu; komunikazio-sarea bi

dimentsioko toru bat da, eta sareko loturak 4 Gbit/s-koak dira. Sareko bideragailuek 5 ns behar dute paketeak prozesatzeko. Paketeak 1+31 bytekoak (= flit-ekoak) dira.

a. Prozesu batek pakete bat bidaltzen du distantzia maximora dagoen prozesadore batera. Kalkula ezazu paketearen transmisio-denbora sarean; komunikazioa cut-through moduan egiten da.

Makina horretan exekutatzen den aplikazioetako bat soilik alboetan dituen nodoekin (probabilitatea = 0,7) eta distantzia maximora dauden nodoekin (probabilitatea = 0,3) komunikatzen da. Kalkula ezazu aplikazio horren paketeek zeharkatzen duten distantzia, batez bestean.

Azkenik, kalkula ezazu sare horrek kudea dezakeen pakete kopuru maximoa, trafikoa zorizkoa denean (espazioan eta denboran).

b1. Honako funtzio hau exekutatu behar da aurreko makinan:

double fun(){ int i, bekl; double emaitza, batura=0.0;

printf("\n Bekt_luz? "); scanf("%d", &bekl);

for (i=0; i<bekl; i++) batura = batura + A[i]*A[i]/(A[i]+2.5);

emaitza = sqrt(batura) / bekl; return emaitza; }

Nodo bakoitzaren memoria pribatua denez, aldagai guztiak pribatuak dira eta komunikazioa mezu-ematearen bidezko eragiketa esplizituen bidez egin behar da. Bi prozesuen arteko komunikazioa betetzeko, batak BIDALI(dat_helb, elem_kop, helburua) funtzioa, eta besteak HARTU(dat_helb, elem_kop, iturburua) funtzioa exekutatu behar dute.

Prozesu batek (esaterako, pid=0-k) bektorearen luzera irakurri behar du; gero, A bektorearen zati bana bidaliko die gainerako prozesuei, banan-banan. Ondoren, dagozkien datuak prozesatuko dituzte prozesu horiek, eta, bukatutakoan, emaitza partzialak pid=0 prozesuari bidaliko dizkiote, azken emaitza kalkula dezan. Laburbilduz: prozesu batek datuak banatzen ditu eta emaitzak biltzen ditu, eta gainerakoek kalkulua egiten dute. Hauxe izan daiteke aurreko algoritmoa paraleloan exekutatzeko kodea:


double fun()

{ int i, bekl, pkop=64; double emaitza, batura=0.0, bat_lag=0.0; if (pid==0) { // P0 printf("\n bekt_luz? "); // bektore-tamaina irakurri scanf("%d", &bekl);

tam = bekl / (pkop - 1); // bektore zatien tamaina // bidali bektore zatiak, banan-banan for (i=1; i<pkop; i++) BIDALI(&A[tam*(i-1)],tam,i); } else HARTU(A, tam, 0); // zain dadude datuak hartzeko

HESIA(pkop); // sinkr. globlala, kalkulua baino lehen

if (pid==0) { // P0k biltzen ditu emaitza partzialak batura = bat_lag; for (i=1; i<pkop; i++){ HARTU (&bat_lag, 1, i);

batura = batura + bat_lag; } emaitza = sqrt(batura) / bekl; // azken kalkulua return (emaitza); } else { for (i=0; i<tam; i++) // kalkulu lokala bat_lag = bat_lag + A[i]*A[i] / (A[i]+2.5);

BIDALI(&bat_lag, 1, 0); // bidali emaitza partzialak P0ra } }

Kalkula ezazu lortuko den azelerazio-faktorea (speed-up) programa hori

multikonputagailua 64 prozesadoreetan exekutatzen denean; A bektoreak 63×105 osagai ditu. Kalkuluak errazteko, kontuan hartu honako exekuzio-denbora hauek: kalkuluko for begiztaren iterazio bat, 500 ns; <BIDALI / HARTU> komunikazio-eragiketa bat, 10.000 + + 2×L ns; sinkronizazio globaleko eragiketa bat, 6.000 ns.

b2. Beharrezkoa da aurreko kodean HESIA sinkronizazio globaleko funtzioa? Hori gabe, zer irabaziko edo galduko genuke? Erantzuna arrazoitzeko, erabil ezazu grafiko bat, non ikusiko den nola betetzen diren kalkulua eta komunikazioa, denboran zehar, prozesuen artean (adib., 5(1+4) prozesadoreko kasuan).

b3. Dakizunez, SMP sistema baterako hesi bat sortzeko, nahikoa da adierazle bat eta kontagailu bat erabiltzea. Baina, nola gauzatuko zenuke sinkronizazio-hesi bat memoria pribatuko sistema batean? Egin ezazu "zirriborro" bat.

c. Konputagailu-eredua aldatuko dugu; hasierako for begizta 8 prozesadoreko SMP

multiprozesadore batean (memoria partekatua, bus bat) exekutatu behar da. Idatz ezazu exekutatu behar den kodea kalkulua paraleloan egin ahal izateko. Erabil itzazu behar dituzun sinkronizazio-funtzioak eta aldagaiak; hala ere, adierazi, argi eta garbi, aldagaien izaera: partekatuak edo pribatuak.

d. Kalkulua paraleloan egiteko, begizta zatiak banatzen dira prozesuen artean, eta,

horretarako, scheduling edo banaketa-estrategia jakin bat erabili da aurreko programetan. Zer scheduling mota erabili da (b) ataleko programan? Kontuan hartu (c) atalean egin duzun memoria partekatuko programa eta berridatzi begiztaren banaketa "beste estrategia mota" erabiliz (nahi duzun bertsioan). Zure ustez, zein da banaketa-estrategiarik egokiena kasu horretan? Zergatik?


10.4. Dakizunez, funtzio baten integrala kalkulatzeko, hau da, kurba (funtzio) azpiko area lortzeko, hainbat poligono txikiren areak batu daitezke:

delta_x = (b – a) / N; x = a; for (i=0; i<N; i++){ A = A + f(x); x = x + delta_x; } A = A * delta_x;

xxfdxxfAN

ii

b

a∑∫−

=

∆≅=1

0

)()(

Zenbat eta zati gehiago egin (N) hainbat eta handiagoa izango da emaitzaren doitasuna, nahiz eta exekuzio-denbora luzea izan daitekeen, N-rekiko proportzionala baita. Zorionez, kalkulu hori oso erraz exekuta daiteke paraleloan, P prozesadore erabiliz.

a. Idatz ezazu SMP konputagailu baten P prozesadoreek aurreko eragiketa egiteko exekutatu behar duten kodea. Har itzazu nahi dituzun erabakiak, baina azaldu ezazu zergatia.

b. Prozesu paraleloek gainkarga bat dakartzate (hariak sortzea, sinkronizazioa...); adibide honetan, honela adieraz daiteke gainkarga hori: Tover = 200 + 10×P µs.

Programa paraleloaren eraginkortasuna kalkuluak behar duen denboraren araberakoa da, Tkalk (µs). Lor ezazu jatorrizko programaren kalkulu-denbora minimoa, P-ren arabera, programa paraleloaren eraginkortasuna gutxienez % 50 izan dadin. Kalkulatu denbora hori P = 20 kasurako.

c. Demagun Tkalk = 105 µs dela. Irudika ezazu grafiko batean (grosso modo) azelerazio-faktorearen portaera prozesadore kopuruaren arabera, eta kalkula ezazu erabili beharko genukeen prozesadore kopurua emaitzarik onena (exekuzio-denbora txikiena) lortzeko. Zein da denbora hori, eta zein da lortu den azelerazio-faktorea?

10.5. Aplikazio jakin bat exekutatu behar da lau nodoko SMP makina batean, lau prozesutan

banatuta. Prozesuek Datuak_Sortu(VA) funtzioa exekutatzen dute, N datu sortu eta VA bektorean uzteko; eta gero, gailu jakin batean idazten dituzte datu horiek Datuak_Idatzi(VA,helb) funtzioaren bidez. Helb aldagaiak datu berriak non idatzi behar diren adierazten du. Prozesu bakar bat onartzen da aldi berean datuak idazten.

a. Idatz ezazu eragiketa hori exekutatzen duen kodea, SPMD motakoa eta ahalik eta eraginkorrena; prozesu guztien artean K datu idatzi behar dira (N×4-ren multiploa). Har itzazu nahi dituzun erabaki guztiak, baina azaldu zergatia eta erabiltzen dituzun aldagaiak (pribatuak edo partekatuak).

Sinkronizazio-funtzioak erabili behar badituzu, idatzi, gero, dagokien kodea (makina-mailan), LL eta SC aginduak erabiliz.

b. Errepikatu aurrekoa, baina baldintza hau kontuan hartuz: lau prozesuek ordena hertsian idatzi behar dituzte datuak (P0, P1, P2, P3, P0, P1…).

c. Datuak sortzen dituen funtzioak 300 ms edo irauten du, eta idazten dituenak 30 ms. Kalkula ezazu lortuko den azelerazio-faktorea, prozesadore bakarreko kasuarekin alderatuta, (1) 2 prozesadore erabiliz; eta (2) 4 prozesadoreak erabiliz. Demagun <datuak sortu / idatzi> prozesua 1.000 aldiz errepikatzen dela.

d. Errepikatu aurrekoa, baina datu hau kontuan hartuz: idazketak 200 ms irauten du. Argudiatu lortuko dituzun emaitzak.

a b Δx

f


10.6. a. Programak paraleloan exekutatzen direnean, P prozesadore erabiliz, helburu nagusia zera da: exekuzio-denbora P aldiz txikiagoa izatea, hau da, programa P aldiz azkarrago exekutatzea. Zoritxarrez, kasurik gehienetan ez gara helburu teoriko horretara hurbilduko, eta azelerazio-faktoreak P baino txikiagoak izango dira. Azaldu itzazu, zehatz-mehatz, exekuzio paraleloen eraginkortasunaren galera justifikatzen duten lau arrazoi nagusiak.

b. Azter dezagun kasu jakin bat. Aplikazio bat 16 prozesadoretan exekutatu nahi da. Aplikazioaren hasieran, prozesu batek irakurri egiten ditu datuak, eta, bukaeran, emaitzak diskoan idatzi egiten ditu.

Exekuzioaren eraginkortasunak gutxienez % 85 izan behar badu, eta besterik kontuan hartu gabe, zein da sarrera/irteerako prozesu horiek iraun dezaketen denbora maximoa (aplikazioaren exekuzio-denbora osoaren ehunekoa)?

c. Aurreko aplikazioan, exekuzio-denboraren % 2 sarrera/irteerako eragiketetan xahutzen da. Gainerakoa, paraleloan exekutatzen da, P prozesadoretan. Exekuzio paraleloan zehar, broadcast motako eragiketak egiten dira, prozesadore batetik gainerakoetara, serieko denborako milisegundo bakoitzean behin, eta honela modelatu da komunikazio horien kostua: 20 + 4 × P1/2 mikrosegundo.

Marraztu grafiko batean azelerazio-faktorearen eboluzioa prozesadore kopuruaren arabera, balio hauetarako: P = 5, 10, 20, 40, 60, 80, 100 eta 120. Kalkula itzazu prozesadore kopuru egokiena eta kasu horretan lortuko liratekeen azelerazio-faktorea eta eraginkortasuna.

d. Aurreko aplikazioa 4×4 prozesadoreko maila batean exekutatu behar da. Broadcast eragiketa honela exekutatzen da. Broadcast egiten duen prozesadoreak pakete bana bidaltzen die auzoei; gero, pakete hori birbidaltzen da, sarean zehar, modu honetan.

- BC motako paketea X ardatzetik heldu bada, X ardatzetik birbidaltzen da. - BC motako paketea Y ardatzetik heldu bada, Y ardatzetik birbidaltzen da, baita X

ardatzeko bi noranzkoetan ere. BC motako pakete bat nodo batetik hurrengora bidaltzeko, 200 ns behar dira; gero,

birbidali behar diren paketeak sortzeko, beste 50 ns behar dira. Marraz ezazu, 4×4 maila batean, nola gauzatuko den broadcast eragiketa (2, 1) nodotik

abiatuta. Kalkula ezazu broadcast eragiketaren exekuzio-denbora eragiketa sortzen duen prozesadoreak mailan okupatzen duen posizioaren arabera.

Komunikazioa gauzatzeko erabilitako algoritmoaren latentzia distantzia maximoarekin erlazionatuta dago. Maila batean, distantzia maximoa desberdina da nodoen posizioen arabera, sarea simetrikoa ez baita. Kalkula ezazu nodo bakoitzaren distantzia maximoen batez bestekoa 4×4 tamainako maila batean.

10.7. Memoria partekatuko multiprozesadore batek 64 prozesadore ditu, hiperkubo batez lotuta.

Prozesadore bakoitzak 2 GB-ko memoria nagusia eta 1 MB-ko cache memoria ditu, eta datu-blokeak 128 bytekoak dira. Datuen koherentzia mantentzeko, cacheetan banatuko direktorio bat erabiltzen da (SCI).

Une jakin batean, P7 prozesadoreak idatzi egiten du cachean ez duen aldagai batean; aldagaiaren helbidea P32ri esleitutako memoria-espaziokoa da. Bloke horren bi kopia daude cacheetan: P24 (Head–Fresh) eta P56 (Tail–Valid) prozesadoreetan.

a. Kalkula ezazu koherentzia-informazioak nodo bakoitzean behar duen memoria-espazioa.

Blokeen egoerak adierazteko, MNan 2 bit eta cacheetan 6 bit erabiltzen dira.

b. Adieraz ezazu, ahalik eta zehatzen, P7ren cacheko hutsegitea nola konpontzen den; azaldu, argi eta garbi, bidaltzen diren mezuak, nondik nora, haien edukia, eta egoeren aldaketak.


c. Kalkula ezazu P7tik direktoriora doan lehen paketea nondik igaroko den. Bideratzea DOR motakoa da, dimentsio "handienetik" "txikienera". Mezu horretarako, kalkulatu zenbat bide (minimo) desberdin erabil zitezkeen, bideratzea moldakorra balitz, iturburutik helburura heltzeko.

d. Kalkula ezazu P7ko eragiketa bukatzeko behar den denbora. Kalkulua egiteko, erabil itzazu datu hauek: komunikazio-modua: cut-through; sareko loturak eta paketeen flit-a: 1 byte; transmisio-abiadura: 4 Gbit/s; prozesatze-denbora mezu-bideragailuetan: 5 ns; paketeen luzera: 132 byte (datu-blokea), edo 4 byte (kontrola); mezuei erantzuna emateko denbora helburuetan: 250 ns; ez dago trafikorik sarean.

e. Demagun sarea ez dagoela hutsik: nodo bakoitzak 200 MB ari da injektatzen sarean segundoko. Lehenik eta behin, kalkula ezazu prozesadore bakoitzak sor dezakeen trafiko maximoa (zorizkoa) MB/s-tan sarea ase gabe, eta, ondorioz, prozesadore bakoitzak injektatzen ari den trafiko maximo horren ehunekoa. Grafikoan, paketeen latentzia trafikoaren arabera nola hazten den ageri da. Hortik, kalkula ezazu komunikazio-denboran izango den gehikuntza trafikoa dela eta, eta, azkenik, P7ko eragiketaren denbora.

100

200

300

400

500

600

0 10 20 30 40 50

Lat

entz

ia (n

s)

Trafikoa (maximoaren ehunekoa)

ariketak - gipuzkoa€¦ · parametroak; etaexekuzi o-denbora eta kalkulu-abiadura, bektoreak (eta...

Documents