Les 4: geheugenstroom in outof-order

Les 4: geheugenstroom in outof-order microarchitectuur Geavanceerde computerarchitectuur Lieven Eeckhout Academiejaar 2008-2009 Universiteit Gent

Overzicht • Geheugenhiërarchie – (herhaling “Computerarchitectuur”en “Besturingssystemen”)

• Geheugenstroom in OoO processor • Prestatie verbeteren van de geheugenhiërarchie

2

Belang geheugenhiërarchie • Latentie verbergen van geheugen • Te wijten aan relatief gezien zeer traag geheugen t.o.v. processor • Geheugenhiërarchie is zeer effectief • Idealiter – – – – –

Oneindige capaciteit Oneindige bandbreedte Persistent (non-volatile) Geen latentie Goedkoop 3

Geheugenhiërarchie Component

Technologie

Bandbreedte

Latentie

Kost per gigabyte (USD)

Schijf

Magnetisch

10+ MB/s

10ms

<1

Hoofdgeheugen

DRAM

2+ GB/s

50+ ns

< 200

On-chip L2 cache

SRAM

10+ GB/s

2+ ns

<100.000

On-chip L1 cache

SRAM

50+ GB/s

300+ ps

<100.000

Registerbestand

SRAM met meerdere leesen schrijfpoorten

200+ GB/s

300+ ps

>10.000.000 (?)

4

Lokaliteit • Geheugenhiërarchie is gebaseerd op de notie van lokaliteit • Temporele lokaliteit – Toegangen tot dezelfde lokatie in geheugen gebeuren dicht bijeen in de tijd

• Spatiale lokaliteit – Toegangen tot naburige lokaties in geheugen gebeuren dicht bijeen in de tijd

• Zowel in data- als in instructiestroom • Voor (bijna) alle computerprogramma’s 5

M.a.w. … • Data of instructies die we veel gebruiken plaatsen we dicht bij de processorkern – Liefst in registers – Indien niet mogelijk, in L1 cache(s) – Indien ook niet mogelijk, in L2 cache, enz.

• Data die we niet veel nodig hebben, laten we ver van de processorkern – In hoofdgeheugen of op schijf 6

Cache • Drie mogelijke organisaties – Direct-mapped – Set-associatief – Volledig associatief

• Grootte C = S x A x B – S = #sets – A = associativiteit – B = blokgrootte 7

Direct-mapped cache adres tag

index

offset tag

=?

hit?

data

data

8

Set-associatieve cache

adres tag

index

offset tag

=? data

hit?

tag

data

data

=? 9

Vervangingsalgoritme • In set-associatieve en volledig associatieve caches • Replacement policy • Mogelijke vervangingsalgoritmes – First-in first-out (FIFO) – Least recently used (LRU) • Not most recently used (NMRU)

– Random

10

Schrijfoperaties en caches • Write through vs. write back – Write through: schrijf data onmiddellijk door naar volgend niveau in hiërarchie • Vereist meer bandbreedte

– Write back: schrijf data niet onmiddellijk door, maar markeer dirty bit • Data wordt weggeschreven bij een vervanging

• Write allocate vs. write no-allocate – Write allocate: alloceer data in cache – Write no-allocate: alloceer data niet in cache

• Kan op ieder niveau van geheugenhiërarchie verschillend zijn 11

Miss-classificatie • (voor een gegeven cachegrootte, een gegeven blokgrootte en een gegeven vervangingsalgoritme) • Cold miss of compulsory miss – Eerste referentie in programma

• Capacity miss – Miss die ook voorkomt bij een volledig associatieve cache – Beperking van de grootte van de cache

• Conflict miss – Overige misses – Heeft te maken met indexering 12

Typische geheugenhiërarchie • Eerste niveau (L1) – Gescheiden instructie- en datacache – 8KB tot 64KB – Toegangstijd 1 tot 4 processorcycli

• Tweede niveau (L2) – – – –

Geünificeerd (instructies en data samen) 256 KB tot 16MB Toegangstijd 10 tot 30 processorcycli Typisch on-chip

• Derde niveau (L3) – Typisch off-chip, soms met tags on-chip – Soms ook on-chip (Intel Xeon en Itanium 2)

13

