Cache

Cache ([

kæʃ ], [ kaʃ ] ^[1] ) beskriver et fast bufferminne i informasjonsteknologi , noe som bidrar til å unngå (gjentatt) adgang til en langsom bakgrunn medium eller kostbare omregninger. Data som allerede er lastet inn eller generert en gang, forblir i hurtigbufferen, slik at de kan hentes raskere fra den om nødvendig senere. Data som sannsynligvis vil trengs snart, kan også hentes på forhånd fra bakgrunnsmediet og i utgangspunktet gjøres tilgjengelig i hurtigbufferen ( les videre ).

Cacher kan utformes som en maskinvarestruktur (for eksempel som hovedminnebrikker ) eller programvarestruktur (for eksempel som midlertidige filer eller reservert lagringsplass ).

Cache er et lånord fra engelsk. Den har sin opprinnelse i den franske cachen , som faktisk betyr gjemmested . ^[2] ^[3] Navnet tydeliggjør det faktum at hurtigbufferen og dens erstatningsfunksjon for det adresserte bakgrunnsmediet vanligvis er skjult for brukeren. Alle som bruker bakgrunnsmediet trenger ikke å vite størrelsen eller funksjonaliteten til hurtigbufferen i prinsippet, fordi hurtigbufferen ikke blir adressert direkte. Brukeren "adresserer bakgrunnsmediet", men i stedet "svarer" hurtigbufferen - nøyaktig på samme måte som bakgrunnsmediet ville ha svart, det vil si levert data. Fordi denne mellomenheten er usynlig, blir den også referert til som åpenhet . I praksis er det en speilet ressurs som kan redigeres / brukes veldig raskt på vegne av originalen.

Hvis, i tillegg til at enheten bruker hurtigbufferen, andre enheter får tilgang til bakgrunnsmediet, kan dette føre til inkonsekvenser . For å få tilgang til et identisk databilde, er det nødvendig å overføre endringene til hurtigbufferen til bakgrunnsmediet før tilgang. Cache-strategier som gjennomskriving eller tilbakekalling er praktisk mulig her. I ekstreme tilfeller må en fullstendig " cache flush " utføres.

I tillegg må hurtigbufferen informeres om at data på bakgrunnsmediet har endret seg og at innholdet ikke lenger er gyldig. Hvis hurtigbufferlogikken ikke sikrer dette, oppstår ulempen at endringer som gjøres i bakgrunnsmediet eller i dataprogrammet, ikke gjenkjennes i mellomtiden. Hvis det er mistanke om endringer eller for å sikre at gjeldende status blir tatt i betraktning, må brukeren eksplisitt starte en hurtigbufferoppdatering.

Å bruke

Målene når du bruker en cache er å redusere tilgangstiden og / eller å redusere antall tilganger til et sakte bakgrunnsmedium. Dette betyr spesielt at bruk av cacher bare er verdt der tilgangstiden også har en betydelig innflytelse på den generelle ytelsen. Mens z. B. er tilfellet med prosessorbufferen til de fleste (skalare) mikroprosessorer, den gjelder ikke for vektormaskiner , der tilgangstiden spiller en underordnet rolle. Det er derfor cacher vanligvis ikke brukes der fordi de er til liten eller ingen nytte.

En annen viktig effekt ved bruk av cacher er reduksjonen av den nødvendige dataoverføringshastigheten til tilkoblingen av bakgrunnsmediet (se f.eks. Minnehierarki ); bakgrunnsmediet kan derfor kobles “langsommere”, B. kan resultere i lavere kostnader. Fordi flertallet av spørsmålene ofte kan besvares av cachen ("cache hit", se nedenfor), reduseres antall tilganger og dermed den nødvendige overføringsbåndbredden . For eksempel vil en moderne mikroprosessor uten hurtigbuffer, selv med en veldig kort tilgang til hovedminnet, bli bremset av det faktum at utilstrekkelig minnebåndbredde er tilgjengelig, fordi utelatelse av hurtigbufferen i stor grad vil øke antall tilganger til hovedmenyen minne og dermed kravene til minnebåndbredden.

Når det gjelder CPUer, kan bruk av cacher dermed bidra til å redusere Von Neumann -flaskehalsen i Von Neumann -arkitekturen . Gjennomføringshastigheten til programmer kan i gjennomsnitt økes enormt.

En ulempe med cacher er deres dårlig forutsigbare timing, siden utførelsestiden for en tilgang ikke alltid er konstant på grunn av cachemiss. Hvis dataene ikke er i hurtigbufferen, må brukeren som får tilgang, vente til den er lastet inn fra det sakte bakgrunnsmediet. Med prosessorer skjer dette ofte når du får tilgang til data som ennå ikke er brukt, eller når du laster den neste programkommandoen med (brede) hopp .

Cachehierarki

Siden det er teknisk komplekst og derfor vanligvis ikke økonomisk fornuftig å bygge en hurtigbuffer som er både stor og rask, kan du bruke flere cacher - f.eks. B. en liten, rask cache og en betydelig større, men noe tregere cache (som imidlertid fortsatt er mye raskere enn bakgrunnsminnet som skal bufres). Dette gjør at de konkurrerende målene om lav tilgangstid og stor bufferstørrelse kan oppnås sammen. Dette er viktig for trefffrekvensen .

