Hoofdstuk 5: Exploiting memory hierarchy Flashcards
Address space
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.
Explain figure 5.1
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.
Address translation
= 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.
AMAT
= Average memory access time
= time for a hit + miss rate * miss penalty
Deze metriek wordt gebruikt voor de performantie van caches
Amazon web service
= 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.
Availability
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)
Explain figure 5.9
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.
Block or line
Minimale eenheid van informatie die aanwezig (of niet) kan zijn in de cache. Dit is dus in een two-level hiërarchie.
Software optimization via blocking
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)
Cache
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.
Capacity misses
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
Explain figure 5.10
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.
Characteristics of a typical level 1 cache
vooral bezig met hit time te reduceren (zie multilevel caches)
Check yourself p. 369
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!
Choosing which block to replace in a cache
- 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)
Explain figure 5.47
Geoptimaliseerde c versie van DGEMM door cache blocking te gebruiken
Compare random versus LRU
- 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)
Compulsory misses
= 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.
Context switch
= 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.
Cost of a page fault
= 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
Cylinder
Dit zijn alle tracks die zich onder of boven de kop bevinden op een bepaalde plaats bij een magnetic disk.
Explain figure 5.14
Locatie van een memory block met als adress 12 in een cache met 8 blocken voor direct mapped, set associative en fully associative.
Explain figure 5.8
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.
Dependability
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.
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)
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)
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.
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
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.
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
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.
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!
Check yourself p.390
Hoe Kleiner de latency, hoe kleiner de cache blok. Hoe hoger de bandbreedte, hoe breeder de cache blok
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)
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.
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.
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.
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.
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)
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.
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.
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.
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.
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
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
Characteristics of a typical level 2 cache
Vooral bezig met miss rate te reduceren. (zie multilevel caching)
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
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
Explain figure 5.27
= De pagina table voor een met de virtuele pagina nummers om de corresponderende fysieke pagina nummers te vinden.
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.
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.