Off-chip hiërarchie • Soms ook vierde niveau (L4) – Voor geheugen-intensieve applicaties in servers, b.v. IBM xSeries 445 op basis van Itanium 2 processors

• Geheugen (DRAM) – 128MB tot 100GB – Uniprocessor 70ns – In multiprocessor 100ns tot 1000ns 14

Virtueel geheugen • Programmeur ziet 32- of 64-bit adresruimte • Geheugen is echter veel kleiner... • Virtueel-geheugensysteem vertaalt het beeld van de programmeur naar het fysieke geheugen • Indruk wekken dat volledig virtueel adresbereik aanwezig is in fysiek geheugen • En verschillende processen hebben dit beeld... → time-sharing • Dit vereist vertaling van virtuele adressen naar fysieke adressen; en demand paging 15

Adresvertaling virtueel adres pagina van typisch 4 of 8 KB

adresvertaling

fysiek adres hoofdgeheugen

16

Demand paging • Hardware gaat na of pagina aanwezig is in fysiek geheugen • Indien niet moet de software de pagina inladen vanaf de harde schijf – Duurt ongeveer 10ms – Processor blokkeren? Neen – Exceptie wordt gegenereerd (page fault of paginafout); OS zoekt een fysieke pagina die vervangen mag worden; OS leest pagina van schijf terwijl een ander proces in uitvoering is – Wanneer pagina ingelezen is, kan het proces opnieuw gescheduled worden 17

Memory protection • Fysiek geheugen bevat meerdere pagina’s van verschillende processen • Proces A mag toestand van proces B niet ongewenst aanpassen – Zelfde virtueel adres, verschillend fysiek adres

• Soms is dit echter wenselijk – Gemeenschappelijk geheugen tss. twee processen, of gemeenschappelijke bibliotheken – Verschillende virtuele adressen, zelfde fysiek adres

• Ook binnen één proces kan een geheugentoegang ongewenst zijn: bepaalde acties zijn onmogelijk op bepaalde pagina’s → protectiebits (zie “Besturingssystemen”)

18

Paginatabellen bijhouden • Voorwaartse paginatabellen • Geïnverteerde paginatabellen • TLB – Translation lookaside buffer – Kleine hardware structuur • B.v. volledig associatief bestaande uit 64 elementen • Gedeelte van paginatabellen bijhouden in hardware

– Voor instructies (I-TLB) en data (D-TLB) – Indien TLB miss • Indien afbeelding in paginatabel: lees in hoofdgeheugen • Indien niet in paginatabel: pagina niet in geheugen, paginafout (= exceptie) afhandelen via OS 19

Cache en TLB virtueel adres tag

index

pagina-offset

TLB

fysisch adres fysisch-paginanummer tag

pagina-offset index

blok-offset

cache

data

20

Overzicht • Geheugenhiërarchie – (herhaling “Computerarchitectuur”en “Besturingssystemen”)

• Geheugenstroom in OoO processor • Prestatie verbeteren van de geheugenhiërarchie

21

Geheugenstroom • Memory data flow • Load en store operaties – Data ophalen uit het geheugen om berekeningen op uit te voeren – Spill code: compiler kan niet alle data alloceren in registers, dus extra geheugenoperaties nodig – Complexe datastructuren (in geheugen) enkel toegankelijk via geheugen 22

Uitvoering geheugenoperatie • Drie stappen – Adresgeneratie • Typisch: adresberekening via een optelling van registerinhoud plus een offset • Dit is in de virtuele adresruimte

– Adresvertaling • Vertaling virtueel adres naar fysiek adres

– Geheugentoegang • Effectieve toegang tot data • Load: geheugeninhoud ophalen in register • Store: registerwaarde opslaan in geheugen 23

Load/stores in OoO processor • Load moet wachten op register met adres • Store moet wachten op twee registers (adres + inhoud) • Gepijplijnde uitvoering in FU – Eerste trap: adresberekening – Tweede trap: adresvertaling • Toegang tot TLB; mogelijks een TLB miss of zelfs een paginafout (dit laatste leidt tot een exceptie)

– Derde trap: • Load: waarde opladen in register; mogelijks een D-cache miss en een blokkering van de load/store-eenheid • Store: geen derde trap 24

