Arkitektura Paraleloak

Arkitektura Paraleloak IF - EHU

Arkitektura Paraleloak

7. Datuen Koherentzia DSM Konputagailuetan- Sarrera- Koherentzia-direktorioak: MN / CM- Arazoak: trafikoa eta atomikotasuna- Origin konputagailuen protokoloa- SCI protokoloa (NUMA-Q)

Arkitektura ParaleloakIF - EHU

DK-DSM 27

Datuen koherentzia memoria partekatuko SMP sistemetan (komunikazio-sarea, busa):

> Zelataria > Egoerak / egoera iragankorrak...

Eta DSM sistemetan (mailak...)?> Memoria partekatua da, baina

fisikoki banatuta dago sistemako nodoen artean.

> Sarea ez da bus bat. Beraz, zelataria?

Sarrera


DK-DSM 37

Nola eutsi datuen koherentziari DSM sistemetan?

▪ hardwareak ziurtatzen du datuen koherentzia: → cc-NUMA

Nola? Koherentzia-direktorioak.

Sarrera

▪ hardwareak ez du datuen koherentzia ziurtatzen (programatzailearen ardura da datuen koherentzia ziurtatzea) → NUMA


DK-DSM 47

Koherentzia-direktorioak datu-blokeei buruzko informa-zioa gordetzen du:

- egoera (egonkorra, iragankorra)- kopiak non dauden

Arazoak:- direktorioaren tamaina. - koherentzia mantentzeko sortzen den

trafikoa.- koherentzia-eragiketen atomikotasuna.

Koherentzia-direktorioa sistemako prozesadoreen artean banatzen da; ez da (ezin da!) gailu “zentralizatu” bat.

Sarrera


DK-DSM 57

Koherentzia-direktorioaren kokapena eta egitura:

- MNaren ondoan, koherentzia-hitz bat datu-bloke bakoitzeko:

▪ Full bit vector ▪ Limited bit vector

- CMetan banatuta (+MN), blokeei buruzko informazioarekin “zerrenda estekatuak” osatuz:

▪ SCI, scalable coherent interface

Sarrera


DK-DSM 67

1. Full bit vector (MESI)

Direktorioaren egitura:- bit bat prozesadoreko

(1/0), datu-blokearen kopia duen edo ez adierazteko.

- hainbat bit blokearen egoera adierazteko (ohiko egoerak).

> E1 0 0 0 - 0> S1 0 1 0 - 0> M0 0 0 1 - 1> I0 0 0 0 - 0> ez (MESI)

1 1 0 1 - 1

P0 P1 P2 P3 Eg

Koher.-direktorioak (MN)

Koherentzia-direktorioa MNaren ondoan:


DK-DSM 77

ArazoakDirektorioaren tamaina, linealki hazten baita prozesadore kopuruaren arabera.

- 64 byteko blokeak:P = 64 → 65 bit (8 byte)P = 256 → 257 bit (32 byte)P = 1.024 → 1.025 bit (128 byte) + % 200!



DK-DSM 87

Koherentzia-hitzaren tamaina murrizteko aukerak:1. Datu-bloke “handiagoak” erabiltzea2. Nodo kopurua txikiagoa izatea

(egitura hierarkikoa, SMP zelatariak + direktorioa)

- 128 byteko blokeak / 4 prozesadoreko nodoak:

P = 1.024 (256x4) → 257 bit (32 byte) + %25



DK-DSM 97

2. Limited bit vector

- datu-blokeen kopia kopurua cacheetan mugatu egiten da: k kopia bakarrik.

- koherentzia-hitzean, blokearen kopia duten prozesa-doreen helbideak (log P bit) gordetzen dira.

k × log2 P << P

@1, @2, ..., @k, egoera



DK-DSM 107

- 4 prozesadoreko nodoak /128 byteko datu-blokeak / gehienez 5 kopia

P = 256 (64x4) → 5 x 6 + 1 = 31 bit ≈ 4 byte

+ % 3

P = 1.024 (256x4) → 5 x 8 + 1 = 41 bit ≈ 5 byte

+ % 4



DK-DSM 117

1 bit prozesadorekoegoera

0 ... 1 ... 0 M

L

KK = komunikazioen kontrolagailuaD = koherentzia-direktorioaL = local H = home R= remote

H

P

CKK

DMN

R

23

45

1

LD A1 S



DK-DSM 127

2

1 0… 1 …1 0 S

beste bi kopia egoeraST A0 …0 0 M

44’

33’1

L

KK = komunikazioen kontrolagailuaD = koherentzia-direktorioaL = local H = home R= remote

H

P

CKK

DMN


R1R2


DK-DSM 137