Hvis det er flere cacher, danner de en cache hierarki som er en del av minnehierarkiet. De enkelte hurtigbufferne er nummerert i henhold til deres hierarkiske nivå , dvs. nivå - 1 til nivå - n eller L1, L2 for kort osv. Jo lavere tall, jo nærmere er hurtigbufferen for den raske "brukeren"; det laveste tallet angir derfor hurtigbufferen med den raskeste tilgangstiden, som er den første som skal søkes. Hvis L1 -hurtigbufferen ikke inneholder de nødvendige dataene, søkes (vanligvis noe tregere, men større) L2 -hurtigbuffer osv. Dette skjer til dataene enten er funnet i et hurtigbuffernivå (et "hurtigbuffertreff", se nedenfor) eller alle cacher ble søkt uten hell (en "cache miss", se nedenfor). I sistnevnte tilfelle må det sakte bakgrunnsminnet åpnes.

Hvis det oppstår et hurtigbuffertreff f.eks. B. i L3 -cachen blir de forespurte dataene levert til tilgangeren og samtidig overført til L1 -cachen; for dette må en cache -linje vike, som "synker" ned i L2 -cachen.

Med en inkluderende cache er hvert cache -nivå gjennomsiktig for seg selv, det vil si at en cache -linje som er i L1 -cachen også er tilgjengelig i L2- og L3 -cachen. Hvis hurtigbufferlinjen "forskyves" fra L1 -hurtigbufferen (overskrevet med data fra en annen adresse), trenger ingenting annet å gjøres - den er fremdeles tilgjengelig i L2 -hurtigbufferen (hvis det ikke er nødvendig med tilbakekalling eller lignende).
I tilfelle en eksklusiv cache , er en hurtigbufferlinje for en adresse bare tilgjengelig én gang i alle hurtigbuffernivåene. En hurtigbufferlinje til adresse A i L1 -hurtigbufferen er ikke også tilgjengelig i L2- eller L3 -hurtigbufferen. Hvis den forskyves fra L1 -hurtigbufferen, kan den enten kastes helt eller må eksplisitt kopieres til L2 -hurtigbufferen. Der forskyves også en (annen) cache -linje for å få plass til den synkende. Denne andre synker nå ned i L3 -cachen, der en tredje cache -linje må vike.

Eksklusive hurtigbufferhierarkier genererer betydelig mer datatrafikk mellom hurtigbufferne. Så mange hurtigbufferlinjer som summen av L1, L2 og L3 hurtigbufferstørrelser kan holdes klare for dette formålet, mens med den inkluderende hurtigbufferen er bare L3 -hurtigstørrelsen avgjørende.

I maskinvareområdet har spesielt moderne CPUer to eller tre hurtigbuffernivåer; andre enheter har vanligvis bare ett hurtigbuffernivå. I programvaresektoren brukes stort sett bare ett hurtigbuffernivå, et fremtredende unntak er nettlesere som bruker to nivåer ( hovedminne og harddisk ).

Strategier

Cache -størrelse

For å maksimere nytten av hurtigbufferen, som vanligvis er flere krefter på ti, sammenlignet med bakgrunnsminnet, brukes lokalitetsegenskapene til tilgangsmønstrene i funksjon og organisering av en hurtigbuffer. For eksempel, hvis du observerer aktiviteten til et program som kjører på en prosessor over et kort tidsintervall, vil du legge merke til at få og "alltid de samme" små minneområdene (f.eks. Kode i sløyfer, kontrollvariabler, lokale variabler og prosedyreparametere) får gjentatte ganger tilgang til testamentet. Dette er grunnen til at selv små cacher med noen få kibibytes kan være svært effektive.

Imidlertid, hvis en algoritme stadig behandler nye data (f.eks. Streaming data), kan en cache ikke akselerere den gjennom flere tilganger, i beste fall litt gjennom read-ahead .

Utnyttelse av stedet

Siden caches skal være raske, brukes en annen (raskere) minneteknologi for dem enn for minnet som skal bufres (for eksempel SRAM versus DRAM , DRAM versus magnetisk disk, etc.). Derfor er cacher vanligvis mye dyrere når det gjelder pris-bit-forholdet, og derfor er de designet mye mindre. Dette betyr at en cache ikke kan ha alle dataene tilgjengelige samtidig. For å løse problemet med hvilke data som skal lagres i hurtigbufferen, brukes lokalitetsegenskapene til tilgangene:

Midlertidig lokalitet: Siden tilgang til data gjentatte ganger (f.eks. Når du behandler en programsløyfe), er det mer sannsynlig at data som allerede er åpnet også vil bli åpnet igjen. Disse dataene bør derfor helst lagres i hurtigbufferen. Dette resulterer også i behovet for å fjerne gamle data som ikke har blitt brukt på lenge for å få plass til nyere data. Denne prosessen kalles "undertrykkelse".
Romlig lokalitet: Siden programkode og data ikke er spredt tilfeldig rundt i adresserommet, men er ordnet "etter hverandre" og noen ganger bare i visse adresseområder (kode, data, stacksegment , haug , etc.), er det etter tilgang til en bestemt adresse er det sannsynlig at en "nærliggende" adresse (les: mengden av forskjellen mellom de to adressene er veldig liten) er tilgjengelig. Når du behandler et program z. For eksempel behandles den ene kommandoen etter den andre, hvorved disse er "den ene etter den andre" i minnet (hvis det ikke er noen hoppkommando). Mange datastrukturer som matriser er også plassert "den ene bak den andre" i minnet.