Stores in OoO processor • Twee pijplijntrappen identiek aan eerste twee trappen voor load • Data die weggeschreven moet worden, wordt opgeslagen in reorder buffer en in store queue/buffer • Wanneer de store het reorder buffer verlaat (completion), wordt de status bit veranderd in store buffer (of, gecopieerd van store queue naar store buffer) en kan de data weggeschreven worden naar geheugen (retire, in programmavolgorde) – Merk op: store is architecturaal gezien uitgevoerd bij 25 completion

Speculatieve uitvoering • Instructies speculatief uitvoeren langs voorspelde pad • Dus ook loads en stores... • Dit is echter geen probleem – Geheugentoestand wordt niet gewijzigd wegens inorder completion vanuit store buffer – Loads halen mogelijks (bij cache miss) data op uit geheugen in de cache... • Interferentie met data die reeds in de cache aanwezig is... • Kan positief of negatief zijn 26

Afhankelijkheden tussen geheugenoperaties • Wanneer twee geheugenoperaties naar hetzelfde adres verwijzen is er een afhankelijkheid – RAW – WAR – WAW

• Een eerste mogelijkheid is in-order uitvoering van geheugenoperaties... • Beter is out-of-order uitvoering van loads/stores, maar opgepast voor afhankelijkheden in OoO processor • Wegens in-order completion kunnen WAW en WAR niet voorkomen • Enkel RAW zijn een mogelijks probleem 27

OoO uitvoering van loads • Vooral OoO voor loads is belangrijk voor een betere prestatie • We kunnen geen hernoeming doen in front-end pijplijn omdat de adressen nog niet gekend zijn • Loads zijn vaak het begin van een ketting van afhankelijke instructies • Twee mogelijke technieken om loads sneller uit te voeren – Load bypassing – Load forwarding 28

Load bypassing ... store r2 → MEM[A] ...

load vóór stores uitvoeren

store r3 → MEM[B] ... load

r4 ← MEM[C]

...

29

Load forwarding ... store r2 → MEM[A] ... store r3 → MEM[B] ... load

r4 ← MEM[A]

RAW afhankelijkheid; data doorsturen van store naar load; load doet geen toegang meer tot geheugen

...

30

Hoe implementeren in OoO? • Niet zo eenvoudig... • We beschouwen eerst de organisatie van een superscalaire pijplijn • En bekijken twee gevallen – In-order uitvoering van load/stores – Out-of-order uitvoering van load/stores – (… om educatieve redenen; bedoeling is OoO uitvoering van loads/stores)

• Prestatiewinst – 11% tot 19% via load bypassing – 1% tot 4% extra via load forwarding 31

Organisatie reservatiestation

store eenheid

load eenheid

store buffer adres finished

adres

data

data

completed

data cache update data + adres

32

Werking • We veronderstellen (voorlopig) in-order uitvoering van geheugenoperaties • Load heeft voorrang op store; schrijfoperatie gebeurt enkel indien bus vrij is en D-cache een geheugenpoort vrij heeft • Store buffer – Finished: zowel speculatieve als niet-speculatieve instructies • Indien langs foutief voorspeld pad, kan genullifieerd worden

– Completed: niet-speculatieve stores • Architecturaal gezien reeds uitgevoerd • Moeten uitgevoerd worden in geval van een exceptie 33

Load bypassing & forwarding • Nagaan of een load data leest die door een store (die vóór de load komt in programmavolgorde) geschreven wordt • Indien we in-order uitvoering beschouwen van loads en stores, moeten we dus het store buffer bekijken • Indien geen afhankelijkheid, load uitvoeren – Load bypassing (vanuit geheugen bekeken)

• Indien een afhankelijkheid, data van store doorsturen – Load forwarding 34

Complexiteit store buffer • Vrij groot – Comparators voor associatieve opzoeking in store buffer – Mogelijks meerdere stores met zelfde adres als load; dus, data van meest recente store doorsturen naar load – Extra leespoort(en) vanuit load-eenheid

35

OoO issue van loads? • In-order issue garandeert dat alle stores vóór de load uitgevoerd zijn alvorens load uitgevoerd wordt – Enkel store buffer bekijken

• In-order issue beperkt ILP – Load moet wachten op alle voorgaande stores (ook indien load onafhankelijk is van stores)

• Wat indien OoO issue van load/stores? 36