Koherentzia-direktorioak CMetan: egituraDatu-bloke baten egoerari buruzko informazioa ez da hitz bakar batean, direktorioan, zentralizatzen.Koherentzia-informazioa MNaren ondoan zein cacheetan banatzen da (cacheen direktorioetan).Esteka bikoitzeko zerrenda bat osatzen da datu-bloke bakoitzeko koherentzia-informazioarekin.

Koher.-direktorioak (CM)


DK-DSM 147

Koherentzia-informazioa (datu-bloke bakoitzeko)

@kop1 / egoera

“MN” →

@kopi-1 / @kopi+1 / egoera

CM

→



DK-DSM 157

Nola eratzen da bloke baten kopia-zerrenda estekatua?


Home(memoria nagusia)

Pi (cachea) Pj (cachea)

Pk (cachea)

Pk

*, * datu-bl.datu-bl.datu-bl.MN D

datu-bl.

*,Pj *,Pk Pi,P

k Pj,*

Pj Pi


DK-DSM 167

P = 1.024 / MN = 128 MB / CM = 512 kB / bl = 128 byte

1. MN 5 kopia, 3 biteko egoerakKoherentzia-hitza: 5 x 10 + 3 = 53 bitDirektorioa nodoetan: 53 bit x 1 M bloke = 53 Mb

2. CM“MN”an: 10 + 3 = 13 bitCacheetan: 2 x 10 + 3 bit = 23 bitNodoan: 13 x 1 M + 23 x 4 k = 13,1 Mb



DK-DSM 177

Koherentzia mantentzeak ahalik eta trafiko gutxien sortu behar du (kontrol-paketeak eta datu-paketeak).

Gainera, koherentzia mantentzeko eragiketen latentziak txikia behar du izan.

Beraz:- Pakete kopurua (trafikoa) murriztu behar da.

- Eragiketaren bide kritikoa (latentzia) txikiagotu behar da.

Arazoak: koher.-trafikoa


DK-DSM 187

Hiru protokolo koherentzia-eragiketen “elkarriz-ketak” betetzeko:

1. Eskaera / Erantzuna2. Intervention Forwarding3. Reply Forwarding

Adibidea: L prozesadoreak irakurri egin behar du cachean ez duen hitz bat, H prozesadorearen memoriako bloke batekoa, zeina R nodoan aldatuta dagoen.



DK-DSM 197

1. Eskaera / Erantzuna

L HI R1. Eskaera

4b. Blokea (eguner.)

3. Eskaera

mezuak: 5bide kritikoa: 4

0100 / M

M

4a. Erantzuna (Blokea)

2. Erantzuna



DK-DSM 207

2. Intervention Forwarding

L HI R

1. Eskaera


2. Eskaera

3. Erantzuna(Blokea)

0100 / M

M

4. Erantzuna(Blokea)



DK-DSM 217

3. Reply Forwarding

L HI

R 1. Eskaera

3a. Erantzuna (Blokea)

3b. Blokea (eguner.)

2. Eskaera


0100 / M

M



DK-DSM 227

1a. INV

2b. Erantzuna

1b. INV

?

Koherentzia-eragiketek atomikoak izan behar dute, “interferentziarik” gabe bete ahal izateko.

R1 HS

R2S

..1..1.. / S2a→ ..1..0.. / M

→ M??

Arazoak: atomikotasun eza

→M


DK-DSM 237

Atomikotasuna ziurtatzeko:

+ Egoera iragankorrak, busy, erabili behar dira, direktorioan zein cacheetan.

+ Eskaerak prozesatu ezin badira edo inkoherenteak badira:

- errefusatu egiten dira, NACK paketeen bidez.

- gorde egiten dira “buffer” batean, geroago prozesatzeko.

Arazoak: atomikotasun eza


DK-DSM 247

Bi adibide:

1. Origin konputagailuak → MN

2. SCI protokoloa (Numa-Q) → CM

Koh.-protokolo komertzialak


DK-DSM 257

▪ 512 nodo / 1.024 prozesadore / hiperkuboa▪ Bideratze moldakorra / kanal birtualak▪ Baliogabetu / MESI / write-back

▪ Full bit vector / 7 egoeraI / S / E adi: E = E edo M (kopia bakarra)3 busy egoera (desberdinak)beste egoera bat (gauza berezietarako)

▪ Reply forwarding / NACK▪ Kontrol-paketeak: Rd / INV / RdEx / ACK / NACK

Origin 2000

Origin 2000 multikonputagailuen zenbait ezaugarri:


DK-DSM 267

Hiru eragiketa analizatu behar ditugu, datuen koherentzia nola ziurtatzen den aztertzeko:

▪ Aldagai baten irakurketa (huts egin)▪ Aldagai baten idazketa (asmatu / huts egin)▪ Datu-bloke baten ordezkapena (MNa eguneratu)

Origin 2000


DK-DSM 277

Irakurketa (huts)Dir. = I/S

L H

1b. Rd A

0000 / I

I → E/S3 1100 / S

2b. Blokea

1a→ busy

2a

→ 0001 / E→ 1101 / S

Origin 2000


DK-DSM 287

L H

1000 / E

I → S4

E/M1a→ busy

2a→ 1001 / busy

R1b. Rd A 2c. Rd A (+@L)

3b. ACK / Blokea

3c. ACK / Wr (Bl.)

→ 1001 / S4

3a→ S2b. Blokea

(espek.)

Origin 2000

Irakurketa (huts)Dir. = E


DK-DSM 297

L H

1b. Rd A

xxxx / busy

I

2. NACK

1a→ busy

Origin 2000

Irakurketa (huts)Dir. = busy


DK-DSM 307

Idazketa (asm-INV / huts-RdEx)

Dir. = busy

L H

1b. INV A / RdEx A

xxxx / busy

S/I2. NACK

1a→ busy

Origin 2000


DK-DSM 317

2b. k.kop. / +Blokea

L HS/I → M

51a→ busy

2a→ 0001 / E

R1

1b. INV A / RdEx A

2c. INV A (+@L)

3b. ACK

4aS → I

1101 / S1100 / S

R2

4b. ACK

2d. INV A (+@L)

3aS → I

eraginkortasunakontuz lasterketak!

Origin 2000


Dir. = S


DK-DSM 327

L HS/I

1a→ busy

2a→ 0001 / E

R1

1b. INV A / RdEx A

2b. k.kop. / +Blokea

2c. INV A (+@L)

1101 / S1100 / S

R2

2d. INV A (+@L)

R3

→ 0011 / busy

Rd A (@R3)

?

Adi: lasterketak!

R4

NACKeraginkortasuna:ez errefusatu, gorde!

Origin 2000


Dir. = S


DK-DSM 337

L H

1000 / E

I → M4

E/M1a→ busy

2a→ 0001 / busy

R

1b. RdEx A 2c. RdEx A (+@L)

3b. ACK / Blokea

3c. ACK / Wr (Blokea)

→ 0001 / E4

3a→ I2b. k.kop. +

Blokea (espek.)

Origin 2000

Idazketa (huts-RdEx)Dir. = E


DK-DSM 347

L H

1b. INV A

1000 / E

S2. NACK

1a→ busy

Origin 2000

Idazketa (asm-INV)Dir. = E


DK-DSM 357

1b. RdEx A

L H0000 / I

I → M3

2b. Blokea

1a→ busy

2a

→ 0001 / E

Origin 2000

Idazketa (huts-RdEx)Dir. = I


DK-DSM 367

L H

1b. INV A

0000 / I

S2. NACK

1a→ busy

Origin 2000

Idazketa (asm-INV)Dir. = I


DK-DSM 377

Ordezkapena: MNa eguneratzea

Dir.: = E

L H0001 / E

M → x3

2b. ACK

1a→ busy

2a

→ 0000 / I

1b. Wr (Blokea)

Origin 2000


DK-DSM 387

L H

0001 / E

→ x4

I

2a→ 1001 / busy

R

3c. ACK

1b. Rd A

2b. Blokea (espek)

→ 1000 / E3a

1a→ busy

4→ E

2c. Rd A

M2→ busy 2d. Wr

(Blokea)

3b. Blokea

Origin 2000

Ordezkapena: MNa eguneratzea Dir.: = busy


DK-DSM 397

PC

M S/IPCI

S/I

IQ link

D

PC

PC

PC4P

4P

4P

4P

4P 4P

4P 4P

NUMA-Q

NUMA-Q multiprozesadoreen egitura:


DK-DSM 407

▪ 8 x 4 prozesadore / bus (zelataria)▪ IQ-link remote access cache

▪ Baliogabetu / MOESI / write-back

▪ <Eskaera / Erantzuna> / paketeak gorde▪ Esteka bikoitzeko zerrendak CMetan:

direktorioa (MN): egoera / @k1

direktorioa CM: egoera / @ki-1 / @ki+1

▪ SCI: scalable coherent interface

NUMA-Q

NUMA-Q multiprozesadoreen egitura:


DK-DSM 417

Blokeen egoerak:

▪CMan: - posizioa: Only, Head, Mid, Tail- egoera: Dirty (M), Fresh (S), Valid (S’), Exclusive (E) Adib.: Only-Fresh, Head-Fresh, Head-Dirty, Mid-Valid...