På grunn av sin romlige plassering lagrer ikke hurtigbuffere individuelle byte, men heller blokker med data ("cache block" eller noen ganger også kalt "cache line"). I tillegg gjør dette implementeringen enklere og reduserer minneomkostninger , siden du ikke trenger å lagre en adresse per databyte, men bare for hver hurtigbufferblokk. Valget av blokkstørrelse er en viktig designparameter for en hurtigbuffer som kan ha stor innvirkning på ytelsen.

organisasjon

En cache består av et (stort sett) fast antall oppføringer, hver oppføring består av:

Cache -linje: De faktiske bufrede dataene (f.eks. 64 byte for nåværende PC -prosessorer)
Adressekode: Adressen på bakgrunnsmediet der de bufrede dataene begynner
Tilgangs- / administrasjonsinformasjon: spesielt detaljer for "forskyvningsstrategien" (se nedenfor)

Se også # oppføringer i hurtigbufferen nedenfor.

Cache-Line / Cache-Line

En hurtigbufferlinje er den minste administrative enheten i hurtigbufferen til prosessorer. Det er en kopi av et minneområde. Tilgangene fra hurtigbufferminnet til CPU-en eller til hovedminnet skjer således i en enkelt, blokk-for-blokk-overføring. Størrelsen på en hurtigbufferlinje er 16 byte ( Intel 80486 ), 32 byte (Pentium P5 til Pentium III) og 64 byte (Pentium 4 til nåværende Core-i / AMD ZEN-prosessorer i 2018). Minste lengde skyldes minnebussbredden multiplisert med forhåndshentningsdybden til minnet.

Blokker nummerkoder i stedet for adresselapper

I det følgende antas det at hurtigbufferlinjer bare leses og skrives fra adresser hvis adresse kan deles med (byte) lengden på hurtiglinjelinjen.

eksempel

En cache -linje sies å være 64 byte. Det bør spesifiseres at data bare kan leses og skrives med startadresser f.eks. B. 0, 64, 128, 192, 256, ... Bakgrunnsmediet er delt inn i blokker som bare er på størrelse med en hurtigbuffelinje.

Da trenger ikke hele (start) adressen til dataene lenger å bli lagret i adressekodene, men bare hvor mange datablokker som bufres på bakgrunnsmediet. Ved å velge passende tall (potens på to) i det binære systemet, kan kodene lagres på en plassbesparende måte; Dette øker hastigheten på å kontrollere om en forespurt adresse er inneholdt i hurtigbufferen.

Blokk / setningsinndeling av taggene

Fullstendig assosiativ cache

Blokkene (cache-linjene) til en cache kan oppsummeres i såkalte sett. Bare en av postene er da ansvarlig for en bestemt adresse. I en post betjener alle blokker bare en del av alle tilgjengelige adresser. Følgende er variabelen $m$ ${\ displaystyle m}$ $m$ for det totale antallet hurtigbufferblokker og $n$ ${\ displaystyle n}$ $n$ for antall blokker per setning, kalt associativitet. Så da består cachen av ${\tfrac {m}{n}}$ ${\ displaystyle {\ tfrac {m} {n}}}$ ${\ tfrac {m} {n}}$ Setninger.

organisasjon	Antall sett	Associativitet
DM	$m$ ${\ displaystyle m}$ $m$	1
FA	1	$m$ ${\ displaystyle m}$ $m$ ( $=n$ ${\ displaystyle = n}$ $= n$ )
SA	${\tfrac {m}{n}}$ ${\ displaystyle {\ tfrac {m} {n}}}$ ${\ tfrac {m} {n}}$	$n$ ${\ displaystyle n}$ $n$

Avhengig av hvor mye denne inndelingen er gjort, snakker man om en av de tre typene cache -organisasjon:

Kartlagt direkte (Engl. Direkte kartlagt, kort DM): $n=1$ ${\ displaystyle n = 1}$ $n = 1$ , det vil si at hver blokk representerer sin egen setning, så det er like mange setninger som det er blokker. Dermed er nøyaktig én cache -blokk ansvarlig for en gitt adresse. Så det er en direkte kartlegging mellom bakgrunnsminneadressen og hurtigbufferblokkene, derav navnet. Når du ber om en slik cache, trenger du bare å lese opp en enkelt hurtigbufferblokk (mer presist, sjekk den tilhørende koden , se nedenfor), noe som minimerer maskinvarekravene til tagkomparatoren. Til gjengjeld er effektiviteten til hurtigbufferen begrenset, da det kan være gratis hurtigbufferblokker som ikke brukes, se Konflikt -miss nedenfor.
Fullstendig assosiativ, kort sagt FA: $n=m$ ${\ displaystyle n = m}$ $n = m$ , det vil si at det bare er én setning som inneholder alle blokkene. Dette betyr at hver adresse i hver cache -blokk kan bufres. Når du sender en forespørsel til hurtigbufferen, er det derfor nødvendig å sjekke alle hurtiglagerkodene. Siden cachene må være så raske som mulig, gjøres dette parallelt, noe som øker mengden maskinvare som kreves for tag -komparatorer. Fordelen er imidlertid at hurtigbufferen alltid kan lagre data så lenge en hvilken som helst cache -blokk fortsatt er ledig.
Sett associative eller set associative, SA for short: $n$ ${\ displaystyle n}$ $n$ er mellom 2 og ${\tfrac {m}{2}}$ ${\ displaystyle {\ tfrac {m} {2}}}$ ${\ tfrac {m} {2}}$ valgt, dvs. cacheblokkene er i sett med hver $n$ ${\ displaystyle n}$ $n$ Ordnet i blokker. Så her er ${\tfrac {m}{n}}$ ${\ displaystyle {\ tfrac {m} {n}}}$ ${\ tfrac {m} {n}}$ direkte kartlagte cacher valgt fullt assosiativt (dvs. fritt). Denne cachen kalles deretter n-fold setning -assosiativ eller n-fold assosiativ for korte . Denne typen cache representerer et kompromiss mellom maskinvarekompleksitet og effektiviteten til cachen: sammenlignet med en DM -cache får du effektivitet, sammenlignet med en FA -cache, lagrer du maskinvare.