Mogelijks probleem • Store die vóór de load komt en die naar hetzelfde adres refereert, is nog niet uitgevoerd wanneer load uitgevoerd wordt – Store zit nog in reservatiestation, of is in uitvoering – Nog niet in store buffer – Meer zelfs, adres is mogelijks nog niet gekend

37

OoO issue van loads reservatiestation

store eenheid

load eenheid

store buffer finish adres finished

adres

adres

data

data

completed

data

data cache update

finished load buffer 38

Werking • Loads voeren OoO uit – Wanneer inputoperandi beschikbaar zijn – Bij finish, adres en data in finished load buffer – Load verlaat finished load buffer bij completion

• Bij completion van store, doe associatieve opzoeking in finished load buffer – Indien geen overeenkomst: geen afhankelijkheid: load mocht uitgevoerd worden vóór store – Indien wel overeenkomst: RAW hazard, dus load wordt genullifieerd, alsook alle instructies die afhankelijk zijn van de load 39

Ontwerpkeuzes • Load instructies vroeg uitvoeren geeft significante prestatieverhoging • Maar… – Extra hardwarekost is aanzienlijk – In geval van foutieve speculatie • Load opnieuw uitvoeren (en mogelijks opnieuw ophalen) • Alle volgende (afhankelijke) instructies eveneens; een grote kost

– Oplossing: RAW afhankelijkheid voorspellen tussen een load en een store (dependence prediction) 40

Overzicht • Geheugenhiërarchie • Geheugenstroom in OoO processor • Prestatie verbeteren van de geheugenhiërarchie – Latentie van cache miss reduceren – Miss rate reduceren – Latentie van cache miss verbergen – Hit time van cache reduceren 41

Prestatie verbeteren • 4 mogelijke benaderingen – Latentie van cache miss reduceren – Miss rate reduceren – Latentie van cache miss verbergen – Hit time van cache reduceren

• (Meeste van) deze technieken zijn orthogonaal, maw. en-en, niet of-of; voor zowel instructies als data 42

Latentie cache miss ↓ (1) • Meerdere niveaus in hiërarchie • Van een gemiddelde toegangstijd = hit_timeL1 + miss_rateL1 x latentieMEM ... naar ... hit_timeL1 + miss_rateL1 x (hit_timeL2 + miss_rateL2 x latentieMEM) • M.a.w. een kleinere fractie van alle instructies naar hoofdgeheugen • Kostelijk qua hardware • Tegenwoordig tot ±¾ van de chipoppervlakte! 43

Voorbeeld: Intel Itanium • • • • •

800MHz L1 32KB (I- en D-) L2 96KB L3 4MB CPU core: 25 miljoen transistors • Caches: 300 miljoen transistors 44

Latentie cache miss ↓ (2) • (Op hogere niveaus van de hiërarchie; typisch tss. L2 en het hoofdgeheugen) • Cachelijn is typisch 32 tot 128 bytes • Het woord dat opgehaald wordt is typisch ≤ 8 bytes • Twee technieken om gevraagde woord sneller naar CPU kern te brengen – Early restart: cachelijn ophalen in sequentiële volgorde; wanneer cachelijn opgehaald is, gevraagde woord meteen naar CPU – Critical word first: haal gevraagde woord eerst op en stuur naar CPU; haal dan de rest van het blok op 45

Latentie cache miss ↓ (3) • Prioriteit geven aan cache misses tgv. leesoperaties over schrijfoperaties, en buffering • Write-through D-cache – Om blokkering te vermijden: write buffer (merk op: niet hetzelfde als store buffer) • Data tijdelijk in write buffer bijhouden tot wanneer de bus vrij is

– Bij load miss, write buffer eerst controleren op de data

• Write-back D-cache – Stel load miss heeft een write-back tot gevolg – Write-back en dan lezen? Neen – Wel: write-back blok kopiëren in write buffer, lezen, inhoud write buffer wegschrijven in geheugen

46

Latentie cache miss ↓ (4) • Write merging • Zowel write-through als write-back hebben een vorm van write buffers • Write merging gaat verschillende woorden die op naburige adressen of hetzelfde adres liggen samenbrengen in één grotere schrijfoperatie • Voordelen: – Minder geheugentrafiek – Beter gebruik write buffer (minder blokkeringen) 47

