Arkitektura Paraleloak

Arkitektura Paraleloak IF - EHU

Arkitektura Paraleloak

4. Prozesuen Sinkronizazioa SMP Konputagailuetan

- Sarrera- Elkarrekiko esklusioa- Gertaeren bidezko sinkronizazioa- Sinkronizazio-hesiak

Arkitektura ParaleloakIF - EHU

P. Sink. 24

SMP konputagailuetako memoria partekatua da, eta prozesuak aldagai partekatuen bidez komunikatzen dira.

...FST A(R0),F2...

...FLD F4,A(R0)...

Pi Pj

?

Aplikazio gehienetan, aldagai horien erabilera sinkronizatu egin behar da, programaren esanahia zehatza izan dadin. Adibidez:

Sarrera

Arkitektura ParaleloakIF - EHU

P. Sink. 34

Eta zer gertatuko da kasu honetan (KONT =

0)?

...LD R1,KONTADDI R1,R1,#1ST KONT,R1...

Pi...LD R1,KONTADDI R1,R1,#1ST KONT,R1...

Pj

LD..ADDI.......ST

LD....ADDI.....ST KONT = 1 !!

Sarrera

Arkitektura ParaleloakIF - EHU

P. Sink. 44

Memoriako atzipen atomikoak (interferentziarik gabekoak) behar ditugu prozesuak sinkronizatu ahal izateko.

Bi motako beharrak:

- sekzio kritikoakelkarrekiko esklusioan exekutatu behar diren kode zatiak (prozesu bakar bat aldi berean).

- gertaeren bidezko sinkronizazioapuntutik puntura → gertaerak (ekoizle/kontsumitzaile)

globala → hesiak

Sarrera

Arkitektura ParaleloakIF - EHU

P. Sink. 54

Prozesuak zain geratuko dira zerbait gertatu arte; hau da, denbora galdu egingo da.

Sinkronizazio-mekanismoen ezaugarriak:

- latentzia txikia- trafiko

mugatua

- hedagarritasun ona- memoriako kostu

txikia- zuzentasuna

Denbora-tarte bat itxaroteko:-- itxarote aktiboa-- blokeoa

Sarrera

Arkitektura ParaleloakIF - EHU

P. Sink. 64

Ez da prozesadore bat baino gehiago onartzen, aldi berean, kode zati jakin bat (sekzio kritikoa) exekutatzen.

Sekzio kritikoaren exekuzioa kontrolatzeko:

- sarrailak: 0, irekita - 1, itxita- lock - unlock funtzioak:

lock(SAR) aztertu sarraila; irekita badago, itxi eta igaro

sekzio kritikoa exekutatzera;

bestela, zain geratu sarraila ireki arte.

unlock(SAR) ireki sarraila.

Elkarrekiko esklusioa

Arkitektura ParaleloakIF - EHU

P. Sink. 74

lock: LD R1,SARBNZ R1,lock

ADDI R2,R0,#1ST SAR,R2

RET

...

kont ++ ;

...

sekzio kritikoa

unlock: ST SAR,R0RET

RMW motako agindu atomikoak behar ditugu.

unlock(SAR);

lock(SAR);

?

Elkarrekiko esklusioa

Arkitektura ParaleloakIF - EHU

P. Sink. 84

1.1 Test&Set

▪ T&S R1,SAR R1 := MEM[SAR]; MEM[SAR] := 1;

lock: T&S R1,SARBNZ R1,lockRET

unlock: ST SAR,R0 RET

T&S - Swap

Arkitektura ParaleloakIF - EHU

P. Sink. 94

1.2 Swap

▪ SWAP R1,SAR

R1 <--> MEM[SAR];

lock: ADDI R1,R0,#1

l1: SWAP R1,SARBNZ R1,l1RET

unlock: ST SAR,R0 RET

T&S - Swap

Arkitektura ParaleloakIF - EHU

P. Sink. 104

SMP sistemetan, biziki garrantzitsua da ahalik eta trafiko gutxien sortzea. ADI: sarraila –SAR– aldagai partekatua da.

Trafikoa

T&S aginduak beti idazten du sarrailan, itxita dagoenean ere; beraz, sarraila duen datu-blokea baliogabetu egin behar da, behin eta berriz.

Ondorioz, datu-trafiko asko sortuko da prozesuak sekzio kritikoan sartzeko zain dauden bitartean, sarrailaren datu-blokea transmititzen.

T&S - Swap

Arkitektura ParaleloakIF - EHU

P. Sink. 114

TS/INV]

S=0,INVP0

P1 ?

P2 ?

P3 ?

P4 ?