De to første er et spesielt tilfelle av den setningsassosiative bufferen. Den direkte kartlagte og den fullstendig assosiative cachen kan dermed stammer fra den set-assosiative cachen: n = 1 fører til en direkte tilordnet cache, n = m til en fullt assosiativ cache.

Forklaring basert på et eksempel

Hovedstørrelsene på en cache er:

Størrelsen på de lagrede dataene (dvs. størrelsen på hurtigbufferen): her i eksempel 64 KiB
Størrelsen på adresserommet som skal dekkes: her i eksempel 4 GiB
Lengden på en hurtigbuffelinje: her i eksempelet 64 byte
Granulariteten til dataene: her i eksemplet 1 byte
Tilstedeværelse av skitne og gyldige koder.

Uavhengig av strukturen består cachen av 64 KiB / 64 byte = 1024 hurtigbufferlinjer

Fullstendig assosiativ cache

31	30.	29	28	27	26	25.	24	23	22.	21	20.	19.	18.	17.	16	15.	14.	1. 3	12.	11	10	9	8.	7.	6.	5	4.	3	2	1	0
Adresselappens lengde																										Byte posisjon

Det er en hurtigbuffergruppe som inkluderer alle 1024 hurtigbufferlinjer. Hvert hovedminnedataord kan lagres i hvilken som helst av 1024 hurtigbufferlinjer i den ene hurtigbuffergruppen. 1024 komparatorer kreves, som må sammenligne log2 (4 GiB / 64 byte) = log2 (4 GiB) -log2 (64 byte) bits = 32-6 = 26 bits. Disse 26 bitene er festet til hver cache -linje som en adressekode. Maskinvareinnsats:

1024 komparatorer
1024 × 64 × 8 bit faktisk hurtigbuffer
1024 × 26 biters adressekode
1024 × 64 biters gyldige koder
1024 × 64 bit skitne koder
1024 ×? bit for LRU -taggene

Direkte kartlagt cache / enkel eller ikke-assosiativ cache

31	30.	29	28	27	26	25.	24	23	22.	21	20.	19.	18.	17.	16	15.	14.	1. 3	12.	11	10	9	8.	7.	6.	5	4.	3	2	1	0
Adresselappens lengde																cache -gruppe brukt										Byte posisjon

Det er 1024 hurtigbuffergrupper, hver med en hurtigbufferlinje. Hvert hovedminnedataord kan bare lagres i denne hurtigbufferlinjen som tilhører adressen. Cachegruppen resulterer fra bitene 15 til 6 i adressen. Bare én komparator er nødvendig, som må sammenligne log2 (4 GiB) -log2 (64 KiB) bits = 16 bits. Disse 16 bitene er festet til hver cache -linje som en adressekode. Maskinvareinnsats:

En komparator
1024 × 64 × 8 bit faktisk hurtigbuffer
1024 × 16 biters adresselapp
1024 × 64 biters gyldige koder
1024 × 64 bit skitne koder
Ingen LRU -tagger

Dobbel assosiativ cache

31	30.	29	28	27	26	25.	24	23	22.	21	20.	19.	18.	17.	16	15.	14.	1. 3	12.	11	10	9	8.	7.	6.	5	4.	3	2	1	0
Adresselappens lengde																	cache -gruppe brukt									Byte posisjon

Det er 512 hurtigbuffergrupper med to hurtigbufferlinjer hver. Hvert hovedminnedataord kan lagres i en av de to hurtigbufferlinjene som tilhører adressen. Cachegruppen resulterer fra bitene 14 til 6 i adressen. To komparatorer kreves, som må sammenligne log2 (4 GiB) -log2 (64 KiB) +1 bits = 17 bits. Disse 17 bitene er festet til hver cache -linje som en adressekode. Maskinvareinnsats:

To komparatorer
1024 × 64 × 8 bit faktisk hurtigbuffer
1024 × 17 biters adresselapp
1024 × 64 biters gyldige koder
1024 × 64 bit skitne koder
1024 × 1 bit LRU -tagger

2 ^ n-fold assosiativ cache

31	30.	29	28	27	26	25.	24	23	22.	21	20.	19.	18.	17.	16	15.	14.	1. 3	12.	11	10	9	8.	7.	6.	5	4.	3	2	1	0
Adresselappens lengde																		cache -gruppe brukt								Byte posisjon

