Hoofdstuk 5: Exploiting memory hierarchy Flashcards
1
Q
Address space
A
Definieert het bereik van de discrete adressen. Het bepaalt dus de hoeveelheid aan geheugen voor alle mogelijke adressen. (virtuele of fysieke)
// Aparte range van memory locaties die enkel toegankelijk is voor het programma zelf.
2
Q
Explain figure 5.1
A
Dit is de basis structuur van een geheugenhierarchie.
De gebruiker krijgt illusie van een geheugen zo groot als het grootste niveau, met de toegankelijkheid van het snelste geheugen.
3
Q
Address translation
A
= address mapping = het proces waarbij een virtueel adres gemapped wordt naar een fysiek adres, dat gebruikt wordt om toegang te krijgen tot het geheugen. Dit komt voor wanneer gebruik gemaakt wordt van het virtueel geheugen. Dit gebeurt met behulp van een page table. Het virtuele adres bestaat uit een pagina nummer en een offset. Het virtuele paginanummer wordt vertaald naar het fysieke pagina nummer en de offset wordt hier aangeplakt.
4
Q
AMAT
A
= Average memory access time
= time for a hit + miss rate * miss penalty
Deze metriek wordt gebruikt voor de performantie van caches
5
Q
Amazon web service
A
= een VM gebruikt voor cloud computing. 5 reden:
- Beschermd gebruikers tegen elkaar terwijl ze dezelfde server gebruiken
- Maakt software verdeling eenvoudiger in een warehouse-scale computer
- Makkelijk eruit stappen
- Verbergt de identiteit van de hardware, aws kan oude servers blijven gebruiken en nieuwe introduceren
- VMM controleren hoeveel de VM de processor, netwerk, geheugen ruimte verbruikt.
6
Q
Availability
A
Maat van beschikbaarheid = meeteenheid van service accomplishment rekeninghoudend met de afwisseling tussen de 2 states van accomplishment en interruption.
Availability = MTTF / (MTTF + MTTR)
met MTTF = mean time till failure en MTTR = mean time till repair
MTTF + MTTR = MTBF (mean time between failures)
7
Q
Explain figure 5.9
A
Cache waarden nadat elke aanvraag een miss is. De cache in initieel leeg met valid bits die af staan (N). Merk op dat de laatste aanvraag f de vorige waarde overschrijft, dit is een vorm van temporale lokaliteit.
8
Q
Block or line
A
Minimale eenheid van informatie die aanwezig (of niet) kan zijn in de cache. Dit is dus in een two-level hiërarchie.
9
Q
Software optimization via blocking
A
een optimalisatie om ervoor te zorgen dat alle benodigde delen in de cache passen.
Ipv. matrices te stockeren per rij of per kolom, zullen we blocked algoritmes gebruiken. Een block is een submatrix. Dit met als doel toegang tot de data in de caches te maximaliseren voordat ze vervangen moeten worden. (Temporale lokaliteit verbeteren om cache misses te verminderen)
10
Q
Cache
A
De cache is een geheugendatastructuur dat zich hierarchisch net onder de processor bevindt. Ze bevat data die net gebruikt is door het programma, zodanig dat in de toekomst die data sneller gegeven kan worden. Caches exploiteren temporele en spatiale lokaliteit via predictie. Het bevindt zich in elke processor.
11
Q
Capacity misses
A
Een vorm van cache miss. Er is een miss doordat de cache niet alle nodige blokken kan bevatten om aan de vraag te voldoen. Deze doen zich voor wanneer blocks vervangen worden en dan later terug opgehaald worden.
Deze kunnen verminderd worden door de cache te vergroten. Wanneer we de cache groter maken, moeten we ook wel opletten met het verhogen van de access time. vooral L2 caches worden groter, niet L1 caches
12
Q
Explain figure 5.10
A
Een mogelijk format voor een cache. Het toont hoe het toegewezen adres opgedeeld is in een tag veld en cache index. Het volledige adres bestaat uit 64 bits, hiervan hebben we 1 bit nodig voor het valid veld, 64-(n+m+2) voor de tag grootte, en de rest voor de data. Hier zien we dat de cache 10 woorden heeft met een block size van 1 woord, worden er 10 bits gebruikt om de cache te indexeren, en blijven er dus 52 bits voor het tag veld.
13
Q
Characteristics of a typical level 1 cache
A
vooral bezig met hit time te reduceren (zie multilevel caches)
14
Q
Check yourself p. 369
A
Geheugen hiërarchie halt voordeel uit temporale localiteit en het laagste niveau heeft de hoogste capaciteit. Bij een read hangt de teruggegeven waarde niet af van welke blok ze komen en de duurste elementen zijn niet altijd te vinden op het hoogste niveau!
15
Q
Choosing which block to replace in a cache
A
- Wanneer bij direct-mapped cache een miss voorkomt, kan de aangevraagde block maar in 1 positie geplaatst worden en dus wordt de block die in die posititie zit vervangen.
- Bij een associative cache kunnen we kiezen welke block vervangen wordt. Bij fully associative cache zijn alle blocken een mogelijke kanditaat, bij set-associative cache kunnen we kiezen tussen de blocken van de gekozen set. Hierbij zijn 2 methoden: random of LRU.
Vaak wordt bij de associative cache, de LRU gekozen (via extra bits opvolgen → hogere associativiteit, meer bits nodig, dus moeilijker) (zie def LRU)
16
Q
Explain figure 5.47
A
Geoptimaliseerde c versie van DGEMM door cache blocking te gebruiken
17
Q
Compare random versus LRU
A
- LRU = least recently used replacement scheme bij page faults. Replacement scheme waarbij de te vervangen blok diegene is die unused is voor de langste periode. Hoe meer set associativiteit toeneemt, hoe moeilijker het wordt om LRU te implementeren. → LRU te kostelijk vanaf er associativiteit komt bij kijken. Of er wordt dan gebruik gemaakt van LRU benadering, maar voor nog grotere dingen vooral wordt er gebruik gemaakt van random. LRU wordt wel altijd gebruikt in virtueel geheugen omdat daar de kost van een miss zo groot is
- Random: is eenvoudig in HW te doen en wordt vaak gebruikt voor caches en TLB’s. (wel hogere miss rate)
18
Q
Compulsory misses
A
= cold start misses
Cache misses doordat bij de eerste toegang van een blok deze blok niet aanwezig was. Dit vermindert bij grote blokken (je haalt er meer tegelijk binnen), maar grote blokken maken miss kostelijker.
19
Q
Context switch
A
= proces switch
Een verandering van de interne status van de processor om een ander proces toe te laten deze processor te gebruiken inclusief het opslaan van de status die nodig is om terug te keren naar het vorig proces.
Wanneer de OS beslist om van running process te veranderen Bv. wanneer een tijdrovende IO operatie moet uitgevoerd worden slaat het OS de staat van het process op en start een ander process. Wat moet er allemaal gebeuren? Page table register aanpassen en TLB leegmaken maar bij veel context switches is dit erg inefficiënt. Veel gebruikte oplossing is een procesidentificatie plakken aan het virtueel adres. Bv intrinsity fastmath heeft hiervoor 8 bits: Adres Space ID: zit in apart register en
wordt aan tag-deel van TLB geplakt => enkel hit indien zowel id als tag kloppen. Gelijkaardige problemen kunnen ook voor een cache voorkomen aangezien bij switch de cache data bevat van het lopende proces.
20
Q
Cost of a page fault
A
= indien het naar de disk zou zijn zou het miljoenen clock cyclussen vragen → gigantische kost: wordt zeer veel rekening mee gehouden tijdens het ontwerpen van virtual memory systems
21
Q
Cylinder
A
Dit zijn alle tracks die zich onder of boven de kop bevinden op een bepaalde plaats bij een magnetic disk.
22
Q
Explain figure 5.14
A
Locatie van een memory block met als adress 12 in een cache met 8 blocken voor direct mapped, set associative en fully associative.
23
Q
Explain figure 5.8
A
Een ‘direct-mapped’ cache met 8 entries → 3 bits als cache indexen, met adressen van woorden tussen 0 en 31 die mappen naar dezelfde cache locaties.
24
Q
Dependability
A
Dependability is een kwaliteit, het is niet kwantificeerbaar. Het idee voor dependability is redundantie. Via reliability: meeteenheid voor continu succes, availability: MTTF/(MTTF + MTTR). We kunnen dit grotendeels oplossen via de kwaliteit van onze componenten/design systemen. Fault avoidance (bv. Hamming code), fault tolerance (via redundantie), fault forecasting.
25
DIMM's
= Dual inline memory modules
| Dit is geheugen voor servers: 4-16 DRAMs (elks 8 bits breed normaal) (subset van een chip = memory rank)
26
Virtual address
= een adres dat naar de locatie wijst in een virtuele plaats en dat vertaald wordt via address mapping naar een fysiek adres wanneer het geheugen is geaccessed. Een virtueel adres is nodig zodat 2 verschillende programma’s dat dezelfde data nodig hebben deze kunnen delen (meerdere virtuele adressen kunnen naar 1 fysiek adres wijzen)
27
Direct-mapped cache
Een cache structuur waarbij elke geheugenlocatie gemapped wordt naar exact 1 locatie in de cache. Hierdoor is het gemakkelijk en snel om in de cache te zoeken en te zien of het erin zit. Het tag veld bepaalt waar het blok in de cache wordt geplaatst. Een valid bit geeft aan of de inhoud van het cache blok geldig is. Nadeel: blok kan maar op 1 plaats in geheugen dus soms veel competitie voor dezelfde block en soms blokken leeg/zeer weinig gebruikt.
De mapping tussen adressen en cache locaties is simpel een vaak wordt de volgende mapping gebruikt voor het vinden van een blok:
(block adres) modulo (number of blocks in cache)
(#bits = 2𝑛 (block size+tag size+valid field size) = 2^𝑛(2^𝑚⋅32+(64−𝑛−𝑚−2)+1)
2 alternatieven zijn fully associative en set asociative.
Fully associative: Elk blok uit geheugen kan in elk slot in cache. Voordeel: Heeft niet het nadeel van direct mapped. Nadeel: Bij elke blok toegang moet
de hele cache doorzocht worden: alle tags vergelijken tot juiste gevonden, in parallel om hit time te verlagen, duur in HW. Wordt vaak gebruikt als de kost van een miss groot is.
Set associative: tussen vorige 2 in, blok uit geheugen kan in beperkte verzameling slots in cache, de set word bepaald door index-bits, tags in set worden in parallel vergeleken. Verkleint miss-rate maar vergroot hit time. Grootste winst van direct naar 2-way-set-associatief. #sets verdubbelen: index 1 bit minder, tag 1 bit meer. Extra kost in HW voor parallel vergelijken,
mogelijke vertraging hierdoor of door multiplexer op het einde keuzes te vervangen blok via LRU of random indien misses goedkoop.
28
Write buffer
Bij write-through: een buffer die data bijhoudt terwijl het aan het wachten is om in het geheugen geschreven te worden. Is een oplossing om write-through sneller te maken zodat het programma niet moet wachten tot de data in het geheugen geschreven is voor er verder gegaan kan worden. Indien een write buffer toch vol is, krijg je wel terug stall → rate of generating stalls lager dan completing (let op! Kunt nog steeds stalls bekomen als ze in ‘burst’ voorkomen → oplossing: dieper maken van de buffer)
Bij write-back: buffer voor vuil blok tijdens read van nieuw blok
29
Dirty bit
Een dirty bit wordt gebruikt om bij te houden of een pagina is geschreven sinds het in het geheugen is geplaatst. Het wordt samen met de valid en ref bit in de page table geschreven.
30
Disk
Een magnetische disk is een geheugenopslagplaats die nonvolatiel is. Dat betekent dat als hij geen stroom heeft hij toch nog het geheugen bijhoudt. Het wordt gebruikt voor permanente opslag van gegevens. Het bestaat uit draaiend platen met een magnetisch oppervlak met daartussen een schrijf/lees kop. Het schrijven en lezen van informatie op zo een disk is zeer traag. De access time is typisch 5 tot 20 milliseconden.
Er wordt in drie stappen gewerkt om aan de data te geraken.
1. de lees- en schrijfkop op de juiste track plaatsen. De tijd die men daarover doet noemt men seek time.
2. Wachten tot de juiste sector zich onder de schrijf- en leeskop bevindt. Dit noemt men de rotational delay of rotational wachttijd.
3. de transfer van de data. Deze tijd noemt men de transfer time. Dan als laatste is er ook de disk controller die alles coördineert (controller time).
Dus de tijd om een I/O operatie uit te voeren is al deze 4 tijden optellen + de tijd om te wachten op een ander process als die de disk al gebruikt. De grootte van de disk maakt niet uit voor performance. Wat wel uitmaakt is de external interface.
3 grote verschillen tussen een magnetic disk en een main memory:
- Disk is niet volatiel want het is magnetisch
- Disks hebben een tragere access time omdat het mechanical devices zijn
- Disks zijn goedkoper per gigaByte omdat ze een hoge opslag capaciteit hebben voor een kleine kost
31
Double data rate SDRAM
Dit is de snelleste versie van een SDRAM waarbij data transfers gebeuren op zowel de rising en faling edge van de klok → 2x bandwidth. De S staat voor synchronous en dat wil zeggen dat de DRAM zelf een klok heeft zodat de tijd die nodig is om het geheugen en processor te synchroniseren geelimineerd wordt.
32
Explain figure 5.11
Miss rate VS block size
We zien dat de miss rate verlaagt indien we onze blokken vergroten. We zien echter ook dat onze blokken te groot kunnen worden, indien hun grootte een significante fractie is van de cache grootte. . Dit komt doordat het aantal blokken dat in de cache kan gehouden worden te klein zal zijn waardoor het te
‘competitief’ wordt.
!Let op: hoe groter de blokgrootte, hoe lager de miss rate, maar de miss penalty stijgt wel!
33
Check yourself p.390
Hoe Kleiner de latency, hoe kleiner de cache blok. Hoe hoger de bandbreedte, hoe breeder de cache blok
34
Failure
Een transitie van service accomplishment (waar de service geleverd wordt zoals gespecifieerd) naar service interruption (waar de geleverde service anders is dan de gespecifieerde service) worden veroorzaakt door failures. Kunnen permanent of intermittent zijn.
restorations (transitie van service interruption naar service accomplishment)
35
Fault avoidance
Voorkomen van fouten via constructie (dependable). Dit is een van de manieren om mean time till failure te verbeteren (dus te verhogen). Alternatieven zijn fault tolerance en fault forecasting.
36
Conflict misses
Een cache mis, in een set-associative of direct mapped cache, wanneer meerdere blokken ‘strijden’ voor dezelfde set en geëlimineerd worden bij fully associative cache van dezelfde grootte.
Dit wordt verminderd bij hogere associativiteit, maar dit kan dan wel hit-tijd vergroten.
37
Fault forecasting
De aanwezigheid/het ontstaan van fouten voorspelle, zodat de component vervangen kan worden voor het faalt (dependable). Dit is een van de manieren om mean time till failure te verbeteren (dus te verhogen). Alternatieven zijn fault avoidance en fault tolerance.
38
Fault tolerance
Ondanks een fout werkt het systeem toch naar behoren dankzij redundantie. Dit is een van de manieren om mean time till failure te verbeteren (dus te verhogen). Alternatieven zijn fault avoidance en fault forecasting.
39
Finite state machine
= multi-step controle methode. Het wordt gebruikt om bijvoorbeeld de verschillende states van een proces weer te geven. Het bestaat uit toestanden en toestandsveranderingen. De huidige toestand en inputs bepalen de volgende toestand (= volgende-toestand-functie) en deze werkt bij elke kloktik. Elke toestand bepaalt een aantal controlesignalen die gezet worden, alle andere worden afgezet.
Er zijn twee belangrijke toestanden:
- idle: deze state wacht op een valid read of een write request van de processor, waardoor de FSM naar de cmpare tag status gaat
- Compare tag: checkt of de request read or write een hit is of een mis. Het index gedeelte van een adres selecteert de tag die vergeleken moet worden.
(Als de data in de cache blok aangeduid met het deel van de index van het adres geldig is en het tag gedeelte van het adres overeenkomt met de tag,
dan is de requested write of read een hit. Ofwel worden de gegevens gelezen van het geselecteerde woord ofwel geschreven naar het geselecteerde woord en het Cache Ready signaal wordt ingesteld. Als het een write is, wordt de dirty bit op 1 gezet. Merk op dat een geschreven bit ook de valid bit en het tagfield instelt. Hoewel het overbodig lijkt, is het inbegrepen omdat de tag een single memory is, dus om een dirty bit te veranderen moeten we ook de valid en de tag velden wijzigen. Als het een hit is en het block is valid dan keert de FSM terug naar de idle state. Een Miss update eerst de cache tag en gaat dan ofwel naar de write-back staat, als het blok in deze plaats een dirty bit waarde van 1 had of aan de Allocate state als het 0 is.
• Write-back
• Allocatie)
40
Cache miss
Een aanvraag voor data uit cache die niet aanwezig is in de cache. De controle unit moet het detecteren en de gevraagde data (uit het geheugen) in de cache brengen. (zorgt voor een pipeline stall want we moeten wachten op het geheugen, tenzij we out-order processors gebruiken, deze staan de executie van instructies toe tijdens het wachten).
Je hebt verschillende soorten cache misses: compulsory, capacity en conflict misses.
41
Flash (memory)
Een elektrische non-volatile opslag medium dat herschreven kan worden. Het is een niet volatiel halfgeleidend geheugen. Het wordt gebruikt in GSMs en laptops. Het heeft dezelfde bandbreedte als disks maar heeft een toegangstijd die 100 tot 1000 keer groter is dan bij disks en het is ook meer resistent tegen schokken, meer power efficiënt en veel kleiner dan disks. Het is wel duurder in kost per gigabyte. Groot nadeel aan flash memory is dat de bits gaan slijten. Dit is niet het geval bij magnetic disks en DRAM. Daarom is er ook geen write limit bij DRAM, deze is er wel bij flash memory. Om hiermee om te gaan, gaan controllers blokken van informatie die heel vaak geschreven worden verspreiden op minder vaak betreden blokken. Deze techniek noemt men wear leveling. Wat ze nu doen is laptops combineren met disks en flash geheugen. Ze booten vanaf een flash geheugen. Deze verbruikt minder stroom en heeft een snellere access time dus het opstarten zal sneller gaan. Er zijn 2 soorten flash memory. Er is de NOR flash en de NAND flash. De NAND flash heeft een grotere opslag densiteit maar het geheugen kan alleen maar lezen en schrijven in blokken.
42
Fully associative cache
Een cache structuur waarin de blokken in eender welke locatie kunnen staan. (enkel praktisch voor caches met een klein aantal blokken). Een alternatief is direct-mapped cache (heeft niet het nadeel van direct-mapped). Het nadeel van fully associative cache is dat bij elke blok toegang de heel cache moet doorzocht worden: alle tags vergelijken tot juiste gevonden, in parallel om hit time te verlagen, duur in HW. Het wordt vaak gebruikt als de kost van een miss groot is.
Nog een ander alternatief is set associative.
43
Explain figure 5.12
Een 16 KiB cache van de FastMath, met 256 blokken met elks 16 woorden per blok. De adres grootte is slechts 32 bits. Tag field 18 en index 8 en index 4.
44
Handling cache misses
1) stuur orginele PC naar geheugen
2) instruct main memory om een read te doen op de disk
3) schrijf cache entry
4) keer terug naar originele PC
45
Handling cache writes
Er zijn 2 manieren om caches te updaten bij een store instruction:
- Write through met write buffer: simpel, maar slechte performantie
- Write back: betere performantie zeker als processor snel writes kan genereren, wel meer complex
46
Characteristics of a typical level 2 cache
Vooral bezig met miss rate te reduceren. (zie multilevel caching)
47
Hit rate
The fractie van de memory accesses gevonden in een niveau van het geheugenhiërarchie. Het wordt vaak gebruikt als een maatstaf voor performantie van het geheugenhiërarchie.
miss rate = 1 - hit rate
48
DRAM
= Dynamic random acces memory
DRAM is volatiel. Het is goedkoper en trager dan SRAM. DRAM bevat het hoofdgeheugen. De waarde wordt bewaard als een lading in een condensator. Elke bit gebruikt 1 transistor. Deze bit wordt verstoord bij het lezen
- een gelezen geheugenplaats moet herschreven worden, daardoor is cycle time groter dan access time
- bit heeft regelmatig 'refresh' nodig of anders verleis het zijn informatie, daarom heeft het dynamisch
49
Explain figure 5.27
= De pagina table voor een met de virtuele pagina nummers om de corresponderende fysieke pagina nummers te vinden.
50
Explain figure 5.39
De 4 statussen voor een cache controller. (kan uitgebreid worden voor verbeteringen performantie)
- Idle: wacht voor een read of write request van de processor.
- Compare tag: kijkt of de aangevraagde data een hit of een miss is.
- Write-back: schrijft het 128-bit blok naar het geheugen via een adress bepaald door de tag en cache index.
- Allocate: nieuwe blok wordt gehaald uit het geheugen.
51
Hit time
Tijd nodig om in het hoogste niveau van de hiërarchie te komen, inclusief de tijd die nodig is om te bepalen of het een hit of een mis was. Dit is belangrijk om de performantie van het geheugenhiërarchie te bepalen.
52
How is a block / page found?
= via de page table in main memory. Elk programma heft zijn eigen page table.
53
How to calculate cache performance
CPU-time kan onderveeld worden in CPU execution clock cycles en memory-stall cycles. Die laatste komen voornamelijk voort uit cache misses. We gaan ervan uit dat dit het geval is. Memory-stall clock cycles kunen verder opgedeeld worden in read-stall cycles en write-stall cycles. Write buffer stalls hangen niet enkel af van de frequentie maar ook van de nabijheid van writes. Gelukkig zijn deze klein in een systeem met een degelijke write buffer diepte en een geheugen dat writes voldoende snel kan accepteren, zodat we deze kunnen negeren. Er zijn 2 technieken om cache performance te verbeteren. De ene focust op het
verkleinen van de miss rate door de kans dat 2 verschillende geheugenblokken dezelfde cache locatie willen claimen te reduceren. De andere reduceert de miss penalty door een niveau toe te voegen aan de
geheugenhiërarchie (= multilevel caching)
- CPU time = (CPU exec. Clock cycles + memory-stall clocksycles) * clock cycle time
- Memory-stall cycles = (read-stall cycles + write-stall cycles)
- Read-stall cycles = reads/program*read miss rate*read miss penalty
- Write-stall cycles= (writes/program*write miss rate*write miss penalty) + write buffer stalls
- Memory stall clock cycles = memory acces/program * miss rate * miss penalty
- Memory-stall clock cycles = instructions/program * misses/instruction * miss penalty
54
Virtual machine
Algemeen is de definitie: alle emulatie (= simultaan vertalen) methodes die een standard software interface aanbieden bv. Java VM.
Hier bedoelen we met virtuele machine een host computer die een gast OS en zijn resources tot op ISA niveau emuleert. De hardware heeft zelfde ISA als ge-emuleerde systemen. Verschillende gebruikers kunnen wel verschillende OS’en hebben. Is een oud idee met vernieuwde interesse doordat isolatie en beveiliging steeds belangrijker is (bv cloud computing), huidige OS’en niet veilig en reliable genoeg, laat het delen van een machine tussen verschillende gebruikers toe en door snelle processoren is processing kost minder belangrijk (Moore).
Virtuele machines creëren de illusie dat gebruikers een hele machine, inclusief OS, voor zichzelf heeft.
Voordelen:
- verschillende OS'en
- een OS kan crashen, maar de rest niet
- 1 OS met applicatie kan verhuizen: load balancing
55
Explain figure 5.18
= de implementatie van een 4-set-associatieve cache met 4 vergelijkers (bepalen welk element van de set de juiste tag heeft) en een 4-to-1 multiplexor (zegt uit welk blok in de set de match komt).
56
Index field
Deel van een cache adres dat wordt gebruikt om een blok te selecteren (bepaalt in welke blok van de cache gezocht moet worden). 2^n blokken, n bits nodig voor de cache
57
Explain figure 5.26
= mapping van een virtueel adres naar een fysiek adres.
58
Kernel mode
= supervisor mode
een mode om aan te duiden dat een proces een operating system proces is. Dit is nodig voor protectie in het virtueel geheugensysteem.
59
Levels in the memory hierarchy
Hoe verder van de processor, hoe lager het niveau, hoe groter het bereik van de opgeslagen data, maar hoe trager voor de processor. Cache is het hoogste niveau en magnetic disk het laagste.
60
Locality
Programma benutten enkel een kleine portie van hun address space op elk ogenblik. Er zijn 2 verschillende types van localiteit:
- temporeel (zie def): localiteit in tijd
- ruimtelijk (zie def): locailiteit in ruimte
61
Locating a block in a cache
Voor set-associative hebben we 3 velden:
- Tag: dit wordt gebruikt om in de set te vergelijken, het geeft heeft block adres. De tag van elke cache block in de geschikte set wordt gecheckt om te zien of deze overeenkomt met het block adres van de processor (daalt in 1 bit als associativiteit met 2 verhoogt)
- Index: de juiste set te vinden (stijgt met 1 bit als associativiteit met 2 verhoogt)
- Block offset: plaats gezochte woord in blok
(Trivial voor direct-mapped)
Bij fully associative: geen index → 1 set
Bij direct mapping: maar 1 comparator nodig
➔ Keuze hangt af van kost op een miss vs. kost van het implementeren associativiteit (in tijd en hardware)
62
Logical address
Het adres waarop een item verblijft vanuit het perspectief van een uitvoerend applicatie programma. Is verschillend van een fysisch adres door de operatie van een adres/mapping functie.
63
Explain figure 5.15
De verschillende manieren voor de structuur van een cache: direct-mapped (links boven), n-set-associative (recht boven n=2 blocks/set + midden n=4 blocks/set) en fully associative (onder)
64
LRU algorithm
= Least recently used
Een vervangingsschema dat gebruikt wordt bij associative cache om te kiezen welke block vervangen wordt. Bij dit algoritme is de te vervangen blok degene die het langste niet meer gebruikt is, men houdt dus bij welke blok het langste niet is gebruikt. Het kost extra bits om dit bij te houden dus dit wordt zelden gebruikt. Men kan ook een benadering gebruiken. Soms heeft HW een use of reference bit, SW gaat dan regelmatig al de bits na en kopieert ze of zet op 0. De kost van LRU moet afgewogen worden tegen de kost van een miss. (enkel nodig bij associatieve caches)
65
cold start misses
= compulsory miss: Cache misses doordat bij de eerste toegang (=koude start) van een blok deze blok niet aanwezig was. Dit vermindert bij grote blokken (je haalt er meer tegelijk binnen), maar grote blokken maken miss kostelijker.
66
Memory hierarchy
Een structuur van meerdere levels van geheugen, hoe verder van de processor, hoe groter, maar trager, het geheugen wordt. De snelste geheugens zijn duurder per bit en dus kleiner. Het doel van een geheugenhiërarchie te gebruiken is om een groot geheugen aan te bieden aan de snelheid van het snelste geheugen en aan de prijs van het grootste geheugen.
Geheugenhierarchie trekt voordeel uit temporal localicty door de meest recente geaccesseerde data items dicht bij de processor te houden. Het trekt ook voordeel uit spatial locality door blokken die meerdere aaneengesloten woorden in het geheugen bevatten te verplaatsen naar hogere levels.
67
Memory stall clock cycles
Stall die nodig is wanneer er een cache miss optreedt
Indien de read en write miss penalties hetzelfde zijn, en we de write buffer stalls verwaarlozen:
Memory-stall clock cycles = memory access/program * miss rate * miss penalty
= instructions/program*misses/instruction*miss penalty
68
Miss penalty +
De tijd dat nodig is om een block te verplaatsen van een lager naar een hoger niveau in de hiërarchie + de tijd om deze block naar de processor af te leveren. Dit gaat sneller door eventueel gebruik te maken van banken. Er zijn verschillende methoden om miss penalty te verkleinen:
- early start: zodra het woord arriveert, herstarten en niet wachten tot heel blok in cache geschreven is (veel gebruikt voor instructie caches en minder effectief voor data caches)
- requested word first: eerst woord halen, dan hele blok halen en schrijven in cache.
69
MTBF
Mean time between failures. MTBF = MTFF + MTTR → availability = MTTF/(MTTF+MTTR)
70
Multilevel caches
Een cache techniek waarbij we de miss penalty willen verkleinen door extra cache niveaus toe te voegen aan de hiërarchie. Het geheugenhierarchie heeft dus meerdere niveau's van caches ipv alleen een cache en een hoofdgeheugen.
Dit second-level cache bevindt zich normaal op dezelfde chip en wordt geaccessed wanneer er zich een mis voordoet in de primaire cache. Als de second-level cache de data bevat, is de miss penalty voor de primaire cache gelijk aan de access time van de second-level cache ( tijd om 2de cash te lezen.). Dit is vaak veel korter dan de access time van main memory.
Indien 2de cache het niet bevat moet wel naar main memory → grotere miss penalty dan voordien. 2de niveau heeft vaak grotere blokgrootte en een hogere graad van associativiteit
Bij multilevel caches zal de focus bij verschillende levels anders liggen.
- level 1: aandacht voor kleine hit tijd (klok cyclus klein)
- -> kleinere cache en kleinere blokken
- level 2: aandacht voor miss rate
- -> grotere caches, grotere blokken
71
Explain figure 5.28
= Page table mapt elk virtueel adres naar of een fysiek adres of een adres op de disk. De virtual page number wordt gebruikt om de page table te indexeren.
72
Explain figure 5.3
Niveaus van de geheugenhiërarchie, waarbij de laagste levels het grootste zijn, maar verder van de CPU, waardoor de acces time groter wordt. Het toont dat de geheugenhiërarchie kleinere en snellere geheugens gebruikt dicht bij de processor.
73
Next-state function
combinationele functie dat, gegeven de inputs en huidige status, de volgende status van een finite-state machine bepaalt
74
Nonblocking cache
Een cache dat toelaat dat de processor een referentie naar de cache kan maken, terwijl de cache een voorgaande mis aan het fixen is. (optimalisatie om de miss penalty te reduceren)
75
Page fault
Page = block in virtual memory,
page fault = indien een accessed page niet in het geheugen zit. Het is dus een event bij virtuele geheugens dat gebeurt als een gezochte pagina niet aanwezig is in het primaire geheugen, equivalent aan een miss in caches. Het is zeer kostelijk want secundair geheugen is meestal veel trager, dus wordt er zoveel mogelijk gedaan om het aantal page faults te beperken.
76
Explain figure 5.19
Vergelijking tussen quicksort en radix sort. We bekijken instructies uitgevoerd/element gesorteerd, tijd/element gesorteerd, en cache misses/element gesorteerd. ^We kunnen uit 1) concluderen dat radix minder operaties nodig heeft. Uit 2) zien we dat het toch meer clock cycly nodig heeft en divergeert van de quicksort, maar wrm? 3) laat zien wat er gebeurt in 2: quicksort heeft veel minder misses/element dan radix.
77
Write through
Een manier om writes altijd te updaten in zowel het geheugen als de cache. Het verzekerd de consistentie tussen de twee ten allen tijde. Bij write-miss: blok lezen en plaatsen in cache, dan woord overschrijven en dan in hoofdgeheugen schrijven. Dit is traag want bij elke write toegang heb je het hoofdgeheugen nodig, want data moet ook naar het hoofdgeheugen geschreven worden (oplossing is write buffer).
Een alternatief is write back
78
Physical address
= een adres in de main memory. Virtual memory implementeert de vertaling van een programma’s adres space naar een fysiek adres. Dit beschermt het adres van andere VMs.
79
Popularity of virtual machines
Populariteit is enorm gestegen, redenen:
1) Belang van isolatie en beveiliging in moderne systemen
2) Falen van beveiliging en betrouwbaarheid van standaard operating systemen
3) Het delen van 1 computer tussen meerdere onverwante users (voor cloud computing)
4) Dramatische verbetering in de raw speed van een processor → overhead van virtuale machines meer acceptabel
5) Managing software: abstractie die alle OS kan runnen (zelfs de zeer oude)
80
Prefeching
Een techniek waarbij data blokken die nodig zijn in de toekomst al in de cache worden gestoken door speciale instructies te gebruiken die het adres van het blok specificeren. (prediction)
81
Explain figure 5.21
= cache blocked versie van DGEMM.
82
Privilege level
Zodat gebruikers processen andere niet kunnen beïnvloeden: user mode vs kernel mode. (kunnen er nog veel meer zijn).
83
Reference bit
= use bit of access bit: een veld dat ingesteld wordt wanneer men toegang krijgt tot een pagina en dat gebruikt wordt om LRU of andere replacement schemes te implementeren. (voor een benadering van LRU, aangezien dit te duur is om accuraat te volgen)
84
Relationship cache misses and associativity in cache
Hoe hoger de associativiteit, hoe lager de kans op cache misses, maar er is wel een toename in de hit time.
85
Reliability
Maat van bereiken van continue werking (waarbij service geleverd wordt zoals gespecifieerd). MTTF (mean time to failure) of AFR (annual failure rate) zijn reliability measures.
86
Restartable instruction
instructie waarbij de exception geen invloed heeft gehad op de herstarte instructie nadat de expection is opgelost. Dit is wat moet gebeuren bij page fault exceptions.
87
Virtual machine monitor (VMM)
= software die een VM ondersteunt en het mogelijk maakt om virtuele machines te runnen. Veel kleiner dan een traditionele OS. De VMM mapt virtuele resources op fysische resources.
Kwalitatieve eisen:
- De ‘guest’ software moet exact runnen op de VM alsof het op de eigen computer runt. (exclusief performantie gerelateerde zaken)
- ‘guest’ software mag geen directe veranderingen maken aan de allocatie van het echte systeem
88
Rotational latency
De tweede stap om toegang te verkrijgen tot data op een magnetic disk is het wachten tot de juiste sector zich onder de schrijf- en leeskop bevindt. De tijd die hiervoor nodig is, is de rotational latency. Vaak is dit de helft van de rotatietijd.
89
SDRAM
= Synchronous DRAM
Toevoeging van een klok zodat er geen synchronistatie meer nodig is tussen het geheugen en de processor. (= bits overbrengen zonder extra address bits te moeten specificiëren.)
90
Sector
Elke track op een magnetische disk bestaat uit een aantal sectoren. Vaak 100 tot 500 sectoren per track.
Het is de kleinste hoeveelheid data dat gelezen/geschreven kan worden op een disk.
91
Explain figure 5.31
De TLB (translation-lookaside buffer) en cache implementeren het proces om van een virtueel adres naar een data item te gaan in de Intrinsity FastMath. (voor een read)
92
Seek time
De eerste stap voor data access op een magnetische disk is seek, dat is de de positionering van de head over de juiste track. De tijd die nodig is om de head over de juiste track te positioneren is de seek time.
93
Segmentation
= een mapping schema voor een adres met variabele grootte waarbij een adres bestaat uit 2 delen: segment nummer (mapped tot een fysiek adres) en een segment offset (optellen bij segment nummer voor het feitelijke fysieke adres te vinden)
➔ Wordt gebruikt om sterkere methode voor bescherming en delen van adres ruimte te hebben.
94
Set-associative cache
Een cache structuur waarbij er een vast aantal locaties zijn voor een blok (tussenin direct-mapped en fully associative), dus blok uit geheugen kan in beperkte verzameling slots in cache. Een set-associative cache met n locaties voor een blok wordt een n-way set-associative cache genoemd. Een n-way set-associative cache bestaat uit een aantal sets dat elk bestaat uit n blokken. Elke blok wordt gemapt naar een unieke set in de cache gegeven door het index veld, en een block kan dan in eender welk element in deze set geplaatst worden. Het combineert dus direct-mapped en fully associative: een block wordt rechtstreeks gemapt in een set en dan worden alle blocken in de set onderzocht voor een match.
In zo'n cache wordt de set die de block bevat gegeven door:
(block number) modulo (number of sets in cache)
Door de associativiteit te vergroten verklein je de miss rate, je hebt wel een potentiële verhoging van de hit time.
95
Size of tags VS set associativity
Hoe hoger de associativiteit, hoe meer vergelijkers en meer tag bits er nodig zijn.
96
Miss rate
De fractie van de memory accesses dat niet in een niveau van de hiërarchie wordt gevonden.
miss rate = 1 - hit rate
97
Explain figure 5.38
Finite-state machine controller: blok van combinationele logica en een register voor d ehuidige status.
98
Page table
Omdat een page fault heel kostelijk is, is de gebruikte implementatie bij virtuele geheugens bijna uitsluitend volledig associatief. Maar zoeken daarin is kostelijk, de oplossing is een pagina-tabel. Het is een tabel die pagina's indexeert in main memory. De index komt voort uit het paginanummer van een virtueel adres. Het heeft ook een valid bit omdat het ook kan verwijzen naar pagina's die nog in secundair geheugen zitten. De index komt voort uit het paginanummer van een virtueel adres. Hiervoor heeft de hardware een register nodig dat naar het begin van de page table wijst. = page table register.
De OS is verantwoordelijk voor de pagina tabel.
99
Spatial locality
localiteitsprincipe gebaseerd op de assumptie dat als een data locatie wordt gerefereerd, de data locaties in de buurt in de nabije toekomst zullen gerefereerd worden. Programma's tonen hoge spatial locality omdat instructies normaal sequentieel geacesseerd worden.
100
explain figure 5.2
Elk paar in de geheugenhiërarchie heeft een boven niveau en een onderniveau. Tussen elk level is de eenheid van informatie aanwezig of niet een block of lijn. Wanneer we een koppie maken tussen 2 niveaus doen we dit door een hele blok te kopiëren.
101
Split cache
Een manier waarbij een niveau van de hiërarchie bestaat uit 2 onafhankelijke caches die in parallel werken, 1 voor data en 1 voor instructies.
102
SRAM
= Static random acces memory.
Dit is volatiel en heel snel. Levels dicht bij de processor (caches) gebruiken SRAM. Het is sneller maar ook duurder dan DRAM. SRAMs hebben een fixed acces time (wel verschil tussen read en write). Geen nood om te refreshen dus de acces time is min of meer gelijk aan de cycle time.
103
Supervisor mode
= kernel mode: een mode om aan te duiden dat een proces een operating system proces is.
104
Swap space
= de ruimte die op een disk gecreëerd wordt door de OS bij het opstarten van een proces voor alle virtuele pagina's van het proces. De OS creëert ook een datastructuur om bij te houden waar elke virtuele pagina op de disk gestored wordt, maar logisch gezien maar 1 tabel in totaal.
Wanneer een valid bit voor een virtual page op off staat, gebeurt er een page fault. Dan krijgt het operating system de controle. Dit gebeurt door een exception mechanisme. Als het operating system de controle heeft moet het de page zoeken in het volgende level van de hierarchie (dus meestal de magnetic disk) om de beslissen waar de page moet geplaatst worden dat juist gevraagd is. Het virtuele adres zegt niet alleen waar de page staat op de disk. Aan de hand van een titel van een book weten we nog niet waar hij ergens staat in de bib. Hiervoor moeten we dus zoeken in een cataloog om zo te weten op welke plank hij staat. in een virtueel geheugen
systeem moeten we dus ook de locatie bijhouden op de harde schijf van elke pagina in de virtuele adresruimte. We weten op voorhand niet of een page in het geheugen wordt verplaatst. Dus de operating system creëert een space op de disk voor alle pages van een proces wanneer het proces gecreëerd wordt. Deze disk space wordt swap space genoemd.
105
MTTF
= Mean time till failure: een maateenheid van reliability. We willen dat deze zo groot mogelijk is. Kan verbeterd worden door
- fault avoidance (fault = failure van een component): het voorkomen van het optreden van een fault bij constructie
- fault tolerance: redundantie gebruiken zodat de service toch nog overeenkomt met de service specificatie alhoewel er faults optreden
- fault forecasting: het voorspellen van de aanwezigheid en creatie van faults, waardoor je het onderdeel kan vervangen voor het faalt
106
System call
Een speciale instructie waardoor de processor van user mode naar supervisor mode kan gaan.
In RISC-V heet deze instructie ecall. PC wordt bewaard in SEPC
107
Explain figure 5.22
De implementatie van blocking op het DGEMM
108
Explain figure 5.33
Mogelijke combinaties in een TLB, virtueel systeem en cache.
109
System mode
= kernel mode/supervisor mode?
110
Tag field
Een veld dat gebruikt wordt in een tabel voor een hiërarchie dat de adressen bevat, nodig om te checken of de geassocieerde blok correspondeert met het gevraagde woord. Een cache bevat tag velden.
111
Temporal locality
Localiteitsprincipe gebaseerd op de assumptie dat als een data locatie wordt gerefereerd, het in de nabije toekomst nog eens gerefereerd zal worden. De meeste programma's bevatten veel loops wat betekent dat instructies en data waarschijnlijk herhaaldelijk worden geaccessed.
Het andere localiteitsprincipe is spatial locality.
112
The 3 C's
Cache model waarbij alle cache misses geclassificeerd worden in 3 categoriën:
Compulsory misses
Capacity misses
Conflict misses (= collision miss)
Dit model is handig om inzichten te verkrijgen in de performantie van cache designs.
113
TLB
= Translation-lookaside buffer
In virtueel geheugen moet eerst in de paginatabel het fysisch adres opgehaald worden en dan de eigenlijke gegevens ophalen. Dit betekent dus dat elke geheugentoegang minstens 2 keer zo lang de tijd neemt.
De oplosing is TLB = een cache die recent gebruikte adres mapping bijhoudt om toegang tot de page table te vermijden. (= recently used translations bijhouden).
De TLB moet ook extra bits hebben (valid, dirty en reference) want bij hit gaan we niet naar paginatabel, deze bits moeten weggeschreven worden in paginatabel.
Het is een cache in de CPU dat gedeeltes van de page table bevat die omgezet worden van virtuele naar fysieke adressen. De TLB heeft een vast aantal ingangen en wordt gebruikt om de snelheid te verhogen van de virtuele adres omzetting (dankzij zijn SRAM geheugen). Elke ingang in de TLB bestaat uit twee delen: een key (of tag) en een waarde. Als het associatieve geheugen een item krijgt, wordt dit vergeleken met alle keys tegelijk. Als het item wordt gevonden, wordt de bijhorende waarde teruggegeven. Zoeken naar items gaat hiermee snel, maar de hardware is duur (vandaar de kleine ruimte, en dus beperkt aantal items dat de TLB kan opslaan). Het aantal ingangen ligt meestal tussen de 64 en 1024 items.
De TLB wordt als volgt gebruikt: de TLB bevat een paar ingangen van de page-tabel: als een logisch adres wordt gegenereerd door de CPU gaat het page-nummer naar de TLB. Als het page-nummer wordt gevonden, is het framenummer onmiddellijk beschikbaar om het geheugen te benaderen. Als het page-nummer niet in de TLB staat, wordt er verwezen naar de page-tabel (dit noemenwe een TLB-miss). Als het framenummer is opgehaald, wordt het geheugen benaderd (als het niet in de page-tabel staat wordt er een page fault exception afgevuurd). Daarna worden dat page-nummer en framenummer in de TLB geplaatst, zodat ze sneller worden gevonden bij de volgende verwijzing. Als de TLB al vol is, vervangt het besturingssysteem een ingang. Het vervangingsbeleid varieert van least recently used (LRU) tot random (afhankelijk van de implementatie in het besturingssysteem). Ook kunnen er sommige TLB-ingangen vastgelegd worden, zodat ze niet verwijderd kunnen worden, voor kernelcode. Het percentage dat een page-nummer wordt gevonden in de TLB is de TLB hit ratio. Een hit ratio van 70 procent betekent dat we het gewenste page-nummer 70 procent van de keren in de TLB terugvinden. Een hoge hit ratio is cruciaal voor de snelle verwerking van gegevens, immers duurt het veel langer om de juiste data terug te vinden bij een TLB-miss dan dat het direct beschikbaar is.
114
Explain figure 5.23
= de performantie voor DGEMM voor unoptimized vs blocked voor een variateit aan dimensies voor de matrices.
115
To virtualize the processor
De VMM moet alles controleren, ondanks de guest VM en OS hem aan het gebruiken is.
➔ 2 processor modes nodig: user en system
➔ Een ‘priviliged’ subset van instructies die enkel in systeem mode toegankelijk zijn.
116
Track
Een disk bestaat uit een stapel ronde platen. Elke plaat wordt opgedeeld in concentrische cirkels, nl. tracks. Vaak zijn er 10 000'en tracks per oppervlak. Tracks worden nog eens opgesplitst in sectoren.
117
User mode
= de mode op een processor voor de gebruiker. De instructies zijn beperkt zodat de gebruiker geen rechtstreekse aanpassingen kan maken aan de allocatie van het systeem (Dit is nodig voor protectie in het virtueel geheugensysteem)
118
Explain figure 5.32
Read/write through voor de Intrinsity FsatMath voor een TLB en een cache.
119
Valid bit
Een cache bevat een valid bit, het wordt ook gebruikt in een pagina table. Het is een veld in de tabellen van een geheugenhiërarchie dat aanduidt dat de geassocieerde block in de hiërarchie de juiste data bevat. (weten of de tag genegeerd moet worden, gebeurt indien een cache entry leeg is)
120
Explain figure 5.30
TLB die zich gedraagt als een cache van de page table voor entries die enkel naar fysieke pages mappen.
121
Check yourself p.409
First level caches zijn meer bezig met hit time, en second level met miss rate.
122
Virtual memory
Dit is een techniek dat de main memory als een cache gebruikt voor een tweede opslag. Er zijn 2 redenen waarom we virtueel geheugen gebruiken:
➔ Efficiënt en veilig delen van geheugen over meerdere programma’s
Om toe te laten dat meerdere virtuele machines hetzelfde geheugen delen, moeten we de virtuele machines van elkaar beschermen. Het is ook een techniek om de performance te verbeteren. Het virtueel geheugen zorgt ervoor dat we de processor en het main geheugen makkelijk kunnen delen. We weten wel niet welk programma geheugen deelt met andere programma's als we ze compileren. Het geheugen verandert dynamisch. Dus wat we doen is elk programma zijn eigen adresruimte geven.
➔ De programmeerlast van een kleine, beperkte hoeveelheid aan main memory weg te werken.
We willen dus toelaten dat een single-user programma groter kan zijn dan de grootte van het primaire geheugen. Het virtuele geheugen beheert automatisch de 2 levels van geheugenhiërarchie die gerepresenteerd worden door main memory en secondary storage.
Met virtueel geheugen, produceert de processor een virtueel adres dat dan vertaald wordt naar een fysiek adres door een combinatie van hardware en software en wat dan op zijn beurt gebruikt kan worden om main memory te accessen.
Enkele key motivaties voor design
- Pages zo groot mogelijk -> amortiseren van de hoge acces time
- Organisatie dat de page fault rate verlaagt ( via fully associative plaatsing voor de pagina’s)
- Page faults laten oplossen door de software → overhead lager ivm. Disk acces time
- Altijd write back gebruiken, write through veel te kostelijk.
123
Explain figure 5.25
Pages worden gemapped van een virtueel adres naar een fysiek adres. Een virtueel adres is nodig zodat 2 verschillende programma’s dat dezelfde data nodig hebben deze kunnen delen (meerdere virtuele adressen kunnen naar 1 fysiek adres wijzen)
124
What happens on a write?
We hebben 2 basic opties, nl. write back of write through. De voordelen van beide wordt hieronder opgsomd.
Write back:
(Altijd gebruikt bij virtueel geheugen omdat schrijven naar disk zo kostelijk is)
- schrijven van individuele woorden aan snelheid cache (ipv snelheid geheugen)
- meerdere writes in 1 block vereisen slechts 1 write naar een lager level in de geheugenhiërarchie
- Hoge bandbreedte transfer, doordat de hele blok wordt geschreven.
write through:
- Misses zijn simpeler en goedkoper omdat je geen write van heel blok nodig hebt
- Makkelijker te implementeren.
125
Where can a block / page be placed?
Moet geoptimaliseerd worden om page faults te vermijden ten allen tijde.
= toelaten dat een virtuele pagina op elke fysieke pagina mag gemapped worden, zodat de OS kan elke pagina kan kiezen ter vervanging indien er een page fault is.
126
Which block / page should be replaced on a cache miss / page fault?
Kunnen gebruik maken van LRU of random, afhankelijk van set-associativiteit. LRU zelf vaak te kostelijk, dus bijna altijd benadering. Indien te hoge associativiteit: random.
127
Explain figure 5.29
Risc-V gebruikt 4 niveau’s van tafels om te transleren van een virtueel adres naar een fysiek. Dit is om de page table entries compact te houden. Elke stap gebruikt 9 bits van het virtuele adres om de tabel op het volgende niveau te vinden. Tot de bovenste 36 bit van het virtuele adres gemapt is op het fysieke.
128
Write back
Het alternatief van write through. Bij write back, wanneer een write zich voordoet, wordt de nieuwe waarde enkel geüpdatet in de cache en dan indien de block vervangen wordt schrijf je de block in het geheugen.
Gemiddeld gezien worden er meer bytes geschreven naar geheugen, maar sneller indien veel writes voorkomen aangezien acces time groot is in vgl met transfer time, wel moeilijker om te implementeren. Vraagt 2 kloklcycli: check op hit en dan schrijf, store-buffer: check op hit + schrijf in blok, volgende cyclus kopie van buffer naar juiste plaats. Write-buffer: buffer voor vuil blok tijdens read van nieuw blok. (=/
buffer)