- eta busy egoerak

▪ “MNan”: Home (I), Fresh (E, S), Gone (M, O)

SCI koherentzia-protokoloa


DK-DSM 427

Datuen koherentzia mantentzeko hiru funtzioak:▪ List Construction

Bloke baten kopia bat cachean kargatzeko (Rd) eta kopia-zerrendako buruan kokatzeko.

▪ Roll-outBloke baten kopia cachetik kentzeko (ordezkapena), eta kopia-zerrenda egokitzeko.

▪ Purge Aldagai bat aldatzeko (Wr), eta, ondorioz, gainerako kopiak baliogabetzeko eta kopia-zerrenda egokitzeko.



DK-DSM 437

Irakurketa: List Construction (Home)

L H

1b. LC (Rd A)

2b. Blokea1a→ busy 2a

→ F | @L

I

Dir (CM) H | *

Dir (MN)

→ O-F|*-*3



DK-DSM 447

Irakurketa: List Construction (Fresh / Gone)

L H

1b. LC (Rd A)

I → H-F | *-@R5

2b. Blokea + @R

1a→ busy

2a→ F | @L

Dir (CM)

F | @RDir (MN)

R

3. New Head (@L)

4b. ACK→ T-V | @L-*

4a

Dir (CM)O-F | *-*H-F | *-@R2 → M-V | @L-@R2

zer aldatu baldin Gone?



DK-DSM 457

Idazketak: buruan dagoen kopian bakarrik!asmatu / buruan → Purge huts egin → List Construction + Purge

asmatu / ez buruan → Roll-Out + L. Const. + Purge



DK-DSM 467

Purge (Only-Fresh)

L H

1b. Wr (A-ren egoera)

2b. ACK1a→ busy

2a→ G | @L

O-F | *-*

Dir (CM)F | @L

Dir (MN)

→ O-D | *-*3



DK-DSM 477

LH R11b. Wr

(A-ren eg.)

2b. ACK

3. INV A

4b. ACK + @R2

R2

6b. ACK + *

5. INV A

Purge (Head-Fresh)

F | @L

Dir (MN)→ G | @L2a

1a→ busy H-F | *-@R1

Dir (CM)

→ O-D | *-*7 M-V |@L-@R2

Dir (CM)→ I | *-*4a

T-V |@R1-* → I | *-*6a



DK-DSM 487

Roll-Out (Wr / ordezk.)

L R2

1c. RO A + @R1

3b. ACK

3a→ T-V | @R1-*T-V | @L-*

Dir (CM)

R1

1b. RO A + @R2

2b. ACK

2a→ H-D | *-@R2H-D | *-@L

Dir (CM)

1a→ busyM-V | @R1-@R2

Dir (CM)

4→ busy / I | *-*



DK-DSM 497

Dir (MN)

G | @R1

H-D|*-@R2

H

R1 R2

T-V | @R1-*busy

L1

Dir (MN)

G | @L1

H

L1

NewHead

H

L2

busy

Dir (MN)

G | @L2

HH

L1

H

L2 NewHead

HHH

M-V|@L1-@R2

R1L1L1 Ack +

bl

H-D | *-@R1

L1

M-V|@L2-@R1

L2Ack + bl

H-D | *-@L1

R1

NUMA-Q: atomikotasuna

Arazoak: atomikotasuna (i)


DK-DSM 507

R

Dir (MN)

F | @L

H

O-F | *-*

Lbusy

LC

busy

Wr

Dir (MN)

F | @R??

NACK

NUMA-Q: atomikotasuna

Arazoak: atomikotasuna (ii)

any questions?

Arkitektura Paraleloak IF - EHU

DK-DSM | NUMA-Q: atomikotasuna

R

H

O-F | *-*

Lbusy

LC

busy

Wr

Dir (MN)

F | @R??

NACK

Arazoak: atomikotasuna (ii)

Datuen koherentziari eusteko, DSM sistemetan, koherentzia-

direktorioak erabiltzen dira.

Bi modutan antola daiteke direktorioa: blokearen koherentzia-

informazioa hitz batean zentralizatuta, MNaren ondoan;

edo CMetan banatuta, datu-blokeen kopiekin batera.

Koherentzia-eragiketen latentziak eta trafikoak ahalik eta txikiena

izan behar dute: eskaera/erantzuna, intervention forwarding eta reply forwarding.

Baina arazo nagusia atomikotasun eza da. Eta atomikotasuna

ziurtatzeko, egoera iragankorrak eta NACK paketeak erabili ohi dira.

Eta protokolo horiek gauzatzeko...

Aurreko atalean...

Documents

Arkitektura Paraleloak