Latentie cache miss ↓ (5) • Victim cache Victim cache

CPU D-cache

MEM

48

Victim cache • Klein, volledig-associatieve cache • Bevat blokken die verwijderd worden uit de cache t.g.v. een miss • Bij een cache miss, eerst victim cache bekijken – Indien hit: blokken in cache en victim cache omwisselen – Indien miss: naar hoofdgeheugen

• In AMD Athlon: victim cache met 8 elementen

49

Latentie cache miss ↓(6) • Via verbeterde DRAM-technologie – Kortere latentie tot hoofdgeheugen – En ook meer bandbreedte

• Vier technieken – Open paging – Geheugenbanken – Synchrone DRAM-toegang – Double data rate 50

DRAM adres (14 bits)

bitarray

rijdecoder

16K x 16K

RAS

CAS

data (16 bits)

RAS CAS adres

rij

kolom data

51

Dual Inline Memory Module DIMM adres

data (16 bits) RAM chip 0 data (16 bits)

data (64 bits)

RAM chip 1 data (16 bits) RAM chip 2 data (16 bits) RAM chip 3

52

Open paging adres (14 bits)

bitarray

rijdecoder

16K x 16K

RAS

CAS

data (16 bits)

RAS CAS adres

rij

kolom

kolom data

data

53

Geheugenbanken bank N-1 … bank 1

adres (14 bits)

rijdecoder

bitarray bitarray bitarray bank 0

RAS

CAS

data (16 bits)

• Bank is kleiner → kleinere toegangstijd • Meerdere open pages

54

Bijkomende optimalisaties • Synchrone interface – Synchronous DRAM ↔ Asynchronous DRAM – Geen asynchrone handshaking – Op basis van een kloksignaal – Kortere latentie

• Double data rate – Data wordt getransfereerd op zowel opgaande als neergaande flank van het kloksignaal – Hogere bandbreedte 55


Miss rate ↓ (1) • • • •

Grotere blokgrootte Beter spatiale lokaliteit uitbuiten Elimineert koude misses Voor een vaste grootte van de cache bestaat er een optimale blokgrootte – Grotere blokgrootte: minder koude misses – Maar ook minder aantal sets of associativiteit: dus meer conflicten capaciteitsmisses

• Nadeel: grotere latentie in geval van een miss • B.v. 32 tot 128 bytes voor L1; 64 tot 256 bytes voor L2 57

Miss rate ↓ (2) • Grotere caches • Is een belangrijke trend tegenwoordig omwille van – Grote kloof in toegangstijd geheugen t.o.v. klokperiode processor – Steeds groter aantal beschikbare transistors per chip

• B.v. 6MB L3 cache op de chip (Intel Itanium 2) • Nadelen – Hoge kost – Grote toegangstijd (kan deels gecompenseerd worden m.b.v. cachebanken, zie straks) 58

Miss rate ↓ (3) • Hogere associativiteit • 2:1 regel -- een heuristiek – Een direct-mapped cache met grootte N heeft ongeveer dezelfde miss rate als een 2-wegs set-associatieve cache met grootte N/2

• Nadeel: – Grotere hit time, mogelijks een probleem voor klokcyclus

59

Miss rate ↓ (4) • Way prediction • Zie ook vroeger • Weg voorspellen – Miss rate ~ set-associatieve cache – Latentie ~ direct-mapped cache

• Miss rate ↓ of hit time ↓ ?? – Miss rate ↓ t.o.v. direct-mapped cache – Hit time ↓ t.o.v. set-associatieve cache 60

Miss rate ↓ (5) • Via compileroptimalisaties (codegeneratie) • Zowel voor instructies als voor data: code en data layout • Voorbeelden voor code: – Via profilering conflicten tss. stukken code identificeren, en bij plaatsen van code in binair bestand hiermee rekening houden – Alignatie van basisblokken aan begin van een cacheblok (zie vroeger) 61

Compileroptimalisaties bis • Voorbeelden voor data – Lussen omwisselen (loop interchange) /* voor */ for (j = 0; j < 100; j++) for (i = 0; i < 5000; i++) x [i][j] = 2 * x [i][j]; /* na */ for (i = 0; i < 5000; i++) for (j = 0; j < 100; j++) x [i][j] = 2 * x [i][j];