Det er 1024/2 ^ n cachegrupper med 2 ^ n bufferlinjer hver. Hvert hovedminnedataord kan lagres i en av de 2 ^ n hurtigbufferlinjene som tilhører adressen. Cachegruppen resulterer fra bitene 15- (n-1) til 6 i adressen. Det kreves 2 ^ n komparatorer, som må sammenligne log2 (4 GiB) -log2 (64 KiB) + n bits = 16+ (n -1) bits. Disse 16+ (n-1) bitene er festet til hver cache-linje som en adressekode. Maskinvareinnsats:

2 ^ n komparatorer
1024 × 64 × 8 bit faktisk hurtigbuffer
1024 × (16 + n-1) bit adressekode
1024 × 64 biters gyldige koder
1024 × 64 bit skitne koder
1024 × flere biters LRU -tagger

Cache treffer og savner

Prosessen der dataene for en forespørsel til en cache er tilgjengelig kalles en "cache hit", det motsatte kalles en "cache miss".

For å oppnå kvantitative mål for å evaluere effektiviteten til en hurtigbuffer, er to parametere definert:

Treffsrate: Antall forespørsler med en hurtigbuffertreff delt på det totale antallet forespørsler som er gjort til denne bufferen. Som man lett kan se av definisjonen, er denne mengden mellom null og en. En treffrate på f.eks. B. 0,7 (= 70%) betyr at hurtigbufferen i 70% av alle forespørsler til bufferen kunne levere dataene umiddelbart og måtte matche i 30% av alle forespørslene.
Frøken rate: Analogt med trefffrekvensen, er dette definert som antall forespørsler som dataene ikke var i hurtigbufferen dividert med antall totale forespørsler. Følgende gjelder: Miss rate = 1 - hit rate.

Det er tre typer cache -savner:

Kapasitet: Cachen er for liten. Data var tilgjengelig i hurtigbufferen, men ble fjernet fra den. Hvis du deretter får tilgang til denne adressen igjen, blir denne savnet referert til som en "kapasitetsfeil". Den eneste løsningen er en større cache.
Konflikt: På grunn av den set-assosiative organisasjonen (gjelder også DM-cacher), er det mulig at det ikke lenger er nok plass i ett sett mens det fortsatt er ledige cache-blokker i andre sett. Deretter må en blokk fjernes fra den overfylte posten, selv om hurtigbufferen faktisk fortsatt har plass. Hvis du får tilgang til denne fjernede blokken igjen, kalles denne hurtigbuffermissen en "konfliktfeil". Dette kan løses ved å øke hurtigbufferblokkene per post - det vil si å øke assosiativiteten. Når det gjelder fullt assosierende cacher (som bare har én post), er det ingen konfliktfeil på grunn av det involverte prinsippet.
Obligatorisk: En "Obligatorisk frøken" eller "Kald startfrøken" er navnet som gis til den første tilgangen til en adresse hvis data ennå ikke er i hurtigbufferen, og samtidig har bufferen fortsatt ledig plass. Forskjellen med de to andre missene er at det ikke er noen undertrykkelse her, men en blokk er beskrevet for første gang / nytt. Det er vanskelig eller umulig å forhindre. Moderne prosessorer har " prefetcher " -enheter som automatisk laster data inn i hurtigbufferne spekulativt hvis det fortsatt er plass der. Dette er for å redusere antall obligatoriske savner.

Disse tre typene er også kjent som “The Three Cs” for kort. I flerprosessorsystemer, når en cache koherensprotokoll av typen Write-Invalidate brukes, kan en fjerde "C" legges til, nemlig en "Coherency Miss": Når en prosessor skriver til en cache-blokk, kan den samme blokken i cachen til en andre prosessor kastes ut Hvis den andre prosessoren må få tilgang til en adresse som var dekket av denne eksterne cacheblokken, fører dette til en sammenhengende glipp.

Måte å jobbe på

Når du administrerer hurtigbufferen, er det fornuftig å bare beholde blokkene i hurtigbufferen som du ofte får tilgang til. Det er forskjellige erstatningsstrategier for dette formålet. En variant som ofte brukes er LRU -strategien ( l øst r ecently u sed ), der blokken som ikke har vært tilgjengelig på lengst tid alltid byttes ut. Moderne prosessorer (f.eks. AMD Athlon ) implementerer stort sett en pseudo LRU -erstatningsstrategi som fungerer nesten som ekte LRU, men er lettere å implementere i maskinvare.

Forskyvningsstrategier

