2.5 Minnehierarki og cache-beregning
Minnehierarkiet (register → cache → RAM → disk) og cache-beregningen som vektet snitt av treff og bom — et voksende, fast tema.
Nivå 2 — dette avgjør ofte om seksjonen bestås. Sjangeren er ikke like gammel som portene, men den er den eneste regneoppgaven i seksjon 2, maskinvare og arkitektur, og et regnepoeng er alltid det billigste poenget i en seksjon: fasiten er entydig, og du kan kontrollere svaret ditt selv.
Slik kommer den: som svarform F4 (nedtrekksmeny: velg ett alternativ per delspørsmål) eller F1 («velg ett eller flere alternativer»). Alternativene er tall, og hvert galt tall svarer til en bestemt regnefeil.
Den ene tingen som skiller bestått fra bom her: å bytte om treff og bom. Sier oppgaven «40 % bom», er 40 % av instruksjonene bom og 60 % treff — ikke motsatt. Regner du med feil andel, får du et tall som ser helt rimelig ut, og som står blant alternativene nettopp derfor.
Tidsbruk: 50 minutter, fordelt på fire løkker med tidsanslag.
Forkunnskaper — sist du var her
Dette kapitlet bygger på kap. 2.4. Her er det du trenger, ferdig oppfrisket:
1. Klokkesykelen er maskinens minste tidsenhet. Alt arbeid måles i antall sykler. En prosessor på 3 GHz gjør tre milliarder sykler i sekundet.
2. Register er raskest, hovedminnet er tregt. Registeret ligger på prosessorbrikken og nås uten å gå over bussene. Et oppslag i hovedminnet må ut på adressebussen, inn i minnebrikken og tilbake på databussen — og det tar mange sykler.
3. Von Neumann-flaskehalsen. Prosessoren og hovedminnet deler samme forbindelse, så prosessoren blir stående og vente. Dette kapitlet handler om svaret på nettopp det problemet.
4. Prosentregning. 40 % av 3000 er 0,40 · 3000 = 1200. Resten, 60 %, er 3000 − 1200 = 1800. Du trenger ikke mer regning enn dette — men du må holde styr på hvilken andel som er hva.
Løkke 1 — Hierarkiet: raskt er lite, stort er tregt (~12 min)
Tenk på et kjøkken. Det du bruker hele tiden — salt, pepper, sleiv — ligger på benken, en armlengdes avstand unna. Det du bruker av og til, står i skapet over. Det du bruker sjelden, står i kjelleren.
Ingen har bestemt dette; det følger av at benkeplass er dyrt og kjellerplass er billig.
Et datamaskinminne er organisert etter nøyaktig samme logikk. Det raskeste minnet er også det dyreste per byte, og derfor er det lite. Det billigste er tregt, og derfor er det stort.
Lagene av lagring i en datamaskin, ordnet fra raskt, dyrt og lite øverst til tregt, billig og stort nederst:
| Nivå | Typisk størrelse | Typisk tilgangstid |
|---|---|---|
| Register | noen titalls ord | 1 klokkesykel |
| Mellomlager (cache) | kilobyte til megabyte | noen få sykler |
| Hovedminne (RAM) | gigabyte | titalls til hundrevis av sykler |
| Disk | terabyte | millioner av sykler |
De tre egenskapene henger sammen: raskere betyr dyrere per byte, og dyrere betyr mindre. Det er ingen teknologi som er både raskest og størst.
Rekkefølgen skal sitte begge veier. Den faste feilslutningen er å plassere hovedminnet over mellomlageret fordi det heter «hoved»-minne — men navnet sier noe om rollen, ikke om farten.
Et lite, raskt minne mellom prosessoren og hovedminnet, som holder en kopi av de dataene som nylig har vært i bruk.
Når prosessoren ber om en verdi, ser den først i mellomlageret. Ligger verdien der, er saken avgjort på noen få sykler. Ligger den ikke der, må turen gå ut til hovedminnet — og det er den turen som koster.
Mellomlageret styres av maskinvaren og er usynlig for programmereren: det finnes ingen instruksjon som sier «legg dette i cachen». Det eneste programmereren merker, er at noen programmer går fortere enn andre.
Den faste feilslutningen: å tro at mellomlageret er et eget minne der man kan lagre noe permanent. Det er en kopi, og innholdet byttes ut hele tiden.
Observasjonen som gjør mellomlagring lønnsomt: programmer bruker ikke minnet tilfeldig.
Tidsmessig lokalitet — en adresse som nettopp har vært brukt, blir gjerne brukt igjen snart. En løkkevariabel leses på nytt i hver runde.
Romlig lokalitet — når én adresse brukes, blir naboadressene gjerne brukt like etter. Et program som går gjennom en liste, tar element etter element.
Derfor henter maskinen inn en hel blokk ved et bom, ikke bare den ene byten det ble spurt om: nabobytene kommer trolig til nytte om et øyeblikk.
Den faste feilslutningen: å tro at mellomlageret virker fordi det er «smart» og gjetter. Det gjetter ikke — det utnytter et mønster som nesten alle programmer har.
(Innsteg — hierarkiet.) Sorter disse fire fra raskest til tregest, og oppgi for hver om den er stor eller liten sammenlignet med de andre: hovedminne (RAM), disk, mellomlager (cache), register.
Et program går gjennom en liste med 1000 tall og legger dem sammen, ett om gangen. Forklar hvilken form for lokalitet dette utnytter, og hvorfor maskinen henter inn en hel blokk ved første bom.
Løkke 2 — Regningen: treff, bom og vektet sum (~15 min)
Nå til selve regnesjangeren. Den er enkel når du har den, og den har nøyaktig én felle.
Oppgaven gir deg tre tall: hvor mange instruksjoner som utføres, hvor stor andel som er bom, og hvor mange sykler et bom koster. Du skal finne totalt antall klokkesykler.
— naturlig pausepunkt —
Prosedyren, tre steg:
Steg 1 — del instruksjonene i to grupper. Er n antall instruksjoner og r bom-raten som desimaltall:
Steg 2 — vekt hver gruppe med sin kostnad og summer. Med bom-kostnad k sykler:
Steg 3 — gjennomsnitt per instruksjon, hvis oppgaven ber om det:
Regn med enhetene hele veien. «instruksjoner × sykler/instruksjon = sykler». Et svar uten enhet er halvferdig, og enhetene er dessuten den beste kontrollen på at du ikke har delt feil vei.
Den ene fella: «40 % bom» betyr at 40 % er bom og 60 % er treff. Bytter du om, får du et tall som ser helt rimelig ut — og som står blant alternativene, fordi det er nettopp den feilen distraktoren er bygd for.
Sunn fornuft-kontrollen: gjennomsnittet per instruksjon må alltid ligge mellom 1 og bom-kostnaden. Får du et snitt på 0,8 eller på 15 når bom-kostnaden er 10, har du regnet feil et sted.
Et program utfører 2000 instruksjoner. 25 % av oppslagene er bom, og et bom koster 8 klokkesykler. Hvor mange klokkesykler tar kjøringen, og hva er gjennomsnittet per instruksjon?
antall bom = 0,25 · 2000 instruksjoner = 500 instruksjoner
antall treff = 2000 − 500 = 1500 instruksjoner
Kontroll: 1500 + 500 = 2000. Stemmer.
Steg 2 — vekt og summer.
treff: 1500 instruksjoner · 1 sykel/instruksjon = 1500 sykler
bom: 500 instruksjoner · 8 sykler/instruksjon = 4000 sykler
T = 1500 sykler + 4000 sykler = 5500 sykler
Steg 3 — gjennomsnitt.
5500 sykler ÷ 2000 instruksjoner = 2,75 sykler per instruksjon
Svar: 5500 klokkesykler totalt, 2,75 sykler per instruksjon.
Kontroll med sunn fornuft: snittet 2,75 ligger mellom 1 (rent treff) og 8 (rent bom), og nærmere 1 enn 8 — som det skal, siden tre av fire oppslag er treff. Stemmer.
Det galeste svaret du kan få: bytter du om treff og bom, regner du 500·1 + 1500·8 = 12 500 sykler. Det tallet ser like rimelig ut, og det er derfor det står blant alternativene.
(Innsteg — cache-beregning.) Et program utfører 3000 instruksjoner. Halvparten av oppslagene er bom, og et bom koster 4 klokkesykler. Hvor mange klokkesykler tar kjøringen?
Et program utfører 4000 instruksjoner. Bom-raten er 10 %, og et bom koster 12 klokkesykler.
a) Hvor mange klokkesykler tar kjøringen?
b) Hva er gjennomsnittlig antall sykler per instruksjon?
Et program utfører 5000 instruksjoner. Treffraten er 80 %, og et bom koster 20 klokkesykler. Regn ut totalt antall klokkesykler og gjennomsnittet per instruksjon.
Løkke 3 — Hva forbedringer er verdt (~12 min)
En variant som kommer stadig oftere: oppgaven gir deg to scenarier og spør hvor mye du sparer på å forbedre mellomlageret.
Dette er samme regning to ganger, pluss en subtraksjon. Det som gjør den lærerik, er at gevinsten nesten alltid er større enn man tror — fordi det er de få bommene som eier klokka.
En maskin kjører 8000 instruksjoner med bom-kostnad 20 klokkesykler. I dag er bom-raten 10 %. Et nytt mellomlager ville gitt 5 %. Hvor mange sykler spares, og hvor stor andel av tida er det?
bom = 0,10 · 8000 = 800 instruksjoner, treff = 8000 − 800 = 7200 instruksjoner
T₁ = 7200 · 1 sykel + 800 · 20 sykler = 7200 + 16 000 = 23 200 sykler
Scenario 2 — bom-rate 5 %.
bom = 0,05 · 8000 = 400 instruksjoner, treff = 8000 − 400 = 7600 instruksjoner
T₂ = 7600 · 1 sykel + 400 · 20 sykler = 7600 + 8000 = 15 600 sykler
Besparelsen.
23 200 sykler − 15 600 sykler = 7600 sykler
7600 ÷ 23 200 = 0,3276…, altså ≈ 32,8 % av tida. (Tallet går ikke opp, så det er oppgitt med én desimal.)
Svar: 7600 klokkesykler spart, omtrent 32,8 % av kjøretida.
Det som overrasker: bom-raten ble halvert, fra 10 % til 5 %, men kjøretida ble ikke halvert — den falt med en tredjedel. Grunnen er at treffene fortsatt koster 1 sykel hver, og de 7600 syklene fra treffene forsvinner ikke.
Gjennomsnittene: 23 200 ÷ 8000 = 2,9 sykler før, og 15 600 ÷ 8000 = 1,95 sykler etter. Begge ligger mellom 1 og 20. Stemmer.
En maskin kjører 6000 instruksjoner med bom-kostnad 14 klokkesykler. Bom-raten er 15 %.
a) Hvor mange klokkesykler tar kjøringen?
b) Hvor stor andel av syklene skyldes bom?
c) Hva blir gjennomsnittet per instruksjon?
Et program utfører 1200 instruksjoner. Bom-raten er 25 %, og et bom koster 16 klokkesykler. Kryss av alle påstandene som stemmer, og begrunn hvert av de fire.
a) Kjøringen tar 4800 klokkesykler.
b) Gjennomsnittet er 4,75 sykler per instruksjon.
c) Kjøringen tar 5700 klokkesykler.
d) Bommene står for over 80 % av syklene.
Løkke 4 — Eksamensformen og distraktorene (~11 min)
I en flervalgsoppgave med tall er distraktorene ikke tilfeldige. Hver av dem svarer til en bestemt regnefeil, og du kan lære deg hvilke.
Det gir en gratis kontroll: har du regnet riktig, skal ditt tall stå der — og de andre tallene skal du kunne forklare hvor kommer fra.
Når alternativene er tall, svarer hvert galt tall til én bestemt feil. For n instruksjoner, bom-rate r og bom-kostnad k:
| Tall | Feilen bak det |
|---|---|
n·(1−r)·1 + n·r·k | Riktig svar |
n·r·1 + n·(1−r)·k | Byttet om treff og bom |
n·r·k | Glemt at treffene koster 1 sykel hver |
n·k | Regnet som om alle oppslag var bom |
En femte variant finnes også:
n·(1−r)·1 + n·r·(k+1), som kommer av å legge treffsykelen oppå bom-kostnaden. Boka bruker konvensjonen der bom-kostnaden er hele kostnaden.Slik bruker du tabellen: har du regnet ut et svar og finner det blant alternativene, sjekk raskt om ett av de andre tallene er ett av de tre feiltallene dine. Er det det, har du bekreftet at du har regnet riktig — oppgaven er bygd nettopp slik.
Svarform F4. Et program utfører 2500 instruksjoner. Bom-raten er 60 %, og et bom koster 5 klokkesykler. Hvor mange klokkesykler tar kjøringen?
a) 8500 · b) 7500 · c) 12 500 · d) 6500
bom = 0,60 · 2500 instruksjoner = 1500 instruksjoner
treff = 2500 − 1500 = 1000 instruksjoner
treff: 1000 · 1 sykel = 1000 sykler
bom: 1500 · 5 sykler = 7500 sykler
T = 1000 + 7500 = 8500 sykler
a) Riktig — 8500 sykler.
b) Galt — 7500. Dette er bommenes bidrag alene. Feilen er å glemme at treffene også koster: de 1000 syklene fra treffene mangler.
c) Galt — 12 500. Dette er 2500 · 5, altså regnet som om alle instruksjonene var bom. Bom-raten er ikke brukt i det hele tatt.
d) Galt — 6500. Dette er ombyttingen av treff og bom: 1500 · 1 + 1000 · 5 = 1500 + 5000 = 6500. Her er de 1500 bommene talt som treff og de 1000 treffene som bom. Tallet er av samme størrelsesorden som det riktige, og det er nettopp derfor det er den vanligste bommen i sjangeren.
Fasit: a.
Gjennomsnittet, som kontroll: 8500 ÷ 2500 = 3,4 sykler per instruksjon. Det ligger mellom 1 og 5, og nærmere 5 enn 1 — som det skal, siden over halvparten av oppslagene er bom. Stemmer.
Et program utfører 900 instruksjoner. En tredjedel av oppslagene er bom, og et bom koster 7 klokkesykler.
a) Hvor mange klokkesykler tar kjøringen?
b) Forklar hvilken regnefeil som ville gitt svaret 2100, og hvilken som ville gitt 6300.
Vurder hver påstand som sann eller usann, og begrunn hver rad.
| # | Påstand | Sant/usant |
|---|---|---|
| a | Et mellomlager er raskere enn hovedminnet, men tregere enn et register | |
| b | Ved 10 % bom og bom-kostnad 20 sykler er snittet 2,9 sykler per instruksjon | |
| c | Å halvere bom-raten halverer alltid kjøretida | |
| d | Mellomlageret styres av programmet med egne instruksjoner |
1. Å bytte om treff og bom. «40 % bom» betyr 40 % bom og 60 % treff. Ombyttingen gir et tall som ser rimelig ut, og det står blant alternativene nettopp derfor. Skriv opp begge gruppene og kontroller at de summerer til n.
2. Å glemme at treffene koster. Et treff koster 1 klokkesykel, ikke 0. Regner du bare bom · kostnad, får du et tall som står midt i din egen utregning — den farligste distraktoren som finnes.
3. Å regne som om alle oppslag var bom. n · k er svaret på en helt annen oppgave. Denne feilen kommer av å lese fort og gripe de to tallene som står tydeligst.
4. Å blande treffrate og bom-rate. Les ordlyden. «Treffraten er 80 %» betyr 20 % bom. Oppgavene veksler bevisst mellom de to formuleringene.
5. Å regne uten enheter. «instruksjoner × sykler/instruksjon = sykler». Enhetene er den beste kontrollen på at du ikke har delt feil vei, og et svar uten enhet er halvferdig.
6. Å oppgi et desimaltall upresist. Går tallet ikke opp, skriv «omtrent» og oppgi antall desimaler. 7600 ÷ 23 200 er 32,8 % med én desimal — ikke «cirka en tredjedel» uten videre.
7. Å tro at halvert bom-rate gir halvert tid. Treffene koster fortsatt. Regn begge scenariene og trekk fra.
Begrepsbank til eksamen
Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder kjernestoffet.
At verdien prosessoren ber om, allerede ligger i mellomlageret.
Et treff koster 1 klokkesykel i denne bokas konvensjon — turen ut til hovedminnet er unngått.
Den faste feilslutningen: å tro at et treff er gratis. Det koster mindre enn et bom, men det koster. Å glemme treffenes bidrag er den nest vanligste feilen i sjangeren.
At verdien ikke ligger i mellomlageret, slik at den må hentes fra hovedminnet.
Et bom koster det antallet klokkesykler oppgaven oppgir — typisk mellom 4 og 20 i eksamensoppgaver.
Ved et bom hentes ikke bare den ene verdien, men en hel blokk av naboadresser, fordi romlig lokalitet gjør det sannsynlig at de trengs snart.
Er treffraten 85 %, er bom-raten 15 %. Er bom-raten 40 %, er treffraten 60 %.
Oppgavene veksler bevisst mellom de to formuleringene, og å lese feil her er den vanligste enkeltbommen i sjanger E. Skriv ned begge tallene før du regner videre.
Antall klokkesykler et bom koster — altså hva turen ut til hovedminnet er verdt i tid.
I denne boka er bom-kostnaden hele kostnaden for den instruksjonen, ikke et tillegg til treffsykelen. Sier oppgaven «bom-kostnad 10 sykler», koster den instruksjonen 10 sykler.
Størrelsen forteller noe reelt: at et RAM-oppslag koster titalls sykler, er selve grunnen til at mellomlageret finnes.
Hver gruppe ganges med sin egen kostnad, og de to legges sammen. Det er alt regnestykket er.
Enhetene bærer utregningen: «instruksjoner × sykler per instruksjon = sykler».
Den faste feilen er å hoppe over det første leddet. Treffene er som regel den store gruppen, og bidraget deres er sjelden neglisjerbart.
Totalt antall sykler delt på antall instruksjoner.
En nyttig snarvei: snittet avhenger bare av bom-raten og bom-kostnaden, ikke av n. Ved 10 % bom og kostnad 20 er snittet 0,9·1 + 0,1·20 = 2,9 sykler, uansett programlengde.
Snittet er også den beste rimelighetskontrollen: det skal alltid ligge mellom 1 og bom-kostnaden.
Gjennomsnittet per instruksjon må ligge mellom 1 sykel (alt er treff) og bom-kostnaden (alt er bom).
Er bom-raten liten, skal snittet ligge nær 1. Er den stor, skal det ligge nær bom-kostnaden.
Får du et snitt på 0,8 eller på 25 når bom-kostnaden er 20, har du gjort en feil — og kontrollen tar fem sekunder.
At en adresse som nettopp har vært brukt, sannsynligvis brukes igjen snart.
Det klassiske eksempelet er en løkkevariabel: den leses og skrives i hver eneste runde av løkka, og etter første oppslag ligger den i mellomlageret hele veien.
Dette er den ene av de to formene for lokalitet som gjør mellomlagring lønnsom.
At naboadressene til en adresse som brukes, sannsynligvis brukes like etter.
Eksempelet er et program som går gjennom en liste element for element: adressene kommer i rekkefølge.
Dette er grunnen til at maskinen henter en hel blokk ved et bom. Er blokken 16 elementer stor, blir 1 av 16 oppslag bom — bom-raten faller fra 100 % til ca. 6 % uten at programmet er endret.
Den sammenhengende bunken byte som hentes inn i mellomlageret ved ett bom — typisk 32 til 128 byte.
Størrelsen er en avveining: en stor blokk utnytter romlig lokalitet bedre, men bruker mer plass og mer tid på data som kanskje ikke trengs.
Det er blokkstørrelsen som gjør at bom-raten i praksis er lav selv i programmer som leser store mengder data — så lenge de leser dem i rekkefølge.
Moderne prosessorer har flere lag mellomlager, ofte kalt L1, L2 og L3.
L1 er minst og raskest og ligger nærmest kjernen. L3 er størst og tregest og deles gjerne mellom flere kjerner.
Prinsippet er det samme som i hele hierarkiet: hvert lag utover er større, tregere og billigere per byte. Eksamensoppgavene regner som regel med bare ett lag, men rekkefølgen bør du kjenne.
Det finnes ingen instruksjon som sier «legg dette i cachen». Maskinvaren avgjør hva som lagres og hva som kastes ut.
Det programmereren kan påvirke, er hvordan programmet bruker minnet: leser du data i rekkefølge, utnytter du romlig lokalitet og får få bom. Hopper du tilfeldig rundt, får du mange.
Den faste feilslutningen: å tro at cachen er et lager man styrer selv, som en fil eller en variabel.
Varig lagring beholder det: disk og annen sekundærlagring.
Det er derfor et program alltid lagres varig og lastes inn i hovedminnet når det startes — og det er grunnen til at ulagret arbeid forsvinner ved et strømbrudd.
Grunnen til at hierarkiet ser ut som det gjør, er økonomisk: raskt minne koster mer per byte enn tregt.
En maskin bygd bare av registerraskt minne ville vært svært rask og helt uoverkommelig dyr. En maskin bygd bare av disk ville vært billig og ubrukelig treg.
Hierarkiet er kompromisset: mye av det billige, litt av det dyre, og lokalitet som sørger for at det dyre brukes der det gir mest.
Med 20 % bom og bom-kostnad 20 sykler står bommene for 20 000 av 24 000 sykler — over 83 % av tida, fra en femdel av oppslagene.
Årsaken er størrelsesforholdet: et bom koster tjue ganger så mye som et treff, så det trengs bare noen få av dem før de dominerer.
Dette er hele begrunnelsen for at prosessorer bruker en stor del av brikkearealet på mellomlagre.
Treffene koster fortsatt 1 sykel hver, og de syklene forsvinner ikke når bom-raten synker.
Eksempel: 8000 instruksjoner, bom-kostnad 20 sykler. Ved 10 % bom er tida 23 200 sykler; ved 5 % bom er den 15 600. Nedgangen er 7600 sykler, altså omtrent 32,8 % — ikke 50 %.
Regel: regn ut begge scenariene og trekk fra. Ikke resonner deg til prosenten.
Tallet bom · k, altså bommenes bidrag uten treffene.
Dette er den farligste distraktoren i sjangeren, fordi tallet står midt i din egen utregning: du skriver det ned som mellomresultat, og så kjenner du det igjen blant alternativene.
Motgiften er å gjøre summeringen ferdig før du ser på alternativene.
Tallet n · k, altså regnet som om hvert eneste oppslag var bom.
Feilen oppstår når man leser oppgaven fort og griper de to tallene som står tydeligst — antall instruksjoner og bom-kostnaden — uten å bruke bom-raten.
Kontrollen: er bom-raten brukt i utregningen din i det hele tatt? Er den ikke det, har du regnet på en annen oppgave.
Tallet n·r · 1 + n·(1−r) · k, altså med treff og bom byttet om.
Dette er den vanligste feilen, og resultatet ser alltid rimelig ut — det er et tall av samme størrelsesorden som det riktige.
Motgiften er mekanisk: skriv opp begge gruppene med navn («treff: 3600», «bom: 400») og kontroller at de summerer til n før du ganger med noe som helst.
Går et resultat ikke opp i hele tall, skal du oppgi antall desimaler eksplisitt og skrive «omtrent» eller «≈».
7600 ÷ 23 200 = 0,3276…, som er 32,8 % med én desimal.
Den faste feilen er å skrive et avrundet tall som om det var eksakt, eller å oppgi flere desimaler enn utregningen faktisk gir. Sensorkravet i regnesjangre er å vise mellomregningen og være presis om avrundingen.
Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.
Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.