Architektury paralelních počítačů II

Architektury paralelních počítačů II. Sekvenční konzistence paměti Implementace synchronizačních událostí Ing. Miloš Bečvář s použitím slajdů Prof. Ing. Pavla Tvrdíka, CSc.

Architektura počítačů

Osnova přednášky ° Opakování – definice paměťové koherence ° Model sekvenční konzistence paměti ° Typy synchronizačních událostí ° Způsoby implementace zámků ° Atomické instrukce RMW ° Instrukční pár LL & SC ° Implementace bariéry


Problém koherence skrytých pamětí - přesněji Definice: Řekneme že multiprocesorový paměťový systém je koherentní jestliže výsledek jakéhokoli provádění programu je takový, že pro každé paměťové místo je možné sestavit myšlené sériové pořadí čtení a zápisů k tomuto paměťovému místu a platí 1. Paměťové operace k danému paměťovému místu pro každý proces jsou provedeny v pořadí, ve kterém byly spuštěny tímto procesem. 2. Hodnoty vracené každou operací čtení jsou hodnotami naposledy provedené operace zápis do daného paměťového místa vzhledem k sériovému pořadí.


Stačí koherence k rozumnému chování sdilené paměti ?

Proměnná f indikuje, že proměnná x byla změněna. Očekáváme, že print(x) vytiskne 1. Paměťová koherence ovšem nijak nespecifikuje v jakém pořadí jednotlivé procesy P1 a P2 spouštějí své paměťové operace (read, write) a nijak nespecifikuje v jakém pořadí uvidí P2 zápisy do x a f. Koherence pouze zajistí, že P2 se nakonec dozví nové hodnoty x a f, ale nijak nespecifikuje v jakém pořadí tyto nové hodnoty obdrží.

Proto ani na počítači s koherentním paměťovým systémem není vyloučeno, že P2 vytiskne starou hodnotu x (tj. 0).


Co by se mohlo stát i při koherentní paměti ? P1 na procesoru 1

WRITE (X, 1) WRITE (F,1)

P2 na procesoru 2

L1: READ R1, (F) BEQZ R1, L1 READ R2, (X) print R2

Na procesoru s prováděním instrukcí mimo programové pořadí může být provedeno READ R2, (X) dříve než skončí READ R1, (F) a skok je vyhodnocen: 1. 2.

3. 4. 5. 6.

P2 spustí READ R1, (F) a nenajde F v cache, vydá požadavek na čtení z paměti, ale nejprve musí získat sběrnici. P2 využije času a spustí spekulativně READ R2, (X) za předpovězeným skokem BEQZ. Hodnota X=0 je nalezena v cache a je předána do R2. Procesor P1 získá sběrnici a provede BusWr(X,1), hodnota X je v cache u procesoru 1 zneplatněna v souladu s koherenčním protokolem. Procesor P1 získá sběrnici a provede BusWr(F,1). Procesor P2 získá sběrnici a provede BusRd(F). Do R1 získá novou hodnotu F=1 což potvrdí, že předpověď BEQZ byla správná a spekulace úspěšná. P2 vytiskne starou hodnotu X uloženou do R2. Architektura počítačů

Model sekvenční konzistence


Implementace Sekvenční Konzistence (SC)

Konzistence oproti koherenci specifikuje v jakém pořadí jednotlivé procesy spouštějí své paměťové operace (či v jak se toto pořadí jeví ostatním procesorům) Dále specifikuje, že všechny paměťové operace lze sestavit do myšleného sekvenčního pořadí. Koherence požaduje možnost sestavení myšleného sekvenčního pořadí pouze vůči jednotlivým paměťovým místům (nikoli mezi přístupy do různých paměťových míst).

Je možné implementovat cache koherenční počítač s jiným než sekvenčním konzistenčním modelem. Architektura počítačů

Postačující podmínky pro zajištění SC


SC vs optimalizace výkonu • Zajištění SC není jen problém HW neboť programátor očekává

zachování programového po adí popsaného ve zdrojovém programu ve vyšším programovacím jazyce.

• Prakticky všechny vyšší p.j. mají definován slabší model konzistence