FIFO (First In First Out): Den eldste oppføringen er undertrykt.
LRU (minst nylig brukt): Oppføringen som ikke har blitt åpnet på lengst tid er forskjøvet.
LFU (minst brukt): Oppføringen som sjelden leses, undertrykkes. Den lagrer imidlertid ikke komplette tidsstempler , noe som vil kreve et relativt langt heltall. Snarere brukes bare noen få biter (to er vanlige, men bare en er mulig) for å markere en hurtigbufferoppføring som brukt mer eller mindre hyppig. Bitene oppdateres parallelt med en forskyvning.
Tilfeldig: En tilfeldig oppføring blir undertrykt.
KLOKKE: Data lagres i hurtigbufferen i den rekkefølgen de er tilgjengelig. Når du får tilgang til et dataelement, settes det inn litt for denne hurtigbufferblokken. I tilfelle en glipp, søkes den første datoen uten en angitt bit fra forsiden til baksiden; denne erstattes. Biten fjernes for alle data som har passert. Det er også merket hvilken dato sist ble lastet inn i hurtigbufferen. Derfra begynner søket etter en dato, som kan erstattes.
Optimal: Laszlo Belady -metoden, der minneområdet forskyves som ikke vil ha vært tilgjengelig på lengst tid, er optimal. Den kan imidlertid bare brukes hvis den komplette programsekvensen er kjent på forhånd (dvs. det er en såkalt offline-prosedyre, i motsetning til FIFO og LRU, som er online-prosedyrer). Programforløpet er nesten aldri kjent på forhånd; derfor kan beste praksis ikke brukes i praksis. Imidlertid kan den optimale algoritmen tjene som en sammenligning for andre metoder.

Skrive strategi

I prinsippet er det to muligheter for skrivetilgang til en blokk som er i hurtigbufferen:

Kopier tilbake (skriv tilbake): Når du skriver, blir blokken som skal skrives ikke umiddelbart lagret i neste høyere minnenivå, men først i hurtigbufferen. Dette skaper en inkonsekvens mellom hurtigbufferen og minnet som skal bufres. Sistnevnte inneholder derfor utdatert informasjon. Bare når ordet forskyves fra hurtigbufferen, skrives det også til neste høyere minnenivå. I tillegg får hver cache-blokk en såkalt skitten bit, som indikerer om blokken må kopieres tilbake når den byttes ut. Dette fører til problemer med minnetilgang fra andre prosessorer eller DMA -enheter, fordi de ville lese utdatert informasjon. Dette kan utbedres med cache koherensprotokoller som f.eks B. MESI for UMA -systemer.
Kontinuerlig skriving (gjennomskriving): Blokken som skal skrives, blir umiddelbart lagret i neste høyere minnenivå. Dette sikrer konsistens. For at prosessoren ikke trenger å vente hver gang til blokken er lagret i det neste høyere minnenivået (som er tregere enn hurtigbufferen), brukes en skrivebuffer. Men når dette fylles opp, må prosessoren stoppe og vente.

Analogt med det ovennevnte er det i utgangspunktet to alternativer for skrivetilgang til en blokk som ikke er i hurtigbufferen:

skrive-tildele: Som med en vanlig cache -miss, blir blokken hentet fra neste høyere minnenivå. De tilsvarende byte som ble endret av skrivetilgang, blir deretter overskrevet i blokken som nettopp har kommet.
ikke-skrive-fordel: Det skrives til neste høyere minnenivå som omgår bufferen, uten at den tilhørende blokken lastes inn i bufferen. Dette kan være fordelaktig for noen applikasjoner der mye skriftlig data aldri blir lest igjen. Ved å bruke ikke-skrive-tildeling forhindrer andre, muligens viktige blokker i å bli forskjøvet og reduserer dermed savningsfrekvensen.

Noen instruksjonssett inneholder instruksjoner som gjør at programmereren eksplisitt kan spesifisere om data som skal skrives skal skrives forbi hurtigbufferen.

Vanligvis brukes kombinasjonen write-back med write-allocate eller through-through with non-write-allocate . Den første kombinasjonen har fordelen av at påfølgende skrivetilganger til samme blokk (lokalitetsprinsippet) blir fullstendig behandlet i hurtigbufferen (bortsett fra den første missen). Dette er ingen fordel i det andre tilfellet, siden hver skrivetilgang til hovedminnet uansett må, og derfor er kombinasjonen gjennomskriving med skrivetildeling ganske uvanlig. ^[4]

Cache flush

En hurtigbufferflukt fører til at hele innholdet i hurtigbufferen skrives tilbake til bakgrunnsminnet. Cache -innholdet forblir stort sett uberørt. En slik prosedyre er nødvendig for å gjenopprette konsistensen mellom hurtigbufferen og bakgrunnsminnet. Dette er for eksempel nødvendig når data fra hovedminnet kreves av eksterne enheter, for eksempel ved multiprosessorkommunikasjon eller når en del av hovedminnet som brukes som utgangsbuffer overføres til DMA -kontrolleren.

Andre

Oppføringer i cachen

Følgende er lagret i hurtigbufferen for hver hurtigbufferblokk:

De faktiske dataene
Dagen (del av adressen)
Flere statusbiter, for eksempel:

modifisert eller skitten

Indikerer om denne hurtigbufferblokken er endret (bare for tilbakeføringsbuffer).

forskjellige statusbiter avhengig av cache -koherensprotokollen , f.eks. B. en bit hver for:

Eieren: Tilsvarer "modifisert og delt". Indikerer at blokken er endret og er i andre hurtigbuffere. Eieren er ansvarlig for å oppdatere hovedminnet når blokken fjernes fra hurtigbufferen. Prosessoren som sist skrev til hurtigbufferblokken, blir den nye eieren.
eksklusiv: Indikerer at blokken ikke er endret og ikke finnes i noen annen hurtigbuffer.
delt: Noen ganger har forskjellige betydninger: Med MESI indikerer dette at blokken ikke er endret, men er også tilgjengelig i cacher til andre prosessorer (også uendret der). Med MOESI betyr det bare at blokken er i andre prosessorbuffere. Hier ist auch erlaubt, dass der Block verändert wurde, also inkonsistent zum Hauptspeicher ist. In diesem Fall gibt es aber einen „Owner“ (so), der für das Aktualisieren des Hauptspeichers verantwortlich ist.
invalid: Zeigt an, ob der Block frei (also mit ungültigen Daten befüllt) oder belegt (also mit gültigen Daten befüllt) ist.