62

Compileroptimalisaties ter • Voorbeelden voor data – Blocking /* voor */ for (i = 0; i < N; i++) for (j = 0; j < N; j++) { r = 0; for (k = 0; k < N; k++) r += y [i][k] * z [k][j]; x [i][j] = r; }

maw. matrix z wordt N keer volledig gelezen 63

Compileroptimalisaties ter /* na blocking */ for (jj = 0; jj < N; jj += B) for (kk = 0; kk < N; kk += B) for (i = 0; i < N; i++) for (j = jj; j < min (jj+B,N); j++) { r = 0; for (k = kk; k < min (kk+B,N); k++) r += y [i][k] * z [k][j]; x [i][j] += r; }

64


Verbergen latentie • Gemiddelde toegangstijd verkleinen via verbergen latentie – Niet-blokkerende cache – Out-of-order uitvoering – Parallellisme: meerdere simultane cachetoegangen • Cachebanken • Gepijplijnde cachetoegang

– Prefetching – Voorspellen adres – Waardevoorspelling

66

Niet-blokkerende cache • Een blokkerende cache blokkeert bij cache miss • Andere geheugenoperaties kunnen geen toegang doen tot cache • Niet-blokkerende (non-blocking) cache door Kroft in 1981 • Idee: loads die een cache miss veroorzaken “aan de kant” zetten – In missed load queue, of – Miss Status Handling Registers (MSHR) 67

Niet-blokkerende cache reservatiestation

store eenheid

load eenheid

missed load queue cache miss

store buffer finish adres adres

adres

data

data

data

data cache update

finished load buffer 68

Werking • Bij cache miss, load aan de kant zetten in missed load queue • Andere onafhankelijke loads kunnen verder uitvoeren • Wanneer het blok is opgehaald, beëindigt de load zijn uitvoering (finish) • Doel: latentie tgv. load miss verbergen door uitvoeren onafhankelijke instructies • Indien meerdere outstanding misses, bereiken we parallellisme op niveau van geheugen (memory-level parallelism of MLP) 69

Out-of-order uitvoering • Wegens exploiteren ILP • Latentie L1 miss (tot 10 cycli) kan goed verborgen worden via out-of-order uitvoering • Latentie L2 miss (meer dan 100 cycli) kan niet goed verborgen worden via out-oforder uitvoering – Wegens eindige grootte reorder buffer – (zie later) 70

Parallelle cachetoegangen • Hoe simultane cachetoegangen (in een zelfde klokcyclus) op een efficiënte manier implementeren? • Caches dupliceren? – Neen wegens te hoge hardwarekost

• Mogelijke oplossingen: – Cachebanken – Gepijplijnde cachetoegangen 71

Cachebanken

D-cache bank 1

D-cache bank 2

D-cache bank 3

D-cache bank 4

Verdeling tussen verschillende cachebanken gebeurt op basis van een aantal adresbits Nadeel: conflicten (meerdere toegangen tot eenzelfde bank in één cyclus) leiden tot extra cycli in uitvoering [merk op: is afhankelijk van verdeling van data over de verschillende banken]

72

Gepijplijnde D-cache toegang • Meerdere parallelle toegangen tot Dcache • Parallellisme in tijd • Nadeel: blokkeringen indien afhankelijkheden tussen opeenvolgende toegangen – B.v. pointer chasing code: doorlopen van een gelinkte lijst 73

Prefetching • Doel: toekomstige load misses anticiperen en de data vroegtijdig ophalen – overlap tussen ophalen data en uitvoeren andere instructies vóór de load • Wanneer de load dan effectief uitgevoerd wordt, is de data reeds in de cache en hebben we dus geen cache miss • Kan in software (prefetch hints) en in hardware, voor zowel instructies als data 74

Ontwerpkeuzes • Belangrijke aspecten – Tijdig ophalen data om latentie te verbergen – Mogelijks extra conflicten in cache wegens ophalen data langs foutief voorspeld pad – Indien prefetch te vroeg komt, andere zinvolle data wordt onnodig verwijderd uit cache • Kan opgelost worden via een apart prefetch buffer

– Extra communicatie over de bus – Voorspelbaarheid? • Stride over een array is makkelijk te voorspellen; gelinkte lijst, bomen e.d. zijn veel moeilijker 75