a programátor musí striktnější podmínky na paměťové operace vynutit např. použitím deklarace proměnné jako volatile. • Různé procesory implementují buď sekvenční konzistenci nebo některý ze slabších konzistenčních modelů. Architektura počítačů

Sběrnicově založené SMP a koherence a konzistence

Sběrnice zajišťuje serializaci paměťových operací, propagaci výsledků a za určitých podmínek i atomicitu paměťových operací (záleží na protokolu sb.). Myšlené pořadí operací požadované v definicích koherence a konzistence je pořadím těchto operací na sběrnici. Architektura počítačů

WTWNA a problém koherence a konzistence

Tento důkaz ještě obsahuje skrytý předpoklad, že Read a Write jsou jednotlivými procesory spouštěny v programovém pořadí a procesor čeká na dokončení Write ! Architektura počítačů



Dijkstra, 1965







Zámek pomocí Test & Set – simulace na MESI Lock (aL)

UnLock (aL)

P3 unlocked aL P1

aL: ?

P2

I

aL: ?

P3

I

aL: 0

P4

M P3: BusUpgrd

aL: 1 Architektura počítačů

aL: ?

I


UnLock (aL)

P1 is trying to lock aL P1

aL: 0

P2

S

aL: ?

P3

I

aL: 0

P4

S

P1: BusRd


aL: ?

I


UnLock (aL)

P1 is trying to lock aL, , it succeeds P1

aL: 1

P2

M

aL: ?

P3

I

aL: 0

P4

I

P1: BusUpgrd


aL: ?

I


UnLock (aL)

P2 is trying to lock aL, P1

aL: 1

P2

S

aL: 1

P3

S

aL: 0

P4

I

P2: BusRd


aL: ?

I


UnLock (aL)

P2 is trying to lock aL, unsuccessfully P1

aL: 1

P2

I

aL: 1

P3

M

aL: 0

P4

I

P2: BusUpgrd


aL: ?

I


UnLock (aL)


aL: 1

P2

I

aL: 1

P3

S

aL: 0

P4

I

aL: 1

S

P4: BusRd



UnLock (aL)


aL: 1

P2

I

aL: 1

P3

I

aL: 0

P4

I

aL: 1

M

P4: BusUpgrd







Zámek pomocí LL & SC – simulace na MESI Lock (aL)

UnLock (aL)

P3 unlocked aL

P2

P1

aL: ?

I

aL: ?

P3

I

aL: 0

P4

M P3: BusUpgrd

aL: 1


aL: ?

I


UnLock (aL)

P1 executes LL P2

P1

aL: 0

S

aL: ?

P3

I

aL: 0

P4

S

P1: BusRd

aL: 0


aL: ?

I


UnLock (aL)

P2 executes LL P2

P1

aL: 0

S

aL: 0

P3

S

aL: 0

P4

S

P2: BusRd

aL: 0


aL: ?

I


UnLock (aL)

P1 executes SC (P2 will cancel attempt to execute SC) P2

P1

aL: 1

M

aL: 0

P3

I

aL: 0

P4

I

P1: BusUpgrd

aL: 0


aL: ?

I


UnLock (aL)

P4 executes LL P2

P1

aL: 1

S

aL: 0

P3

I

aL: 0

P4

I

aL: 1

S P4: BusRd

aL: 1



UnLock (aL)

P2 executes LL, now P2 and P4 loops internally till the aL is unlocked P2

P1

aL: 1

S

aL: 1

P3

S

aL: 0

P4

I

P2: BusRd

aL: 1


aL: 1

S






Závěr • Pro

synchronizaci v paralelních počítačích se sdílenou pamětí je vhodné definovat sekven n konzistentní pam ový systém. • Synchronizační operace jsou vzájemné vylou ení, dvoubodová synchronizace a synchroniza ní bariéra. • Základem implementace synchronizačních operací jsou atomické RMW primitivy. • V ISA procesorů se vyskytují RMW instrukce T&S, SWAP, F&I, C&S • Novější procesory podporují tvorbu RMW primitiv pomocí instrukcí LL a SC, které umožňují efektivní implementaci synchronizačních operací v systémech se skrytými paměťmi


Architektury paralelních počítačů II

Recommend Documents