Heiße und kalte Caches

Ein Cache ist „heiß“, wenn er optimal arbeitet, also gefüllt ist und nur wenige Cache Misses hat; ist das nicht der Fall, gilt der Cache als „kalt“. Nach Inbetriebnahme ist ein Cache zunächst kalt, da er noch keine Daten enthält und häufig zeitraubend Daten nachladen muss, und wärmt sich dann zunehmend auf, da die zwischengelagerten Daten immer mehr den angeforderten entsprechen und weniger Nachladen erforderlich ist. Im Idealzustand werden Datenzugriffe fast ausschließlich aus dem Cache bedient und das Nachladen kann vernachlässigt werden.

Beispiele

Prozessor-Cache

Bei CPUs kann der Cache direkt im Prozessor integriert oder extern auf der Hauptplatine (früher weiter verbreitet, heute eher untypisch) platziert sein. Oft gibt es mehrere Ebenen (Levels), die aufeinander aufbauen. Kleinere Level sind dabei typischerweise schneller, haben aber aus Kostengründen eine geringere Größe. Je nach Ort des Caches arbeitet dieser mit unterschiedlichen Taktfrequenzen: Der L1 (Level 1, am nächsten an der CPU) ist fast immer direkt im Prozessor (dh auf dem Die ) integriert und arbeitet daher mit dem vollen Prozessortakt – also u. U. mehreren Gigahertz . Ein externer Cache hingegen wird oft nur mit einigen hundert Megahertz getaktet.

Aktuelle Prozessoren (z. B. AMD Ryzen , Intel-Core-i-Serie , IBM Power 9 ) besitzen überwiegend drei Cache-Level: L1, L2 und L3. Gängige Größen für L1-Caches sind 4 bis 256 KiB pro Prozessorkern, der L2-Cache ist 64 KiB bis 1024 KiB (meist ebenfalls pro Kern), der L3-Cache 2 bis 32 MiB (für alle Kerne gemeinsam). Bei kostengünstigeren Versionen wird mitunter der L3-Cache weggelassen oder abgeschaltet, dafür ist der L2-Cache teilweise etwas vergrößert. Prozessorcache als Extra-Chip auf dem Mainboard wird heute nicht mehr gebaut, als Extra-Die im selben Chip-Gehäuse (siehe Multi Chip Package ) nur noch selten.

In jedem Fall ist eine Protokollierung erforderlich, um die Kohärenz der Daten (z. B. zwischen Caches und Hauptspeicher) sicherzustellen. Dazu dienen Flags , die einen Speicherbereich (typischerweise eine ganze line von 64 Byte) als „dirty“, also geändert, markieren (so bei Schreibstrategie ). Das Problem verschärft sich bei mehreren Cache-Levels und mehreren Prozessoren oder Prozessorkernen.

Die Cachekonsistenz ist sowohl bei mehreren aktiven Geräten auf dem Datenbus, als auch bei mehreren zusammengeschalteten Prozessoren ( Multiprozessorsysteme ) zu beachten.

Bei Mehrprozessorsystemen unterscheidet man ua zwischen SIMD- und MIMD -Strukturen (Single/Multiple Instruction – Multiple Data). Bei MIMD-Systemen ist die Wahrscheinlichkeit hoch, dass verschiedene Prozessoren auf verschiedene Speicherbereiche zugreifen, bei SIMD dagegen kleiner. Danach lässt sich die Cache-Konfiguration einstellen.

Moderne Prozessoren haben getrennte L1-Caches für Programme und Daten (Lese- und Schreibcache), teilweise ist das auch noch beim L2 der Fall ( Montecito ). Man spricht hier von einer Harvard-Cachearchitektur . Das hat den Vorteil, dass man für die unterschiedlichen Zugriffsmuster für das Laden von Programmcode und Daten unterschiedliche Cachedesigns verwenden kann. Außerdem kann man bei getrennten Caches diese räumlich besser zu den jeweiligen Einheiten auf dem Prozessor-Die platzieren und damit die kritischen Pfade beim Prozessorlayout verkürzen. Des Weiteren können Instruktionen und Daten gleichzeitig gelesen/geschrieben werden, wodurch der Von-Neumann-Flaschenhals weiter verringert werden kann. Ein Nachteil ist, dass selbstmodifizierender Code gesondert behandelt werden muss, was seine Ausführung stark verlangsamt. Allerdings wird diese Technik aus Sicherheitsgründen und weil sie oft schwer verständlich, schwer prüfbar und daher nur schlecht zu warten ist, heute ohnehin nur noch sehr selten verwendet.

Laufwerks-Cache

Bei Festplatten befindet sich der Cache auf der Steuerplatine (siehe Festplattencache ) oder einer separaten Platine, dem Festplattenkontroller .

Die Größe beträgt bei aktuellen Festplatten – je nach vom Hersteller vorgesehenen Einsatzzweck der Festplatte – zwischen 8 und 64 MiB (Stand 2012).

