Les 9: Meerdradige uitvoering consistentie Geavanceerde computerarchitectuur Lieven Eeckhout Academiejaar 2008-2009 Universiteit Gent
Overzicht • Sequentiële consistentie • Versoepelde consistentie • Transactional memory
2
Geheugenconsistentie • Geheugenconsistentiemodel specificeert de onderlinge volgorde van geheugenreferenties op een processor t.o.v. de geheugenreferenties van andere processors • Is een integraal onderdeel van de ISA van een systeem voor multiprocessordoeleinden – “contract” tussen de hardware en software
• Is van belang voor een correcte uitvoering van meerdradige applicaties 3
Consistentie vs coherentie • Coherentie specificeert de onderlinge volgorde van geheugenreferenties naar eenzelfde geheugenlocatie • Consistentiemodel specificeert de onderlinge volgorde van geheugenreferenties naar verschillende geheugenlocaties
4
A en B zijn gedeelde variabelen, en zijn initieel nul
Voorbeeld
Draad 0 A=1; if (B==0) { // critical section A=0; }
Draad 1
algoritme van Dekkers
B=1; if (A==0) { // critical section B=0; }
• Algoritme van Dekkers is een software implementatie voor locking • Mutuele exclusie is gegarandeerd zolang eerst geschreven wordt en dan pas gelezen wordt • Maar in OoO processor kunnen geheugenoperaties herordend worden, b.v. via load bypassing
5
Voorbeeld (bis) Draad 0 A=1; if (B==0) { // critical section A=0; }
Draad 1 B=1; if (A==0) { // critical section B=0; }
• Enkele mogelijke correcte uitvoeringen: – WA,0;RB,0;WB,1;RA,1: draad 0 in kritische sectie – WB,1;RA,1;WA,0;RB,0: draad 1 in kritische sectie
W = write; R = read; subscript X,n = op geheugenlocatie X door draad n
• Een incorrecte uitvoering: – RB,0;RA,1;WA,0;WB,1: beide draden in kritische sectie – RB,0;WB,1;RA,1;WA,0: beide draden in kritische sectie 6
Voorbeeld (ter) Draad 1
Draad 2
A=1; if (B==0) { critical section A=0; }
B=1; if (A==0) { critical section B=0; }
• B.v. indien de leesoperatie vóór de schrijfoperatie uitgevoerd kan worden (load bypassing wegens niet-identieke adressen) • Mutuele exclusie is niet langer gegarandeerd 7
Consistentiemodellen • Twee types – Sequentiële consistentie (SC) • Sequential consistency • Totale ordening tussen alle geheugenoperaties van alle processors
– Versoepelde consistentie • Relaxed consistency • Partiële ordening tussen de geheugenoperaties van alle processors • Betere prestatie omdat totale ordening niet steeds nodig is 8
Sequentiële consistentie • Totale ordening tussen alle geheugenreferenties van alle processors • Door Lamport in 1979 • Alsof alle processors alle gedeelde variabelen om beurt lezen en schrijven; bovendien is de ordening per draad zoals opgelegd door de programmavolgorde • Conceptueel: ordening in een time-sharing systeem == multiprocessor met SC • Eenvoudig voor programmeur 9
Sequentiële consistentie Processors P1 issuing memory references as per program order
P2
Pn
The “switch” is randomly set after each memory reference
Memory
Uit Culler, Singh en Gupta “Parallel Computer Architecture”
• “The result of the execution is the same as if the operations of all processors are executed in some sequential order, and the operations of each individual processor appear in the order specified by its program.” (Lamport, 1979) 10
Voorbeelden
Draad 1 ld ld st st ld st
A; B; C; A; A; B;
een SC uitvoering draad 1 ld A ld B
draad 2
st B ld A
een andere SC uitvoering draad 1
ld C
ld A st B
ld B
B; A; C; A; B; B;
ld B
st C
st A st B
draad 2
st ld ld st st ld
ld A
st C
st A
Draad 2
st A ld A st B
st B ld A ld C
st A st B ld B 11
Waarom SC? • Is een eenvoudig en intuïtief programmeermodel • Heel wat legacy code werd geschreven voor time-sharing omgeving – Men wil dat die code ook werkt op MP systeem – Men wil inspanningen niet doen om code te herschrijven
12
SC: bespreking • SC implementeren op een efficiënte manier voor goede prestatie is niet eenvoudig • Wegens – Totale ordening van geheugenoperaties per draad (↔ OoO paradigma) – Totale ordening van geheugenoperaties van alle processors • Vereist zeer veel bandbreedte over interconnectie 13
Maar... • Totale ordening is niet steeds nodig • Dus: versoepelen – Enkel die geheugenreferenties ordenen die in volgorde uitgevoerd moeten worden teneinde de echte afhankelijkheden te respecteren • Enkel ordening op gedeelde variabelen • Betere prestatie en illusie van SC uitvoering
– Merk op: niet hetzelfde als versoepelde consistentie (zie later) • Versoepeling op microarchitecturaal niveau versus op architecturaal niveau
• ~ OoO uitvoering van afhankelijkheden via registers en geheugen in OoO processor
14
SC implementeren • Via cachecoherentie worden RAW afhankelijkheden tussen verschillende processors gerespecteerd – Indien CPU A een variabele leest die geschreven wordt door CPU B, moet eerst de variabele in CPU A ongeldig gemaakt worden om nadien de nieuwe waarde te kopiëren van CPU B naar CPU A
• Indien geen coherentietrafiek (invalidates en/of cache misses), zijn er geen afhankelijkheden tussen de CPUs 15
SC implementeren (bis) • M.a.w. geen consistentieregels nodig voor cache hits tussen coherentietrafiek (invalidate en/of cache miss) – Geen interventie voor een groot deel van de geheugenoperaties wegens cache hits
• Twee overblijvende problemen – Lokaal probleem: ordening van cache hits t.o.v. coherentietrafiek – Globaal probleem: ordening van invalidates en cache misses 16
Globale probleem • Er is ergens in het systeem één punt nodig waar de cache misses en invalidaties geordend worden • Kleine multiprocessor met gedeelde bus – Toegang tot de bus wordt geordend
• Grote multiprocessor met een directory – Toegangen ordenen aan de ingang van de directory of in de interconnectie 17
Lokale probleem • Ordenen van cache hits t.o.v. coherentietrafiek • Eenvoudig in OoO processor • De load/store queue uitbreiden om ook adressen van de globale stroom te bekijken – Gebeurt toch reeds voor respecteren van RAW afhankelijkheden tussen geheugenoperaties (zie vroeger) 18
M.a.w. speculatie • We speculeren dat een geheugenoperatie niet geordend moet worden • Indien later blijkt dat ordening vereist is, heruitvoeren • Dit mechanisme is reeds aanwezig voor de OoO uitvoering van geheugenoperaties (load bypassing en load forwarding) • We hebben dus een mechanisme nodig om inbreuk op de ordening te detecteren 19
Uitbreiding in OoO processor finished load buffer CPU B bus upgrades bus writes
OoO processorkern
CPU C
CPU D
in-order commit bus CPU A 20
Detectie van inbreuk op ordening • We markeren een speculatieve leesoperatie indien die hetzelfde adres refereert als het adres dat op de bus verschijnt t.g.v. een externe schrijfoperatie • Bij completion van een gemarkeerde leesoperatie, de leesoperatie beschouwen als een foutief voorspelde sprong – De leesoperatie en alle daarop volgende instructies opnieuw ophalen en uitvoeren – Geïmplementeerd in MIPS R10K, HP PA-8000 en Intel Pentium Pro 21
Voorbeeld 1 Draad 1 st A=1 ld B ...
Draad 2 ... ld A ...
ld B st A
coherentie ld A ld A
execute
ld B
commit 22
Voorbeeld 2 Draad 1 st A=1 if (ld B==0) { // critical section st A=0 }
Draad 2 st B=1 if (ld A==0) { // critical section st B=0 }
ld B st B=1 ld A
st A=1 execute
ld B
commit
st A=0
beiden in kritische sectie
ld A st B=0
23
Voorbeeld 2 (bis) Draad 1 st A=1 if (ld B==0) { // critical section st A=0 }
Draad 2 st B=1 if (ld A==0) { // critical section st B=0 }
ld B st B=1 ld A ld A st A=1 execute commit
st B=0
ld B ld B st A=0 24
SC versoepelen in hardware • Wordt vaak toegepast – MIPS R10K, HP PA-8000, Intel Pentium Pro
• Heeft beperkingen – Vereist extra hardware – Niet alle processors ondersteunen dit – Toepasbaarheid is beperkt tot de processor • Dit is een microarchitecturale optimalisatie • Compiler is niet in staat instructies te herordenen 25
Overzicht • Sequentiële consistentie • Versoepelde consistentie • Transactional memory
26
Relaxed Consistency • Waarom niet het geheugenmodel wijzigen/versoepelen? – Relaxed memory consistency model
• Idee – Eenvoudige hardware – Programmeur/compiler moet geheugenoperaties aanduiden die geordend moeten worden • Alle andere operaties hoeven niet geordend te worden
• Voordelen – Stelt compiler én processor in staat geheugenoperaties te herordenen 27
Versoepelde geheugenmodellen • Groep 1: een leesoperatie kan een schrijfoperatie bypassen – TSO, PC
• Groep 2: een schrijfoperatie kan ook een schrijfoperatie bypassen – PSO
• Groep 3: lees- en schrijfoperaties kunnen ook leesoperaties bypassen – WO, RC, RMO, Alpha, PowerPC
• [Merk op: een read-modify-write instructie is een lees- én schrijfoperatie] 28
Groep 1: Versoepelen van schrijf-lees ordening • Een leesoperatie kan een schrijfoperaties bypassen – Kortere latentie leesoperatie – Latentie verbergen van schrijfoperatie
• 2 varianten – TSO: total store ordering • Garandeert write atomicity – Write atomicity = alle schrijfoperaties (tot om het even welke geheugenlocatie) zijn zichtbaar voor alle processors in dezelfde ordening
– PC: processor consistency • Garandeert geen write atomicity, enkel totale ordening van schrijfoperaties per processor 29
Fragment 1 Draad 1 A = 1; flag = 1;
Draad 2 while (flag == 0); print A;
TSO en PC garanderen SC semantiek
30
Fragment 2 Draad 1 A = 1; B = 1;
Draad 2 print B; print A;
• SC garandeert dat – Indien ‘1’ geprint wordt voor B, ook ‘1’ geprint wordt voor A
• Zo ook TSO en PC 31
Fragment 3 Draad 1 A = 1;
Draad 2 while (A == 0); B = 1;
Draad 3 while (B == 0); print A;
• SC garandeert dat A als ‘1’ geprint wordt • Zo ook TSO • Maar niet PC – Schrijfoperatie “B=1;” kan vroeger zichtbaar zijn voor draad 3 dan schrijfoperatie “A=1;” – Dit kan optreden tgv. buffering in processor, cache en geheugencontroller, interconnectienetwerk, etc. 32
Fragment 4 Draad 1 A = 1; print B;
Draad 2 B = 1; print A;
• SC garandeert dat – Onmogelijk ‘0’ geprint wordt voor zowel A als B
• Dit is de basis voor Dekker’s algoritme – Software manier voor mutuele exclusie
• Maar niet TSO en PC – Omdat een leesoperatie een schrijfoperatie kan bypassen – M.a.w., Dekker’s algoritme werkt niet in TSO en PC 33
Hoe SC garanderen wanneer nodig in TSO/PC model? • Mechanisme nodig dat garandeert dat – (a) Een leesoperatie niet vóór een schrijfoperatie (waarbij lees- na schrijfoperatie komt in programmavolgorde) uitgevoerd wordt – (b) Write atomicity vóór een leesoperatie
• (a) Kan gegarandeerd worden via MEMBAR (memory barrier) of FENCE instructies 34
Memory barriers • Een barrier is een instructie • Bestaat typisch in verschillende varianten voor verschillende ordeningen – Hier: write-to-read MEMBAR • Alle schrijfoperaties vóór de barrier moeten uitgevoerd zijn alvorens de uitvoering van de leesoperatie gestart kan worden • B.v. fragment 4: Draad 1 A = 1; w2r_MEMBAR; print B;
Draad 2 B = 1; w2r_MEMBAR; print A;
35
SC semantiek bij TSO/PC • MEMBAR vóór de leesoperatie • OF – De leesoperatie vervangen door een readmodify-write instructie • Leesoperatie wordt behandeld als een schrijfoperatie, dus geen herordening
36
Barrier implementatie • Processor blokkeren (stall) tot alle voorgaande geheugenoperaties architecturaal gezien uitgevoerd zijn (completed) • Vereist inspecteren – ROB – store buffer – alle invalidaties in andere CPUs tgv. een store vóór de barrier moeten afgehandeld zijn
• Kan honderden processorcycli duren 37
Groep 2: Versoepelen van schrijf-schrijf ordening • Een schrijfoperatie kan ook een schrijfoperatie (naar een andere geheugenlocatie) bypassen – Laat write buffer merging toe – Latentie van schrijfoperaties verbergen
• PSO: partial store ordering – Sun Sparc – Garandeert ook write atomicity 38
Fragment 1 Draad 1 A = 1; flag = 1;
Draad 2 while (flag == 0); print A;
• TSO en PC garanderen SC semantiek • PSO niet
39
Fragment 2 Draad 1 A = 1; B = 1;
Draad 2 print B; print A;
• SC garandeert dat – Indien ‘1’ geprint wordt voor B, ook ‘1’ geprint wordt voor A
• Zo ook TSO en PC • Is niet het geval voor PSO 40
Fragment 3 Draad 1 A = 1;
Draad 2 while (A == 0); B = 1;
Draad 3 while (B == 0); print A;
• SC garandeert dat A als ‘1’ geprint worden • Zo ook TSO en PSO – Wegens write atomicity
• Maar niet PC – Wegens geen write atomicity
41
Fragment 4 Draad 1 A = 1; print B;
•
Draad 2 B = 1; print A;
SC garandeert dat – Onmogelijk ‘0’ geprint wordt voor zowel A als B
•
Maar niet voor TSO, PC en PSO – Omdat een leesoperatie een schrijfoperatie kan bypassen
42
Hoe SC garanderen wanneer nodig in PSO model? • Via write-to-write MEMBAR of STBAR – Alle schrijfoperaties vóór de barrier moeten uitgevoerd zijn alvorens de uitvoering van de volgende schrijfoperatie gestart kan worden – B.v. fragment 1: Draad 1 A = 1; w2w_MEMBAR; flag = 1;
Draad 2 while (flag == 0); print A;
43
Groep 3: Alle ordeningen versoepelen • Geen enkele programma-ordening wordt gegarandeerd – Bovenop groep 1 en 2: lees- en schrijfoperaties kunnen ook leesoperaties bypassen
• Verbergen van latentie tgv. leesoperaties – Out-of-order uitvoering van leesoperaties – Maakt heel wat compileroptimalisaties mogelijk 44
Verschillende modellen • WO: weak ordering • RC: release consistency • Commerciële implementaties – RMO: relaxed memory ordering • Sun Sparc V9
– Digital Alpha – IBM PowerPC
45
WO: Weak Ordering • Idee: – Parallelle programma’s gebruiken synchronisatie-operaties om geheugentoegangen te coördineren – Tussen synchronisatie-operaties: geen ordening van geheugenoperaties
46
Voorbeeld Draad 1 ... lock (taskQ); newTask->next = head; if (head != NULL) head->prev = newTask; head = newTask; unlock (taskQ); ...
Draad 2 ... lock (taskQ); newTask->next = head; if (head != NULL) head->prev = newTask; head = newTask; unlock (taskQ); ...
• Semantiek blijft behouden – Ondanks herordeningen tss. synchronisatie-operaties – Zolang geheugenoperaties niet herordend worden tov. synchronisatie-operaties, en vice versa 47
SYNC operatie • Alle geheugenoperaties vóór de SYNC operatie moeten uitgevoerd zijn alvorens de uitvoering van de volgende geheugenoperatie gestart kan worden
read/write … read/write
SYNC
read/write … read/write
SYNC
read/write … read/write
48
RC: Release Consistency Draad 1
acquire: toegang krijgen tot ... code of variabelen lock (taskQ); newTask->next = head; if (head != NULL) head->prev = newTask; head = newTask; release: toegang verlenen unlock (taskQ); (aan andere processor) ... tot code of variabelen
• Uitbreiding op WO model door onderscheid te maken tussen verschillende types van synchronisatie 49
Acquire en Release • Acquire – Alle geheugenoperaties die volgen op de acquire kunnen niet uitgevoerd worden vóór de acquire – acquire mag herordend worden tov. voorgaande operaties
• Release – Alle geheugenoperaties die komen vóór de release moeten uitgevoerd zijn alvorens de release uit te voeren – Operaties volgend op de release kunnen herordend worden tov. de release 50
1 read/write … read/write
2 read/write … read/write
SYNC
3 SYNC
read/write … read/write Weak Ordering
1 read/write … read/write 2 acquire
read/write … read/write
release
3
Release Consistency
read/write … read/write 51
Commerciële implementaties • Veronderstellen geen ordening • Verschillen in de instructies die aangeboden worden om een ordening op te leggen – Memory barriers – Of fences genaamd
• ISA-specifiek
52
Voorbeeld 1: Digital Alpha • Twee soorten fence instructies – Memory barrier (MB) = synchronisatie-operatie zoals in WO
– Write memory barrier (WMB) = STBAR in PSO; legt enkel ordening op voor schrijfoperaties
53
Voorbeeld 2: Sun Sparc V9 RMO • Relaxed memory ordering • MEMBAR fence instructie met 4 ‘flavor’ bits – Read-to-read – Read-to-write – Write-to-read – Write-to-write
• Elke combinatie van bits kan aangezet worden 54
Voorbeeld 3: IBM PowerPC • Eén enkele fence instructie – sync – zoals MB instructie in Alpha ISA
• Geen write atomicity
55
model
w-to-r reorder
w-to-w reorder
r-to-r/w reorder
SC
write atomicity
operaties
ja
TSO
ja
ja
MEMBAR
PC
ja
neen
MEMBAR
PSO
ja
ja
ja
STBAR
WO
ja
ja
ja
ja
SYNC
RC
ja
ja
ja
ja/neen
REL, ACQ
RMO
ja
ja
ja
ja
MEMBARs
Alpha
ja
ja
ja
ja
MB, WMB
PowerPC
ja
ja
ja
neen
SYNC 56
Hardware/software interface • Redeneren over toegelaten herordeningen is niet eenvoudig • Ook portabiliteit is een mogelijks probleem – B.v. een programma dat correct uitvoert op een TSO systeem zal niet correct uitvoeren op een RMO systeem
• Programmeermodel is vaak geïnspireerd op WO/RC modellen – Programmeur moet synchronisatie toevoegen – Compiler vertaalt synchronisatie in fence instructies – Compiler en hardware herordenen geheugenoperaties 57
Consistentiemodellen in commerciële processors • SC – SGI MIPS
• PC – Intel Pentium processor familie
• TSO – Veel Sun Microsystems machines
• Geen ordening, enkel fence instructies – Digital Alpha, IBM PowerPC, Sun Sparc V9 58
Overzicht • Sequentiële consistentie • Versoepelde consistentie • Transactional memory
59
TM: motivatie • We gaan het multi-core tijdperk in – Zie volgende les
• Huidig programmeermodel op basis van synchronisatie via locks is ontoereikend – Niet robust – Moeilijk efficiënte code te schrijven – Software met locks is niet composable
60
Locks zijn niet robust • Stel: draad 1 neemt de lock en de load operatie (ld r1,A) veroorzaakt een page fault – Zeer lange latentie – Terwijl draad 1 de lock vasthoudt
• Draad 2 blijft in spin loop → geen vooruitgang Draad 1
Draad 2
spin: cmpswp AL,1 bfail spin ld r1,A add r1,r1,1 st r1,A st 0,AL
spin: cmpswp AL,1 bfail spin ld r1,A add r1,r1,3 st r1,A st 0,AL
61
Programmeren met locks is niet eenvoudig • Coarse-grained locking – Eenvoudig te programmeren – Slechte prestatie
• Fine-grained locking – Goede prestatie – Moeilijk te programmeren
62
Software met locks is niet composable (1/2) hash tabel add(T1,item)
lock T1 item
eerst lock nemen op T1 alvorens item toe te voegen
kopieer element van T1 naar T2 delete(T1,item) add(T2,item)
lock T1
lock T2
item
item
eerst lock nemen op T2 alvorens item te verwijderen uit T1 63
Software met locks is niet composable (2/2) kopieer element van T1 naar T2 delete(T1,item) add(T2,item)
lock T1
lock T2
item
item
eerst lock nemen op T2 alvorens item te verwijderen uit T1
• Stel: we willen deze methode als interface aanbieden • Wat gebeurt er indien draad 1 een element wil kopiëren van T1 naar T2, en draad 2 van T1 naar T2? – Mogelijks een deadlock • Draad 1 neemt lock op T2, en draad 2 neemt lock op T1 • Draad 1 probeert nadien lock to nemen op T2, en draad 2 probeert lock te nemen op T1 → geen van beide maakt vooruitgang…
64
Transactional Memory: basisidee • Meerdere draden proberen gelijktijdig een kritische sectie te betreden op een atomaire manier – Indien dat lukt: prima, pas architecturale toestand aan: commit – Indien dat niet lukt: herstel de toestand zoals aan het begin van de kritische sectie (abort) en probeer opnieuw
• Programmeur specificeert de kritische secties maar zegt niet hoe dat moet gegarandeerd worden – Dat gebeurt door het onderliggende TM systeem Draad 1
Draad 2
atomic{ ld r1,A add r1,r1,1 st r1,A }
atomic{ ld r1,A add r1,r1,3 st r1,A }
65
Programmeren in TM lock (L); x++; unlock (L);
atomic { x++; }
• Dit is wat de programmeur specificeert • Het onderliggende systeem (compiler, VM, hardware, etc.) garandeert correcte uitvoering
66
Transactional Memory (1/2) • Transactie – Atomaire eenheid – Een sequentie van operaties die ofwel volledig uitgevoerd wordt (commit), ofwel geen effect heeft (abort) – Door programmeur gedefinieerd
• Gebaseerd op DBMS – Toegang tot gemeenschappelijke data zonder locks – Indien een conflict, herstel toestand, en probeer opnieuw 67
Transactional Memory (2/2) • “Alles of niets” benadering: atomicity – Bij commit, alle geheugenoperaties hebben terzelfdertijd effect – Bij abort, geen enkele schrijfoperatie heeft effect
• Transactie is geïsoleerd: isolation – Het effect van schrijfoperaties is enkel zichtbaar voor andere draden bij commit – Geeft de illusie aan programmeur van seriële uitvoering – Geen conflicterende geheugentoegangen door parallelle transacties vanuit andere draden
• Lost veel problemen van locks op: TM is robust, 68 eenvoudig te programmeren, composable
TM: schaalbaarheid • Parallelle leesoperaties tot dezelfde data – Locks laten geen meerdere lezers toe – TM wel, op automatische manier
• Parallelle lees- en schrijfoperaties tot disjuncte data – Programmeur kan fine-grain locking toevoegen • Niet eenvoudig • Niet modulair
– TM garandeert fine-grain locking op automatische manier 69
TM implementatie (1) • Data versioning – Het beheren van verschillende versies van ‘dezelfde’ data – Twee benaderingen • Eager versioning – Past geheugentoestand onmiddellijk aan; en houdt ‘undo’ log bij – Snelle commit; trage abort
• Lazy versioning – Houdt schrijfoperaties bij in buffer; past geheugentoestand aan bij commit – Trage commit; snelle abort
70
Eager versioning schrijf X ← 15
begin van de transactie draad
draad Undo Log
X: 10
geheugen
Undo X: 10 Log X: 15
commit transactie draad
abort transactie draad
Undo X: 10 Log X: 15
geheugen
geheugen
Undo X: 10 Log X: 10
geheugen 71
Lazy versioning schrijf X ← 15
begin van de transactie draad
draad Write Buffer
X: 10
X: 15 X: 10
geheugen
commit transactie
geheugen
abort transactie
draad
draad
X: 15 X: 15
Write Buffer
geheugen
Write Buffer
X: 15 X: 10
Write Buffer
geheugen 72
TM implementatie (2) • Per transactie hebben we een – een Read Set, en • Geheugenlocaties gelezen door de transactie
– een Write Set • Geheugenlocaties geschreven door de transactie
• Conflict treedt op indien ene draad een variabele leest die een andere draad wil schrijven • Conflictdetectie op basis van vergelijken Read en Write Sets 73
TM implementatie (2) bis • Conflictdetectie: twee benaderingen – Optimistische benadering • Bekijk lees- en schrijfoperaties enkel bij commit • Veronderstel dat er geen conflicten zullen zijn
– Pessimistische benadering • Bekijk lees- en schrijfoperaties tijdens uitvoering van transactie • Gebruik contention manager om te beslissen over (i) stall, of (ii) abort (restart) – Optimaliseer meest voorkomende geval
74
Optimistische detectie D1
D2 rd A
D1
D2 wr A
wr B
D1
D2
D2 rd A wr A
rd A
rd A
D1
rd A wr A
wr A
commit
wr C
commit
commit
restart commit
restart commit
rd A wr A rd A
commit commit
tijd
succes
abort
commit
succes
abort
75
Pessimistische detectie D1
D2 rd A
D1
D2 wr A
wr B
D1
D2
D2 rd A wr A
rd A
rd A
D1
rd A wr A
wr A
stall restart
wr C
commit
restart
rd A commit
rd A wr A
rd A
commit
restart
rd A wr A
commit
commit
commit restart
tijd
succes
stall
abort
geen 76 vooruitgang
Conflictdetectie • Pessimistisch + Snelle detectie van conflicten − Geen garantie voor vooruitgang; meer aborts − Fine-grain communicatie
• Optimistisch + Garantie voor vooruitgang + Potentieel minder conflicten + Coarse-grain communicatie − Trage detectie van conflicten 77
Transactional Memory • Onderwerp van huidig onderzoek • TM API • Verschillende mogelijke TM implementaties – Software – Hardware – Hybride software/hardware implementaties
• Ondersteuning in Sun Rock processor 78
