Minnehierarkiet

Minnehierarkiet utnytter lokalitetsprinsippet: programmer aksesserer nylig brukte data (temporal lokalitet) og data nær nylig brukte adresser (spatial lokalitet). Hierarkiet fra raskest/minst til tregeste/størst: Register → L1-cache → L2-cache → L3-cache → DRAM → Disk.

Cache-organisasjon

En adresse deles i tre felt:

Tag: Øverste biter – identifiserer hvilket minneblokk som er i cache.
Index (set): Midtre biter – velger cache-sett (eller cache-linje for direkte-avbildet).
Block offset: Nedre biter – velger byte innen en cache-blokk.

Parameteroversikt: Cache har $2^s$ sett, blokkstørrelse $2^b$ bytes, $w$-bits adresse. Da er tag = $w - s - b$ biter, index = $s$ biter, offset = $b$ biter.

Cache-typer

Direkte-avbildet (direct-mapped): Én linje per sett ($E=1$). Enkel logikk, men høy konfliktrate.
Sett-assosiativ ($E$-veis): $E$ linjer per sett. Reduserer konflikter. Vanlig: 2-veis, 4-veis, 8-veis.
Fullt assosiativ: Én sett som inneholder alle linjene ($s=0$). Ingen konfliktmiss, men krevende søk-hardware.

Gjennomsnittlig aksesstid (AMAT)

$\text{AMAT} = t_{\text{hit}} + (1 - h) \times t_{\text{miss\_penalty}}$

der $h$ er treffrate og $t_{\text{miss\_penalty}}$ er ekstra tid ved cache-miss (typisk DRAM-aksesstid).

Innbyttepolitikker

LRU (Least Recently Used): Bytt ut linjen som ikke er brukt lengst tid. Optimal ved temporal lokalitet.
FIFO: Bytt ut den eldste innlastede linjen. Enklere å implementere enn LRU.
Random: Tilfeldig valg. Overraskende godt i praksis.

Write-politikker

Write-through: Skriv alltid til både cache og DRAM. Enkel, men treg for skriveintensive arbeidsbelastninger.
Write-back: Skriv bare til cache; skriv til DRAM bare når linjen byttes ut (dirty bit). Raskere men mer kompleks.

Eksempel: Direkte-avbildet cache-analyse

Cache: 16 linjer, blokkstørrelse 4 bytes, 32-bits adresser. $s = \log_2 16 = 4$ bits (index), $b = \log_2 4 = 2$ bits (offset), tag = $32 - 4 - 2 = 26$ bits.

Adresse $0x0050$: Offset = siste 2 biter = $00_2 = 0$, Index = neste 4 biter = $0100_2 = 4$, Tag = resterende 26 biter.

Adresse $0x0150$ har samme index = 4, men annet tag → konfliktmiss hvis begge er i cache!

Eksempel: Adressebiter, antall sett og tag-biter

Fast oppgave med tre tall: gitt fysisk minne, blokkstørrelse og cache-kapasitet, finn (1) adressebredde, (2) antall sett, (3) tag-biter.

Fysisk minne $256\,\text{MB} = 2^{28}$ byte → adressen trenger 28 bit.
Direkte-mappet cache (N=1), blokkstørrelse 2 ord á 4 byte $= 8 = 2^3$ byte → offset $= 3$ bit.
Kapasitet $32\,\text{kB} = 2^{15}$ byte; antall blokker (=sett ved N=1) $= 2^{15}/2^3 = 2^{12} = $ 4096 sett → index $= 12$ bit.
Tag $= 28 - 12 - 3 = $ 13 bit.

Eksempel: Treff/bom over en adressesekvens + konvergens

Direkte-mappet cache, kapasitet 32 ord, blokkstørrelse 2 ord, ordstørrelse 4 byte. Blokk $= 8$ byte (offset 3 bit); antall sett $= (32 \cdot 4)/8 = 16$ (index 4 bit). For hver byte-adresse: bestem blokk $= \lfloor \text{adresse}/8 \rfloor$ og sett $= \text{blokk} \bmod 16$.

Gå gjennom sekvensen og før en tabell over hvilken blokk som ligger i hvert sett. Et oppslag er treff hvis blokken allerede ligger i sitt sett, ellers bom (og blokken lastes inn, og kaster ut en evt. konflikt). Treffrate $= \text{antall treff}/\text{antall oppslag}$.

Gjentas sekvensen uendelig mange ganger, konvergerer treffraten mot andelen oppslag som treffer når cachen er «varm» – altså etter at alle konflikter har stabilisert seg. Adresser i samme blokk som nettopp ble lastet (spatial lokalitet) gir varige treff; adresser som stadig kaster hverandre ut i samme sett forblir bom.

En 2-veis sett-assosiativ cache (samme kapasitet, LRU) halverer antall sett men gir to plasser per sett, slik at to konkurrerende blokker kan ligge samtidig → lavere missrate. Med større blokkstørrelse hentes flere naboord per miss.

Eksempel: To-nivå cache (AMAT)

L1-aksess $1$ syklus med treffrate $80\%$; L2-aksess $20$ sykler med treffrate $90\%$; hovedminne $100$ sykler (alltid treff). Gjennomsnittlig aksesstid:
$\text{AMAT} = t_{L1} + (1-h_{L1})\big[t_{L2} + (1-h_{L2})\,t_{mem}\big]$
$= 1 + 0{,}20\,[20 + 0{,}10 \cdot 100] = 1 + 0{,}20 \cdot 30 = 1 + 6 = 7\,\text{sykler}$.

For en ett-nivås cache ($1$ syklus, hovedminne $100$ sykler) som skal slå dette: $1 + (1-h)\cdot 100 \le 7 \Rightarrow (1-h) \le 0{,}06 \Rightarrow h \ge 94\%$.

Studieguide: Cache og minnehierarki

Studieguide: Cache og minnehierarki