Die meisten optischen Laufwerke besitzen Caches, um die oft im dreistelligen Millisekundenbereich liegenden Zugriffszeiten und Schwankungen im Datenstrom (z. B. durch Synchronisierungsprobleme) aufzufangen.

Software-Caches

Caches können auch bei Software genutzt werden, dabei ist dasselbe Prinzip wie bei der Hardwareimplementierung gemeint: Daten werden für einen schnelleren Zugriff auf ein schnelleres Medium zwischengespeichert.

Beispiele:

Festplattencache (vom Betriebssystem verwaltet): Festplatte → Hauptspeicher
Anwendungsdaten ( Memoisation ): Berechnung → Hauptspeicher
Browser-Cache: Netz → (Festplatte / Arbeitsspeicher)
Webserver: Datenbank → HTML -Datei ( HTTP Caching )

Software-Caches, welche die Festplatte als schnelleres Medium verwenden, werden meist in Form von temporären Dateien angelegt.

Man spricht auch von Caching, wenn ein Betriebssystem gewisse Ressourcen – wie z. B. Funktionsbibliotheken oder Schriftarten – vorerst im Arbeitsspeicher belässt, obwohl sie nach Ende ihrer Benutzung nicht mehr gebraucht werden. Solange kein Speichermangel herrscht, können sie im Arbeitsspeicher verbleiben, um dann ohne Nachladen von der Festplatte sofort zur Verfügung zu stehen, wenn sie wieder gebraucht werden. Wenn allerdings die Speicherverwaltung des Betriebssystems einen Speichermangel feststellt, werden diese Ressourcen als erste gelöscht.

Suchmaschinen-Cache

Der Suchmaschinen -Cache ist der Lesecache einer Suchmaschine. Eine Suchmaschine besitzt drei Kernkomponenten:

Ein Webcrawler durchsucht das WWW nach neuen oder veränderten Webseiten und lädt sie (zusätzlich) in
den Suchmaschinen-Cache, über den regelmäßig verschiedene Indizes erstellt werden. Über diese Indizes sucht
ein Suchalgorithmus , der gemäß einer Benutzeranfrage passende Webseiten finden soll.

Die Inhalte aller Webseiten , die die Suchmaschine als Basisdaten für Benutzeranfragen berücksichtigt, werden im Suchmaschinen-Cache zwischengespeichert. Die Server einer Suchmaschine können nicht für jede Abfrage jede Webseite in Echtzeit auf die aktuellsten Inhalte durchsuchen; stattdessen wird in einem Index über dem Cache gesucht.

Im Allgemeinen kann ein Webseiten-Betreiber Änderungen seiner Webseiten an die Suchmaschine melden, dann fragt der Webcrawler die Seite baldmöglichst erneut ab; ansonsten prüft der Webcrawler jede Webseite in regelmäßigen Abständen – die Cache-Inhalte können also veraltet sein. Eine Webseite kann dem Crawler einen Hinweis geben, wie häufig sie sich im Allgemeinen ändert. Suchmaschinen gehen mit dieser Information mitunter verschieden um.

Die in Deutschland verbreitetste Suchmaschine ist Google ; deren Cache-, Indizier- und Suchstrategien wird daher besonders hohes Interesse zuteil. Die Webcrawler-Frequenz, mit der Webseiten geprüft werden, liegt bei Google bei den meisten Webseiten zwischen einer und vier Wochen („[…] Inhalt wird in der Regel alle 7 Tage aktualisiert “ ^[5] ). Gemeldete Webseiten untersucht der sogenannte Googlebot .

Weblinks

Wiktionary: Cache – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Artikel über CPU-Cache bei arstechnica.com (englisch)
Cache und Hauptspeicher Online-Seminar
Kurzüberblick Cache im Elektronik-Kompendium

Einzelnachweise

↑ Cache auf duden.de
↑ Wörterbuch Französisch. Übersetzung: cache. (Nicht mehr online verfügbar.) Éditions Larousse , archiviert vom Original am 28. Januar 2013 ; abgerufen am 20. November 2018 .
↑ Definition for cache. University of Oxford , abgerufen am 18. Februar 2012 .
↑ John Hennessy, David Patterson: Computer Architecture. A Quantitative Approach. 4th Edition. Morgan Kaufmann Publishers, ISBN 978-0-12-370490-0 (engl.), S. C-11–C-12
↑ „ Ein kurzer Einblick in die Funktionalität des Google-Caches ( Memento vom 28. Juli 2017 im Internet Archive )“ (Mit Suchfunktion)

[1] Cache auf duden.de

[2] Wörterbuch Französisch. Übersetzung: cache. (Nicht mehr online verfügbar.) Éditions Larousse , archiviert vom Original am 28. Januar 2013 ; abgerufen am 20. November 2018 .

[3] Definition for cache. University of Oxford , abgerufen am 18. Februar 2012 .

[4] John Hennessy, David Patterson: Computer Architecture. A Quantitative Approach. 4th Edition. Morgan Kaufmann Publishers, ISBN 978-0-12-370490-0 (engl.), S. C-11–C-12

[google_cache-5] „ Ein kurzer Einblick in die Funktionalität des Google-Caches ( Memento vom 28. Juli 2017 im Internet Archive )“ (Mit Suchfunktion)

[1]

[2]

[3]

[4]

[5]