TS/INV]

P0 SKan dago BRQ = blokea eskatu / x = baliogabetuta / bus-kontrola = FIFO

x BRQ.......

x BRQ.........

x BRQ...

behin eta berriz!

SK

x

x

x

x [TS BRQ

[TS BRQ..........

[TS BRQ...................

[TS BRQ............................

[TS..

TS/INV][TS..

TS/INV][TS...

TS/INV][TS..

T&S – Swap: trafikoa

x

Arkitektura ParaleloakIF - EHU

P. Sink. 124

1 Test&Set with backoff

Hobekuntzak trafikoa murrizteko

lock: T&S R1,SARBNZ R1,zain

RET

zain: CALL ITXOIN[egokitu itx-denb.]JMP lock

Sarraila itxita badago, ez saiatu behin eta berriz sartzen: utzi denbora tarte bat berriro ere saiatu baino lehen.

Itxarote-denbora esponentziala izatea egokia ohi da:

t0 = k; t1 = k × c; t2 = k × c2; ...

T&S with backoff

Arkitektura ParaleloakIF - EHU

P. Sink. 134

2 Test-and-Test&Set prozedura

Hobekuntzak trafikoa murrizteko

lock: LD R1,SARBNZ R1,lock

T&S R1,SARBNZ R1,lock

RET

Banatu lock eragiketa bi zatitan:

a. irakurri sarraila irekita aurkitu arte (LD);

b. eta, orduan, saiatu sarraila modu atomikoan ixten (T&S).

Test-and-Test&Set

Arkitektura ParaleloakIF - EHU

P. Sink. 144

LD[TS.......

S=0,INVP0

P1 LD

P2 LD

P3 LD

P4 LD

x

TS/INV][LD..

TS/INV][LD..

TS/INV]

LD.........

LD......

LD...

x

x

x

x

BRQ

BRQ...........

BRQ.......

BRQ...

SK

Datu-trafikoa (datu-blokeak)prozesu bat SKra sartzeko → P + (P-1) + (P-2)SKtik ateratzeko → 1

guztira → 3P - 2 P proz. → P(3P-1)/2

TS/INV]

LD[TS.......

LD[TS...

LD[TS.

x BRQ

x BRQ........

x BRQ...............

x BRQ.....

x BRQ.

Test-and-T&S: trafikoa

P0 SKan dago BRQ = blokea eskatu / x = baliogabetuta / bus-kontrola = FIFO

Arkitektura ParaleloakIF - EHU

P. Sink. 154

2.1 Load Locked / Store Conditional

▪ LL R1,SAR R1 := MEM[SAR]; SinL[helb] := SAR; SinL[adi] := 1;

- eragiketa atomikoa bi zatitan banatu- hardwareko adierazle bat atomikotasuna

bermatzeko

▪ SC SAR,R1baldin (SinL[helb,adi] = SAR,1)

MEM[SAR] := R1; SinL[adi] := 0; proz. guztietan

(INV);R1 := 1; (idatzi da)

bestela R1 := 0; (ez da idatzi)

LL – SC

Arkitektura ParaleloakIF - EHU

P. Sink. 164

lock: ADDI R2,R0,#1l1: LL R1,SAR

BNZ R1,l1...SC SAR,R2BZ R2,lockRET

unlock: ST SAR,R0RET

2.1 Load Locked / Store Conditional

behin bakarrik sortzen da trafikoa: sekzio kritikora sartzean; gainerako kasuetan, ez da idazten!

LL – SC

Arkitektura ParaleloakIF - EHU

P. Sink. 174

LL(1)[SC....

S=0,INVP0

P1 LL

P2 LL

P3 LL

P4 LL

SC] LL............

SC] LL.......

SC] LL.....

x

x

x

x

BRQ

BRQ............

BRQ........

BRQ.....

Datu-trafikoa (datu-blokeak)prozesu bat SKra sartzeko → P + (P-1) SKtik ateratzeko → 0

guztira → 2P - 1 P proz. → P2

SKSC /INV]

LL(1)[SC......

LL(1)[SC..

LL(1)[SC.

(0)x BRQ

(0)x BRQ....

(0)x BRQ.........

LL – SC: trafikoa

P0 SKan dago BRQ = blokea eskatu / x = baliogabetuta / bus-kontrola = FIFO

Arkitektura ParaleloakIF - EHU

P. Sink. 184

2.2 Compare&Swap

▪ C&S R1,R2,SAR baldin (R1 = MEM[SAR])

MEM[SAR] <--> R2;

lock: ADDI R2,R0,#1

l1: C&S R0,R2,SARBNZ R2,l1RET

C&S

Arkitektura ParaleloakIF - EHU

P. Sink. 194

3 Fetch&OpRMW motako agindu-familia bat, eragiketa jakin sinple batzuk atomikoki egiteko; ohikoenak:

▪ Fetch&Incr R1,ALD (edo Fetch&Dcr)R1 := MEM[ALD]; MEM[ALD] := MEM[ALD] + 1;

▪ Fetch&Add R1,R2,ALD R1 := MEM[ALD]; MEM[ALD] := MEM[ALD] + R2;

Fetch&OP

Arkitektura ParaleloakIF - EHU

P. Sink. 204

1 Txartelak (tickets)

Hobekuntzak trafikoa murrizteko

F&I R1,TXARTELA

tx: LL R1,TXARTELAADDI R2,R1,#1SC TXARTELA,R2BZ R2,tx

Ideia: sekzio kritikorako sarrerak ordenatzea. Sarrailaren ordez, bi sinkronizazio-aldagai: txanda (nori dagokio SKra sartzea) eta txartela (zure txanda-zenbakia).

Aurrena, txartela eskuratu, eta gero zain geratu txanda heldu arte.

Txartelak

> Txartela lortzeko:

Arkitektura ParaleloakIF - EHU

P. Sink. 214

1 Txartelak: lock eta unlock funtzioak

Hobekuntzak trafikoa murrizteko

lock: F&I R1,TXARTELA

itx: LD R2,TXANDASUB R3,R1,R2BNZ R3,itx

RET

unlock: LD R1,TXANDAADDI R1,R1,#1ST TXANDA,R1

RET

Trafikoa: - txartela eskuratzen denean- txanda aldagaia eguneratzen denean

adi: balizko gainezkatzeak!

Txartelak

Arkitektura ParaleloakIF - EHU

P. Sink. 224

2 Sarraila-bektoreak

Hobekuntzak trafikoa murrizteko

SKan dagoen proz.INDIZEA: itxaroteko hurrengo posizioa

Ez erabili TXANDA aldagai partekatua, baizik eta sarraila pribatu bat prozesu bakoitzeko.Prozesu bakoitzak hurrengoari abisatzen dio.

Sarraila-bektoreak

1 1 0 1 1 1 1 1SB

0 i i+1

3 prozesu zain daude

01

Arkitektura ParaleloakIF - EHU

P. Sink. 234

2 Sarraila-bektoreak

Hobekuntzak trafikoa murrizteko

lock: F&I R1,INDIZEA

itx: LD R2,SB(R1)BNZ R2,itx

ST NIRE_IND,R1

RET

unlock: ADDI R2,R0,#1

LD R1,NIRE_INDnirea itxi: ST SB(R1),R2

ADDI R1,R1,#1hurr. ireki: ST SB(R1),R0

RET

Trafikoa: behin bakarrik, sarraila-bektoreko osagaiak eguneratzean (adi! partekatze faltsua eta balizko gainezkatzeak).

Sarraila-bektoreak

Arkitektura ParaleloakIF - EHU

P. Sink. 244

LD

TX++,INVP0

P1 LD

P2 LD

P3 LD

P4 LD

LD.......

LD...

LD...

x

x

x

x

BRQ

BRQ............

BRQ.........

BRQ.....

SK

Datu-trafikoa (datu-blokeak)Txartelak → 1 + P → P(P+3)/2Sarraila-bektoreak → 1 + 1 + 1 → 3P

SB(i+1)=0,INVP0

P1 LD..

P2 LD....

P3 LD....

P4 LD....

LDx BRQSK

Trafikoa

P0 SKan dago BRQ = blokea eskatu / x = baliogabetuta / bus-kontrola = FIFO

Txartela/Txanda Sarraila-bektoreak

Arkitektura ParaleloakIF - EHU

P. Sink. 254

Sekzio kritikora sartzeko trafikoa (8 prozesadoreko SMP bat; kasurik txarrena: P = 7 prozesadore sekzio kritikora sartzeko zain daude.)

T&S (mugatugabea)

Test-and-Test&Set P(3P-1)/2 70 bloke

LL - SC P2 49 blokeTxartelak P(P+3)/2 35 blokeSarraila-bektoreak 3P 21 bloke

Laburpena

Arkitektura ParaleloakIF - EHU

P. Sink. 264

1 Puntutik punturako sinkronizazioa gertaeren bidezOhiko sinkronizazioa ekoizlearen eta kontsumitzaile-aren artean, adierazle edo flag baten bidez.

P1 (ekoizlea) P2 (kontsumitzailea)

X = F1(Z);Y = F2(X);

post(adi); wait(adi);

while (adi == 0) {};adi = 1;

post(adi,i); wait(adi,i);

Gertaerak

Arkitektura ParaleloakIF - EHU

P. Sink. 274

2 Hesien bidezko sinkronizazioa

Hesia antolatzeko datu-egitura:struct hesi_egitura{

int sar ; SKaren sarraila

int kont ; zenbat heldu diren

int egoera ; 0 itxita - 1 irekita}

Sinkronizazio globala: prozesu multzo bat sinkronizatzen da exekuzioarekin jarraitu baino lehen.

Hesiak

H

H

H

H

HH

H

H

Arkitektura ParaleloakIF - EHU

P. Sink. 284

Hesi sinple bat (H, hesi_egitura motako struct bat)

HESIA (H,P){

LOCK (H.sar);if (H.kont == 0) H.egoera = 0;H.kont++;nire_kont = H.kont;

UNLOCK (H.sar);

if (nire_kont == P) {H.kont = 0;H.egoera = 1;

}else while (H.egoera == 0) {};

}

Aurrenak hesia itxi behar du; azkenak, ireki.

Hesiak

Arkitektura ParaleloakIF - EHU

P. Sink. 294

Hesi berrerabilgarria. “Hesia irekita” adieratzen duen balioa ez da beti bera: bi balioren artean txandakatzen da.

HESIA (H,P){

irt_bal = !(irt_bal);LOCK (H.sar);

H.kont++;nire_kont = H.kont;

UNLOCK (H.sar);

if (nire_kont == P) {H.kont = 0;H.egoera = irt_bal;

}else while (H.egoera != irt_bal);

}

Hesiak

aldagai pribatua

Arkitektura ParaleloakIF - EHU

P. Sink. 304

Eraginkortasuna: datu-trafikoaPartekatze faltsua saihesteko, demagun sar, kont eta egoera aldagaiak datu-bloke desberdinetan daudela. P prozesuko hesi batean, honako datu-bloke hauek eskatuko ditu Pi prozesadoreak:- sar aldagai duena, lock funtzioa

exekutatzean.- kont aldagaiarena, gehitu ahal izateko.- egoera aldagaiarena, bitan, itxarote-

begiztaren hasieran eta bukaeran.

>> guztira, 4P (hesian sartzeko lehiarik gabe)

Hesiak

Arkitektura ParaleloakIF - EHU

P. Sink. 314

> Prozesu paraleloak sinkronizatu egin behar dira (maiz), dela sekzio kritikoak antolatzeko, dela prozesu multzo baten exekuzioa “bateratzeko”.

> Sinkronizazioak ahalik eta trafiko gutxien sortu behar du, eta ahalik eta azkarren bete behar da.

> Agindu bereziak, atomikoak, behar dira sekzio kritikoak gauzatzeko: T&S (sinpleena) edo LL-SC bikotea. Hardwarearen laguntza behar da atomikotasuna bermatzeko.

Laburpena

Arkitektura ParaleloakIF - EHU

P. Sink. 324

> T&S soil bat (edo, hobeto, LL/SC bikotea) nahikoa da sekzio kritiko bat kudeatzeko, baldin eta lehiarik ez badago. Bestela, trafikoa murriztuko duen estrategiaren bat erabili behar da: test-and-t&s, txartelak, sarraila-bektoreak...

> Ekoizlea eta kontsumitzailea sinkronizatzeko, nahikoa da adierazle bat erabiltzea (aldagai partekatua).

> Sinkronizazio-hesiak erabili behar dira aplikazio paraleloen prozesuak exekuzioaren puntu jakin batera heldu direla ziurtatzeko. Aukeran, behin eta berriz erabil daitezkeen hesiak dira egokienak.

Laburpena

ez ahaztuazterketa, urriaren 27an

Arkitektura Paraleloak IF - EHU

P. Sink. | Laburpena

> T&S soil bat (edo, hobeto, LL/SC bikotea) nahikoa da sekzio kritiko bat kudeatzeko, baldin eta lehiarik ez badago. Bestela, trafikoa murriztuko duen estrategiaren bat erabili behar da: test-and-t&s, txartelak, sarraila-bektoreak...

> Ekoizlea eta kontsumitzailea sinkronizatzeko, nahikoa da adierazle bat erabiltzea (aldagai partekatua).

> Sinkronizazio-hesiak erabili behar dira aplikazio paraleloen prozesuak exekuzioaren puntu jakin batera heldu direla ziurtatzeko. Aukeran, behin eta berriz erabil daitezkeen hesiak dira egokienak.