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 Paraleloak IF - EHU
DK-DSM 2 7
Datuen koherentzia memoria partekatuko SMP sistemetan (komunikazio-sarea: busa)
> Zelataria > Egoerak / egoera iragankorrak...
Eta DSM sistemetan (mailak...)? > Memoria partekatzen da, baina fisikoki
banatuta dago sistemako nodoen artean. > Sarea ez da bus bat. Beraz, zelataria?
Sarrera
Arkitektura Paraleloak IF - EHU
DK-DSM 3 7
Nola eutsi datuen koherentziari DSM sistemetan?
▪ hardwareak ziurtatzen du datuen koherentzia → cc-NUMA
Nola? Koherentzia-direktorioak.
Sarrera
▪ hardwareak ez du ziurtatzen datuen koherentzia (programatzailearen ardura da koherentzia ziurtatzea) → NUMA
Arkitektura Paraleloak IF - EHU
DK-DSM 4 7
Koherentzia-direktorioak datu-blokeei buruzko informa-zioa gordetzen du:
- egoera (egonkorra, iragankorra) - kopiak non dauden
Arazoak: - direktorioaren tamaina. - koherentzia lortzeko sortzen den trafikoa. - koherentzia-eragiketen atomikotasuna.
Koherentzia-direktorioa sistemako prozesadoreen artean banatzen da; ez da (ezin da!) gailu “zentralizatu” bat.
Sarrera
Arkitektura Paraleloak IF - EHU
DK-DSM 5 7
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
Arkitektura Paraleloak IF - EHU
DK-DSM 6 7
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).
> E 1 0 0 0 - 0
> S 1 0 1 0 - 0
> M 0 0 0 1 - 1
> I 0 0 0 0 - 0
> ez (MESI) 1 1 0 1 - 1
P0 P1 P2 P3 Eg
Koher.-direktorioak (MN)
Koherentzia-direktorioa MNaren ondoan:
Arkitektura Paraleloak IF - EHU
DK-DSM 7 7
Arazoak
Direktorioaren 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!
Koher.-direktorioak (MN)
Arkitektura Paraleloak IF - EHU
DK-DSM 8 7
Koherentzia-hitzaren tamaina murrizteko aukerak:
1. Datu-bloke “handiagoak” erabiltzea
2. Nodo kopurua txikiagoa izatea (egitura hierarkikoa, SMP zelatariak + direktorioa)
- 128 byteko blokeak / 4 prozesadoreko nodoak:
P = 1.024 (256x4) → 257 bit (32 byte) + %25
Koher.-direktorioak (MN)
Arkitektura Paraleloak IF - EHU
DK-DSM 9 7
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
Koher.-direktorioak (MN)
Arkitektura Paraleloak IF - EHU
DK-DSM 10 7
- 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
Koher.-direktorioak (MN)
Arkitektura Paraleloak IF - EHU
DK-DSM 11 7
1 bit prozesadoreko egoera
0 ... 1 ... 0 M
L
KK = komunikazioen kontrolagailua D = koherentzia-direktorioa
L = local H = home R= remote
H
P
C
KK
D
MN
R
2 3
4 5
1
LD A
1 S
Koher.-direktorioak (MN)
Arkitektura Paraleloak IF - EHU
DK-DSM 12 7
2
1 0… 1 …1 0 S
beste bi kopia egoera ST A
0 …0 0 M
4
4’
3
3’
1
L
KK = komunikazioen kontrolagailua D = koherentzia-direktorioa
L = local H = home R= remote
H
P
C
KK
D
MN
Koher.-direktorioak (MN)
R1
R2
Arkitektura Paraleloak IF - EHU
DK-DSM 13 7
Koherentzia-direktorioak CMetan: egitura
Datu-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)
Arkitektura Paraleloak IF - EHU
DK-DSM 14 7
Koherentzia-informazioa (datu-bloke bakoitzeko)
@kop1 / egoera “MN” →
@kopi-1 / @kopi+1 / egoera CM →
Koher.-direktorioak (CM)
Arkitektura Paraleloak IF - EHU
DK-DSM 15 7
Nola eratzen da bloke baten kopia-zerrenda estekatua?
Koher.-direktorioak (CM)
Home (memoria nagusia)
Pi (cachea) Pj (cachea) Pk (cachea) Pk
*, * datu-bl. datu-bl.
datu-bl. MN D
datu-bl.
*,Pj *,Pk Pi,Pk
Pj,*
Pj Pi
Arkitektura Paraleloak IF - EHU
DK-DSM 16 7
P = 1.024 / MN = 128 MB / CM = 512 kB / bl = 128 byte
1. MN 5 kopia, 3 biteko egoerak Koherentzia-hitza: 5 x 10 + 3 = 53 bit Direktorioa nodoan: 53 bit x 1 M bloke = 53 Mb
2. CM Koherentzia-hitza “MN”an: 10 + 3 = 13 bit Koherentzia-hitza cacheetan: 2 x 10 + 3 bit = 23 bit Direktorioa nodoan:
13 x 1 M bloke + 23 x 4 k bloke = 13,1 Mb
Koher.-direktorioak (CM)
Arkitektura Paraleloak IF - EHU
DK-DSM 17 7
Koherentzia mantentzeak ahalik eta trafiko gutxien sortu behar du (kontrol-paketeak eta datu-paketeak).
Gainera, koherentzia mantentzeko prozesuak azkarra izan behar du, latentzia baxukoa.
Beraz: - Sortzen den pakete kopurua (trafikoa) murriztu
behar da. - Komunikazioen bide kritikoa (latentzia) ahalik eta
motzena izan behar du.
Arazoak: koher.-trafikoa
Arkitektura Paraleloak IF - EHU
DK-DSM 18 7
Hiru protokolo koherentzia-eragiketen “elkarriz-ketak” betetzeko:
1. Eskaera / Erantzuna 2. Intervention Forwarding 3. Reply Forwarding
Adibidea: L prozesadoreak irakurri egin behar du cachean ez duen hitz bat, H prozesadorearen memoriako bloke batekoa, zeina R nodoko cachean aldatuta dagoen.
Arazoak: koher.-trafikoa
Arkitektura Paraleloak IF - EHU
DK-DSM 19 7
1. Eskaera / Erantzuna
L H I
R
1. Eskaera
4b. Blokea (eguner.)
3. Eskaera
mezuak: 5 bide kritikoa: 4
0100 / M
M
4a. Erantzuna (Blokea)
2. Erantzuna
Arazoak: koher.-trafikoa
→ 0101 / S
→ S → S
Arkitektura Paraleloak IF - EHU
DK-DSM 20 7
2. Intervention Forwarding
L H I
R
1. Eskaera
mezuak: 4 bide kritikoa: 4
2. Eskaera
3. Erantzuna (Blokea)
0100 / M
M
4. Erantzuna (Blokea)
Arazoak: koher.-trafikoa
→ 0101 / S
→ S → S
Arkitektura Paraleloak IF - EHU
DK-DSM 21 7
3. Reply Forwarding
L H I
R
1. Eskaera
3a. Erantzuna (Blokea)
3b. Blokea (eguner.)
2. Eskaera
mezuak: 4 bide kritikoa: 3
0100 / M
M
Arazoak: koher.-trafikoa
→ 0101 / S
→ S → S
Arkitektura Paraleloak IF - EHU
DK-DSM 22 7
1a. INV
2b. Erantzuna
1b. INV
?
Koherentzia-eragiketek atomikoak izan behar dute, “interferentziarik” gabe bete ahal izateko.
R1 H S
R2 S
..1..1.. / S 2a → ..1..0.. / M
→ M??
Arazoak: atomikotasun eza
→M
Arkitektura Paraleloak IF - EHU
DK-DSM 23 7
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
Arkitektura Paraleloak IF - EHU
DK-DSM 24 7
Bi adibide:
1. Origin konputagailuak → MN
2. SCI protokoloa (Numa-Q) → CM
Koh.-protokolo komertzialak
Arkitektura Paraleloak IF - EHU
DK-DSM 25 7
▪ 512 nodo / 1.024 prozesadore / hiperkuboa
▪ Bideratze moldakorra / kanal birtualak
▪ Baliogabetu / MESI / write-back
▪ Full bit vector / 7 egoera direktorioan I / 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:
Arkitektura Paraleloak IF - EHU
DK-DSM 26 7
Hiru eragiketa analizatu behar ditugu, aldagai partekatuen koherentzia nola ziurtatzen den aztertzeko:
▪ Aldagai baten irakurketa (huts egin)
▪ Aldagai baten idazketa (asmatu / huts egin)
▪ Datu-bloke baten ordezkapena (MNa eguneratu)
Origin 2000
Arkitektura Paraleloak IF - EHU
DK-DSM 27 7
Irakurketa (huts) Dir. = I/S
L H
1b. Rd A
0000 / I
I → E/S 3 1100 / S
2b. Blokea
1a → busy
2a
→ 0001 / E
→ 1101 / S
Origin 2000
Arkitektura Paraleloak IF - EHU
DK-DSM 28 7
L H
1000 / E
I → S 4
E/M 1a → busy
2a → 1001 / busy
R
1b. Rd A 2c. Rd A (+@L)
3b. ACK / Blokea
3c. ACK / Wr (Bl.)
→ 1001 / S 4
3a → S
2b. Blokea (espek.)
Origin 2000
Irakurketa (huts) Dir. = E
Arkitektura Paraleloak IF - EHU
DK-DSM 29 7
L H
1b. Rd A
xxxx / busy
I
2. NACK
1a → busy
Origin 2000
Irakurketa (huts) Dir. = busy
Arkitektura Paraleloak IF - EHU
DK-DSM 30 7
Idazketa (asm-INV / huts-RdEx) Dir. = busy
L H
1b. INV A / RdEx A
xxxx / busy
S/I 2. NACK
1a → busy
Origin 2000
Arkitektura Paraleloak IF - EHU
DK-DSM 31 7
2b. k.kop. / +Blokea
L H S/I → M
5 1a → busy
2a → 0001 / E
R1
1b. INV A / RdEx A
2c. INV A (+@L)
3b. ACK
4a S → I
1101 / S 1100 / S
R2
4b. ACK
2d. INV A (+@L)
3a S → I
eraginkortasuna kontuz lasterketak!
Origin 2000
Idazketa (asm-INV / huts-RdEx) Dir. = S
Arkitektura Paraleloak IF - EHU
DK-DSM 32 7
L H S/I
1a → busy
2a → 0001 / E
R1
1b. INV A / RdEx A
2b. k.kop. / +Blokea
2c. INV A (+@L)
1101 / S 1100 / S
R2
2d. INV A (+@L)
R3
→ 0011 / busy
Rd A (@R3)
?
Adi: lasterketak!
R4
NACK eraginkortasuna: ez errefusatu, gorde!
Origin 2000
Idazketa (asm-INV / huts-RdEx) Dir. = S
Arkitektura Paraleloak IF - EHU
DK-DSM 33 7
L H
1000 / E
I → M 4
E/M 1a → busy
2a → 0001 / busy
R
1b. RdEx A 2c. RdEx A (+@L)
3b. ACK / Blokea
3c. ACK / Wr (Blokea)
→ 0001 / E 4
3a → I
2b. k.kop. + Blokea (espek.)
Origin 2000
Idazketa (huts-RdEx) Dir. = E
Arkitektura Paraleloak IF - EHU
DK-DSM 34 7
L H
1b. INV A
1000 / E
S 2. NACK
1a → busy
Origin 2000
Idazketa (asm-INV) Dir. = E
Arkitektura Paraleloak IF - EHU
DK-DSM 35 7
1b. RdEx A
L H 0000 / I
I → M 3
2b. Blokea
1a → busy
2a
→ 0001 / E
Origin 2000
Idazketa (huts-RdEx) Dir. = I
Arkitektura Paraleloak IF - EHU
DK-DSM 36 7
L H
1b. INV A
0000 / I
S 2. NACK
1a → busy
Origin 2000
Idazketa (asm-INV) Dir. = I
Arkitektura Paraleloak IF - EHU
DK-DSM 37 7
Ordezkapena: MNa eguneratzea Dir. = E
L H 0001 / E
M → x 3
2b. ACK
1a → busy
2a
→ 0000 / I
1b. Wr (Blokea)
Origin 2000
Arkitektura Paraleloak IF - EHU
DK-DSM 38 7
L H
0001 / E
→ x 4
I
2a → 1001 / busy
R
3c. ACK
1b. Rd A
2b. Blokea (espek.)
→ 1000 / E 3a
1a → busy
4 → E
2c. Rd A
M 2 → busy 2d. Wr (Blokea)
3b. Blokea
Origin 2000
Ordezkapena: MNa eguneratzea Dir. = busy
Arkitektura Paraleloak IF - EHU
DK-DSM 39 7
P C
M S/I
PCI
S/I
IQ link
D
P C
P C
P C 4P
4P
4P
4P
4P 4P
4P 4P
NUMA-Q
NUMA-Q multiprozesadorearen egitura:
Arkitektura Paraleloak IF - EHU
DK-DSM 40 7
▪ 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 multiprozesadorearen egitura:
Arkitektura Paraleloak IF - EHU
DK-DSM 41 7
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
Arkitektura Paraleloak IF - EHU
DK-DSM 42 7
Datuen koherentzia mantentzeko hiru funtzioak:
▪ List Construction Bloke baten kopia bat cachean kargatzeko (Rd) eta
kopia-zerrendako buruan kokatzeko.
▪ Roll-out Bloke baten kopia cachetik kentzeko (ordezkapena),
eta kopia-zerrenda egokitzeko.
▪ Purge Aldagai bat aldatzeko (Wr), eta, ondorioz, gainerako
kopiak baliogabetzeko eta kopia-zerrenda egokitzeko.
SCI koherentzia-protokoloa
Arkitektura Paraleloak IF - EHU
DK-DSM 43 7
Irakurketa: List Construction (Home)
L H
1b. LC (Rd A)
2b. Blokea 1a
→ busy 2a
→ F | @L
I
Dir (CM) H | *
Dir (MN)
→ O-F|*-*
3
SCI koherentzia-protokoloa
Arkitektura Paraleloak IF - EHU
DK-DSM 44 7
Irakurketa: List Construction (Fresh / Gone)
L H
1b. LC (Rd A)
I → H-F | *-@R
5
2b. Blokea + @R
1a
→ busy
2a → F | @L
Dir (CM)
F | @R
Dir (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?
SCI koherentzia-protokoloa
Arkitektura Paraleloak IF - EHU
DK-DSM 45 7
Idazketak: buruan dagoen kopian bakarrik!
asmatu / buruan → Purge
huts egin → List Construction + Purge
asmatu / ez buruan → Roll-Out + L. Const. + Purge
SCI koherentzia-protokoloa
Arkitektura Paraleloak IF - EHU
DK-DSM 46 7
Purge (Only-Fresh)
L H
1b. Wr (A-ren egoera)
2b. ACK 1a
→ busy
2a
→ G | @L
O-F | *-*
Dir (CM)
F | @L
Dir (MN)
→ O-D | *-*
3
SCI koherentzia-protokoloa
Arkitektura Paraleloak IF - EHU
DK-DSM 47 7
L H R1 1b. 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 | @L
2a
1a
→ busy H-F | *-@R1
Dir (CM)
→ O-D | *-*
7 M-V |@L-@R2
Dir (CM)
→ I | *-*
4a
T-V |@R1-* → I | *-*
6a
SCI koherentzia-protokoloa
Arkitektura Paraleloak IF - EHU
DK-DSM 48 7
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 | *-@R2 H-D | *-@L
Dir (CM)
1a → busy M-V | @R1-@R2
Dir (CM)
4 → busy / I | *-*
SCI koherentzia-protokoloa
Arkitektura Paraleloak IF - EHU
DK-DSM 49 7
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
H H
L1
H
L2
NewHead
H H H
M-V|@L1-@R2
R1 L1 Ack + bl
H-D | *-@R1
L1
M-V|@L2-@R1
L2 Ack + bl
H-D | *-@L1
R1
NUMA-Q: atomikotasuna
Arazoak: atomikotasuna (i)
Arkitektura Paraleloak IF - EHU
DK-DSM 50 7
R
Dir (MN)
F | @L
H
O-F | *-*
L
busy
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 | *-*
L
busy
LC
busy
Wr
Dir (MN) F | @R
??
NACK
Arazoak: atomikotasuna (ii)
Top Related