Hardware prefetching CPU D-cache

prefetcher

MEM

76

Voorbeeld • Stream buffer • Door Jouppi in 1990 • Bij cache miss, haal ook volgende blok op en houd dit bij in stream buffer • Als nadien toegang tot blok in stream buffer, haal het daarop volgende blok op • We kunnen meerdere stream buffers hebben die anticiperend ophalen van op verschillende adressen 77

Software prefetching • Compiler (of programmeur) voegt prefetchinstructies toe in de code • Ophalen in – Register, of – Cache

• Faulting vs. non-faulting – Kan exceptie veroorzaken? – Typisch: non-faulting

• Overhead t.g.v. extra prefetch-instructies • Vaak in combinatie met software pipelining, loop unrolling, enz. 78

Voorspellen adres van load • Load address prediction • Door Austin en Sohi in 1995 • Adres van ophaalgroep aanleggen aan voorspeller; voorspeller geeft adres terug van leesoperatie; data ophalen in volgende cyclus (dus in begin van de pijplijn) • Speculatieve techniek: indien verkeerde voorspelling, herstel nodig 79

Voorspellen data van load • Load value prediction • Lipasti, Wilkerson en Shen, 1996 • Effectieve waarde voorspellen van de leesoperatie • Speculatieve techniek

80


Hit time reduceren (1) • Kleine en eenvoudige caches • Direct-mapped is sneller dan setassociatief • Klein is sneller dan groot (wegens kortere draadlengtes) • Trend: grootte L1 caches blijft gelijk over verschillende generaties, of verkleint zelfs – L1 D-cache: 16KB in Pentium III en 8KB in Pentium 4 82

Hit time reduceren (2) • Latentie adresvertaling virtuele adressen naar fysieke adressen verbergen • Extra pijplijntrap voor vertaling... virtueel adres

tag

index

pagina-offset

TLB

fysiek adres

fysiek-paginanummer tag

index

pagina-offset blok-offset

cache data

83

Virtuele cache? • I.p.v. een fysiek geadresseerde cache? • Voordeel: kortere hit time • Problemen – Protectie wordt bijgehouden als onderdeel van de adresvertaling – Bij proces-switch: zelfde virtuele adressen verwijzen naar andere fysieke adressen • Oplossing: procesID bijhouden per cachelijn

– In geval verschillende virtuele adressen verwijzen naar eenzelfde fysiek adres zitten er meerdere kopieën in de cache… – I/O gebeurt typisch via fysieke adressen 84

Alternatief • Virtueel geïndexeerd, fysiek getagged virtueel adres tag

index

pagina-offset index blok-offset

TLB

cache

fysiek paginanummer

tag = fysiek paginanummer

=?

data

hit/miss? 85

Nadeel • Paginagrootte = grootte van één weg in de cache • Een direct-mapped cache kan niet groter zijn dan de paginagrootte • Door associativiteit toe te voegen kan de cache groter worden

86

Hit time reduceren (3) • Cachebanken • In plaats van één grote cache, meerdere kleine cachebanken • Kleine cachebank → kortere toegangstijd • Selectie cachebank op basis van een aantal bits in adres – Typisch “blok-interleaving”: opeenvolgende blokken in opeenvolgende banken

• Verhoogt ook bandbreedte van de geheugenhiërarchie 87

Oefeningen (1) • De IBM Power4 en UltraSPARC III hebben een write through cache op L1 en een write-back cache op L2. Beide cacheniveaus zijn on-chip. Waarom deze ontwerpsbeslissing? • Bedenk een adresstroom waarbij een direct-mapped cache beter presteert dan een set-associatieve cache. 88

Oefeningen (2) • Beschouw een processor met 32-bit virtuele adressen, 4KB pagina’s en 36-bit fyische adressen. En beschouw verder – L1 I-cache: 64KB, 128 byte blokgrootte, 4WSA, virtuele cache – L1 D-cache: 32KB, 64 byte blokgrootte, 2WSA, fysische cache, writeback – TLB: 128 elementen, 4WSA

Bereken het aantal bits voor de offset, index en tag. Alsook het aantal tag bits en data bits. 89

Les 4: geheugenstroom in outof-order

Recommend Documents