Cache

Från Wikipedia, den fria encyklopedin
Hoppa till navigation Hoppa till sökning

Cache ([ kæʃ ], [ kaʃ ] [1] ) beskriver ett snabbt buffertminne i informationsteknologi , vilket hjälper till att undvika (upprepas) tillgång till en långsam bakgrundsmediet eller kostsamma omräkningar. Data som redan har laddats eller genererats en gång finns kvar i cacheminnet så att det kan hämtas från det snabbare om det behövs senare. Data som förmodligen kommer att behövas snart kan också hämtas i förväg från bakgrundsmediet och initialt göras tillgängligt i cacheminnet ( read-ahead ).

Cacheminne kan utformas som en hårdvarustruktur (till exempel som huvudminnechips ) eller programvarustruktur (till exempel som tillfälliga filer eller reserverat lagringsutrymme ).

Cache är ett lånord från engelska. Det har sitt ursprung i den franska cachen , vilket faktiskt betyder gömställe . [2] [3] Namnet förtydligar det faktum att cachen och dess substitutfunktion för det adresserade bakgrundsmediet vanligtvis är dolda för användaren. Alla som använder bakgrundsmediet behöver i princip inte veta storleken eller funktionen på cacheminnet, eftersom cachen inte adresseras direkt. Användaren "adresserar bakgrundsmediet", men i stället "svarar" cachen - exakt på samma sätt som bakgrundsmediet skulle ha svarat, det vill säga tillhandahållen data. Eftersom denna mellanliggande enhet är osynlig kallas den också transparens . I praktiken är det en speglad resurs som kan redigeras / användas mycket snabbt för originalets räkning.

Om, förutom att enheten använder cachen, andra enheter kommer åt bakgrundsmediet kan detta leda till inkonsekvenser . För att kunna få åtkomst till en identisk databild är det nödvändigt att överföra ändringarna i cacheminnet till bakgrundsmediet före åtkomst. Cachestrategier som genomskrivning eller återskrivning är praktiska här. I extrema fall måste en fullständig " cache flush " utföras.

Dessutom måste cachen informeras om att data på bakgrundsmediet har ändrats och att dess innehåll inte längre är giltigt. Om cache -logiken inte säkerställer detta uppstår nackdelen att ändringar som görs i bakgrundsmediet eller i datorprogrammet inte känns igen under tiden. Om det misstänks ändringar eller för att säkerställa att den aktuella statusen beaktas måste användaren uttryckligen initiera en cache -uppdatering.

Att använda

Målen när du använder en cache är att minska åtkomsttiden och / eller att minska antalet åtkomst till ett långsamt bakgrundsmedium. Detta innebär i synnerhet att användningen av cacheminnen endast är värd när åtkomsttiden också har ett betydande inflytande på den totala prestandan. Medan z. B. är fallet med processorcache för de flesta (skalära) mikroprocessorer, det gäller inte vektordatorer , där åtkomsttiden spelar en underordnad roll. Det är därför cachar vanligtvis inte används där eftersom de är till liten eller ingen nytta.

En annan viktig effekt vid användning av cacheminnen är minskningen av den nödvändiga dataöverföringshastigheten till anslutningen av bakgrundsmediet (se t.ex. minneshierarki ); bakgrundsmediet kan därför anslutas "långsammare", B. kan resultera i lägre kostnader. Eftersom majoriteten av frågorna ofta kan besvaras av cachen ("cache hit", se nedan), minskar antalet åtkomst och därmed nödvändig överföringsbandbredd . Till exempel skulle en modern mikroprocessor utan cache, även med en mycket kort åtkomsttid för huvudminnet, bromsas av det faktum att otillräcklig minnesbandbredd är tillgänglig, eftersom utelämnandet av cacheminnet kraftigt skulle öka antalet åtkomst till minnet och därmed kraven för minnesbandbredd.

När det gäller processorer kan användningen av cacheminne således bidra till att minska Von Neumann -flaskhalsen i Von Neumann -arkitekturen . Körningshastigheten för program kan i genomsnitt ökas enormt.

En nackdel med cacheminnen är deras dåligt förutsägbara timing, eftersom körningstiden för en åtkomst inte alltid är konstant på grund av cachemissar. Om data inte finns i cacheminnet måste den åtkomstande användaren vänta tills den har laddats från det långsamma bakgrundsmediet. Med processorer händer detta ofta vid åtkomst till data som ännu inte har använts eller när nästa programkommando laddas med (breda) hopp .

Cachehierarki

Eftersom det är tekniskt komplext och därför vanligtvis inte är ekonomiskt vettigt att bygga en cache som är både stor och snabb kan du använda flera cacher - t.ex. B. en liten, snabb cache och en betydligt större, men något långsammare cache (som dock fortfarande är mycket snabbare än bakgrundsminnet som ska cachas). Detta gör att de konkurrerande målen med låg åtkomsttid och stor cachestorlek kan uppnås tillsammans. Detta är viktigt för träfffrekvensen .

Om det finns flera cachar, bildar de en cache hierarki som är en del av minneshierarkin. De enskilda cacheminnena är numrerade enligt deras hierarkiska nivå , dvs nivå - 1 till nivå - n eller L1, L2 för kort, etc. Ju lägre siffra, desto närmare är cachen för den snabba "användaren"; det lägsta numret anger därför cacheminnet med den snabbaste åtkomsttiden, som är den första som ska sökas. Om L1 -cacheminnet inte innehåller nödvändig data söks (vanligtvis något långsammare, men större) L2 -cache, etc. Detta händer tills data antingen finns i en cache -nivå (en "cache -träff", se nedan) eller alla cacher sökdes utan framgång (en "cache -miss", se nedan). I det senare fallet måste det långsamma bakgrundsminnet nås.

Om en cache -träff inträffar t.ex. B. i L3 -cacheminnet levereras den begärda informationen till åtkomstmannen och överförs samtidigt till L1 -cachen; för detta måste en cachelinje ge vika, som "sjunker" in i L2 -cachen.

  • Med en inkluderande cache är varje cachenivå transparent för sig själv, dvs en cachelinje som finns i L1 -cachen är också tillgänglig i L2- och L3 -cachen. Om cachelinjen "förskjuts" från L1 -cacheminnet (skrivs över med data från en annan adress) behöver inget annat göras - det är fortfarande tillgängligt i L2 -cachen (om ingen återkoppling eller liknande är nödvändigt).
  • I fallet med en exklusiv cache är en cachelinje med en adress endast tillgänglig en gång i alla cachenivåer. En cachelinje till adress A i L1 -cacheminnet är inte också tillgänglig i L2- eller L3 -cacheminnet. Om den förskjuts från L1 -cachen kan den antingen kasseras helt eller måste uttryckligen kopieras till L2 -cachen. Där förskjuts också en (annan) cachelinje för att ge plats för den sjunkande. Den här andra sjunker nu in i L3 -cachen, där en tredje cachelinje måste ge vika.

Exklusiva cachehierarkier genererar betydligt mer datatrafik mellan cacheminnena. Lika många cachelinjer som summan av L1, L2 och L3 cachestorlekar kan hållas redo för detta ändamål, medan med den inkluderande cachen är det bara L3 -cachestorleken som är avgörande.

Inom hårdvaruområdet har i synnerhet moderna processorer två eller tre cachenivåer; andra enheter har vanligtvis bara en cachenivå. Inom mjukvarusektorn används oftast bara en cachenivå, ett framträdande undantag är webbläsare som använder två nivåer ( huvudminne och hårddisk ).

Strategier

Cachestorlek

För att maximera användbarheten hos cacheminnet, som vanligtvis är flera befogenheter på tio, jämfört med bakgrundsminnet, används lokalitetsegenskaperna för åtkomstmönstren vid funktion och organisation av en cache. Om du till exempel observerar aktiviteten hos ett pågående program på en processor under ett kort tidsintervall kommer du att märka att få och "alltid samma" små minnesområden (t.ex. kod inom loopar, kontrollvariabler, lokala variabler och procedurparametrar) får upprepade gånger tillgång till testamentet. Det är därför som även små cachar med några kibibyte kan vara mycket effektiva.

Men om en algoritm ständigt bearbetar ny data (t.ex. strömmande data) kan en cache inte påskynda den genom flera åtkomst, i bästa fall något genom read-ahead .

Utnyttjande av platsen

Eftersom cacheminnen ska vara snabba används en annan (snabbare) minneteknik för dem än för minnet som ska cachas (till exempel SRAM kontra DRAM , DRAM kontra magnetisk disk, etc.). Därför är cachar vanligtvis mycket dyrare när det gäller pris-bit-förhållandet, varför de är utformade mycket mindre. Det betyder att en cache inte kan ha all data tillgänglig samtidigt. För att lösa problemet med vilken data som ska sparas i cacheminnet används lokalitetsegenskaperna för åtkomsten:

Temporal ort
Eftersom data öppnas upprepade gånger (t.ex. vid bearbetning av en programslinga) är det mer troligt att data som redan har nåtts också kommer åt igen. Dessa data bör därför helst förvaras i cacheminnet. Detta resulterar också i behovet av att ta bort gamla data som inte har använts på länge på cacheminnet för att ge plats för nyare data. Denna process kallas "förtryck".
Rymlig lokalitet
Eftersom programkod och data inte sprids slumpmässigt runt i adressutrymmet, utan är ordnade "efter varandra" och ibland bara i vissa adressområden (kod, data, stapelsegment , hög , etc.), är det efter åtkomst till en specifik adress är det troligt att en "närliggande" adress (läs: skillnaden mellan de två adresserna är mycket liten) nås. Vid bearbetning av ett program z. Till exempel bearbetas det ena kommandot efter det andra, varvid dessa är "en efter den andra" i minnet (om det inte finns något hoppkommando). Många datastrukturer som arrays är också placerade "en bakom den andra" i minnet.

På grund av sin rumsliga plats lagrar cacheminnen inte enskilda byte, utan snarare block av data ("cacheblock" eller ibland även kallat "cachelinje"). Dessutom gör detta genomförande lättare och minskar minne overhead , eftersom du inte behöver spara en adress per databyte, men bara för varje depåblock. Valet av blockstorlek är en viktig designparameter för en cache som kan ha stor inverkan på prestanda.

organisation

En cache består av ett (mestadels) fast antal poster, varje post består av:

Cachelinje
Den faktiska cachade data (t.ex. 64 byte för nuvarande PC -processorer)
Adresstagg
Adressen på bakgrundsmediet där cachade data börjar
Åtkomst / hanteringsinformation
särskilt detaljer för "förskjutningsstrategi" (se nedan)

Se även nedan # poster i cachen .

Cache-Line / Cache-Line

En cachelinje är den minsta administrativa enheten i processorns cache. Det är en kopia av ett minnesområde. Åtkomsterna från cacheminnet till CPU: n eller till huvudminnet sker således i en enda block-by-block-överföring. Storleken på en cachelinje är 16 byte ( Intel 80486 ), 32 byte (Pentium P5 till Pentium III) och 64 byte (Pentium 4 till nuvarande Core-i / AMD ZEN-processorer 2018). Minsta längd är resultatet av minnesbussbredden multiplicerat med förhämtningsdjupet för minnet.

Blockera nummertaggar istället för adresstaggar

I det följande antas att cachelinjer bara någonsin läses och skrivs från adresser vars adress kan divideras med (byte) längden på cachelinjen.

exempel

En cachelinje sägs vara 64 byte. Det bör specificeras att data endast kan läsas och skrivas med startadresser t.ex. B. 0, 64, 128, 192, 256, ... Bakgrundsmediet är uppdelat i block som är lika stora som en cachelinje.

Då behöver inte hela (start) adressen för data lagras i adresstaggarna, utan bara hur många datablock som cachas på bakgrundsmediet. Genom att välja lämpliga nummer (befogenheter två) i det binära systemet kan taggarna sparas på ett platsbesparande sätt; detta påskyndar kontrollen av om en begärd adress finns i cachen.

Block / meningsindelning av taggarna

Helt associativ cache

Blocken (cachelinjer) i en cache kan sammanfattas i så kallade uppsättningar. Endast en av posterna är då ansvarig för en specifik adress. Inom en post tjänar alla block endast en del av alla tillgängliga adresser. Följande är variabeln för det totala antalet cacheblock och för antalet block per mening, kallad associativitet. Så då består cachen av Meningar.

organisation Antal uppsättningar Associativitet
DM 1
FA 1 ( )
SA

Beroende på hur mycket denna uppdelning görs talar man om en av de tre typerna av cache -organisation:

Kartlagt direkt (Engl. Direct mapped, short DM)
, det vill säga varje block representerar sin egen mening, så det finns lika många meningar som det finns block. Således är exakt ett cacheblock ansvarig för en given adress. Så det finns en direkt mappning mellan bakgrundsminnesadressen och cacheblocken, därav namnet. När du begär en sådan cache behöver du bara läsa ut ett enda cacheblock (mer exakt, kontrollera den associerade taggen , se nedan), vilket minimerar maskinvarukraven för taggkomparatorn. I gengäld är cacheminnets effektivitet begränsad, eftersom det kan finnas gratis cacheblock som inte används, se Conflict Miss nedan.
Helt associativ, FA för kort
, det vill säga, det finns bara en mening som innehåller alla block. Det betyder att varje adress i varje cacheblock kan cachas. När du gör en begäran till cacheminnet är det därför nödvändigt att kontrollera alla cachetaggar. Eftersom cacheminnen måste vara så snabba som möjligt görs detta parallellt, vilket ökar mängden hårdvara som krävs för taggkomparatorer. Fördelen är dock att cacheminnet alltid kan lagra data så länge cacheblocket fortfarande är ledigt.
Ange associativ eller set associativ, SA för kort
är mellan 2 och valda, dvs cacheblocken finns i uppsättningar av varje Ordnade i block. Så här är direkt mappade cacher utvalda fullt associativt (dvs. fritt). Denna cache kallas då n-faldig mening -associativ eller n-faldig associativ för kort . Denna typ av cache representerar en kompromiss mellan hårdvarukomplexitet och effektivitet i cachen: jämfört med en DM -cache får du effektivitet, jämfört med en FA -cache sparar du hårdvara.

De två första är ett specialfall av den meningsassociativa cachen. Den direktmappade och den fullständigt associerade cachen kan således härledas från den set-associativa cachen: n = 1 leder till en direkt mappad cache, n = m till en fullt associativ cache.

Förklaring baserad på ett exempel

Huvudstorleken på en cache är:

  • Storleken på lagrade data (dvs cacheminnets storlek): här i exemplet 64 KiB
  • Storleken på det adressutrymme som ska täckas: här i exemplet 4 GiB
  • Längden på en cachelinje: här i exemplet 64 byte
  • Dataens granularitet: här i exemplet 1 byte
  • Förekomst av smutsiga och giltiga taggar.

Oavsett struktur består cachen av 64 KiB / 64 byte = 1024 cachelinjer

Helt associativ cache
31 30: e 29 28 27 26 25: e 24 23 22: a 21 20: e 19: e 18: e 17: e 16 15: e 14: e 13 12: e 11 10 9 8: e 7: e 6: e 5 4: e 3 2 1 0
Adresstaggens längd Byte position

Det finns en cachegrupp som innehåller alla 1024 cachelinjer. Varje huvudminnesdataord kan lagras i vilken som helst av 1024 cachelinjer i en cachegrupp. 1024 jämförare krävs, som måste jämföra log2 (4 GiB / 64 byte) = log2 (4 GiB) -log2 (64 byte) bitar = 32-6 = 26 bitar. Dessa 26 bitar är kopplade till varje cachelinje som en adresstagg. Hårdvara:

  • 1024 jämförare
  • 1024 × 64 × 8 bitars verklig cache
  • 1024 × 26 bitars adresstagg
  • 1024 × 64 bitars giltiga taggar
  • 1024 × 64 bitars smutsiga taggar
  • 1024 ×? bit för LRU -taggarna
Direktmappad cache / enkel eller icke-associativ cache
31 30: e 29 28 27 26 25: e 24 23 22: a 21 20: e 19: e 18: e 17: e 16 15: e 14: e 13 12: e 11 10 9 8: e 7: e 6: e 5 4: e 3 2 1 0
Adresstaggens längd cachegrupp används Byte position

Det finns 1024 cachegrupper, var och en med en cachelinje. Varje huvudminnesdataord kan endast lagras i denna cachelinje som tillhör dess adress. Cachegruppen resulterar från bitarna 15 till 6 i adressen. Endast en komparator krävs, som måste jämföra log2 (4 GiB) -log2 (64 KiB) bitar = 16 bitar. Dessa 16 bitar är kopplade till varje cachelinje som en adresstagg. Hårdvara:

  • En jämförare
  • 1024 × 64 × 8 bitars verklig cache
  • 1024 × 16 bitars adressetikett
  • 1024 × 64 bitars giltiga taggar
  • 1024 × 64 bitars smutsiga taggar
  • Inga LRU -taggar
Dubbel associerad cache
31 30: e 29 28 27 26 25: e 24 23 22: a 21 20: e 19: e 18: e 17: e 16 15: e 14: e 13 12: e 11 10 9 8: e 7: e 6: e 5 4: e 3 2 1 0
Adresstaggens längd cachegrupp används Byte position

Det finns 512 cachegrupper med två cachelinjer vardera. Varje huvudminnesdataord kan lagras i en av de två cachelinjerna som tillhör dess adress. Cachegruppen resulterar från bitarna 14 till 6 i adressen. Två jämförare krävs, som måste jämföra log2 (4 GiB) -log2 (64 KiB) +1 bitar = 17 bitar. Dessa 17 bitar är kopplade till varje cachelinje som en adresstagg. Hårdvara:

  • Två jämförare
  • 1024 × 64 × 8 bitars verklig cache
  • 1024 × 17 bitars adresstagg
  • 1024 × 64 bitars giltiga taggar
  • 1024 × 64 bitars smutsiga taggar
  • 1024 × 1 bit LRU -taggar
2 ^ n-faldig associativ cache
31 30: e 29 28 27 26 25: e 24 23 22: a 21 20: e 19: e 18: e 17: e 16 15: e 14: e 13 12: e 11 10 9 8: e 7: e 6: e 5 4: e 3 2 1 0
Adresstaggens längd cachegrupp används Byte position

Det finns 1024/2 ^ n cachegrupper med 2 ^ n cachelinjer vardera. Varje huvudminnesdataord kan lagras i en av de 2 ^ n cachelinjer som tillhör dess adress. Cachegruppen resulterar från bitarna 15- (n-1) till 6 i adressen. 2 ^ n komparatorer krävs, som måste jämföra log2 (4 GiB) -log2 (64 KiB) + n bitar = 16+ (n -1) bitar. Dessa 16+ (n-1) bitar är kopplade till varje cachelinje som en adresstagg. Hårdvara:

  • 2 ^ n jämförare
  • 1024 × 64 × 8 bitars verklig cache
  • 1024 × (16 + n-1) bit adresstagg
  • 1024 × 64 bitars giltiga taggar
  • 1024 × 64 bitars smutsiga taggar
  • 1024 × flera bitars LRU -taggar

Cache träffar och missar

Processen där data för en begäran till en cache är tillgänglig kallas en "cache hit", det omvända kallas en "cache miss".

För att få kvantitativa åtgärder för att utvärdera effektiviteten hos en cache definieras två parametrar:

Träffhastighet
Antalet förfrågningar med en cache -träff dividerat med det totala antalet förfrågningar som gjorts till denna cache. Som man enkelt kan se från definitionen är denna mängd mellan noll och en. En träfffrekvens på t.ex. B. 0,7 (= 70%) betyder att i 70% av alla förfrågningar till cacheminnet kunde cacheminnet leverera data direkt och måste matcha 30% av alla förfrågningar.
Fröken hastighet
Analogt med träfffrekvensen definieras detta som antalet förfrågningar för vilka data inte fanns i cacheminnet dividerat med antalet totala förfrågningar. Följande gäller: Missfrekvens = 1 - träfffrekvens.

Det finns tre typer av cachemissar:

Kapacitet
Cachen är för liten. Data fanns tillgänglig i cachen men togs bort från den. Om denna adress sedan nås igen kallas denna miss som en "kapacitetsmiss". Den enda åtgärden är en större cache.
Konflikt
På grund av den set-associerade organisationen (gäller även DM-cacher) är det möjligt att det inte längre finns tillräckligt med utrymme i en uppsättning medan det fortfarande finns lediga cacheblock i andra uppsättningar. Sedan måste ett block tas bort från den överfyllda posten, även om cachen faktiskt fortfarande har utrymme. Om detta borttagna block nås igen kallas denna cachemiss för "konfliktmiss". Detta kan åtgärdas genom att öka cacheblocken per post - det vill säga öka associativiteten. När det gäller fullständigt associerande cacheminnen (som bara har en post) finns det inga konfliktmissar på grund av principen.
Obligatorisk
En "obligatorisk fröken" eller "kallstartfröken" är namnet som ges till den första åtkomsten till en adress vars data ännu inte finns i cacheminnet, och samtidigt har cachen fortfarande ledigt utrymme. Skillnaden mot de andra två missarna är att det inte finns något förtryck här, men ett block beskrivs för första gången / nytt. Det är svårt eller omöjligt att förhindra. Moderna processorer har " prefetcher " -enheter som automatiskt laddar data i cacheminnet spekulativt om det fortfarande finns utrymme där. Detta för att minska antalet obligatoriska missar.

Dessa tre typer är också kända som "The Three Cs" i korthet. I multiprocessorsystem, när ett cachekoherensprotokoll av typen Write-Invalidate används, kan en fjärde "C" läggas till, nämligen en "Coherency Miss": När en processor skriver till ett cacheblock, samma block i cachen i en andra processor kastas ut Om den andra processorn måste få åtkomst till en adress som täcktes av detta fjärrcache -block, leder detta till en sammanhängande miss.

Arbetssätt

När du hanterar cachen är det meningsfullt att bara behålla de blocken i cacheminnet som ofta används. Det finns olika ersättningsstrategier för detta ändamål. En variant som ofta används är LRU -strategin ( l öst r ecently u sed ), där blocket som inte har nåtts på längst tid alltid byts ut. Moderna processorer (t.ex. AMD Athlon ) implementerar mestadels en pseudo LRU -ersättningsstrategi som fungerar nästan som riktig LRU, men är lättare att implementera i hårdvara.

Förskjutningsstrategier

FIFO (First In First Out)
Den äldsta posten undertrycks.
LRU (minst nyttjat)
Posten som inte har nåtts på länge har förskjutits.
LFU (minst använda)
Posten som sällan läses undertrycks. Det lagrar dock inte fullständiga tidsstämplar , vilket skulle kräva ett relativt långt heltal. Snarare används bara några bitar (två är vanliga, men bara en är möjlig) för att markera en cachepost som mer eller mindre frekvent. Bitarna uppdateras parallellt med en förskjutning.
Slumpmässig
En slumpmässig post undertrycks.
KLOCKA
Data lagras i cacheminnet i den ordning de öppnas. När ett dataobjekt nås, ställs en bit in för detta cacheblock. I händelse av en miss sökes det första datumet utan en bit från framsidan till baksidan; detta ersätts. Biten rensas för all data som har gått igenom. Det är också markerat vilket datum som senast laddades i cachen. Därifrån börjar sökningen efter ett datum, som kan ersättas.
Optimal
Laszlo Belady -metoden, där minnesområdet förskjuts som inte kommer att ha nåtts längst, är optimalt. Den kan dock bara användas om hela programsekvensen är känd i förväg (dvs. det är en så kallad offline-procedur, till skillnad från FIFO och LRU, som är online-procedurer). Programsekvensen är nästan aldrig känd i förväg; därför kan bästa praxis inte användas i praktiken. Den optimala algoritmen kan dock fungera som en jämförelse för andra metoder.

Skrivstrategi

I princip finns det två möjligheter för skrivåtkomst till ett block som finns i cacheminnet:

Kopiera tillbaka (skriva tillbaka)
Vid skrivning lagras inte blocket som ska skrivas omedelbart i nästa högre minnesnivå, utan först i cacheminnet. Detta skapar en inkonsekvens mellan cachen och minnet som ska cachelagras. Den senare innehåller därför föråldrad information. Först när ordet förskjuts från cacheminnet skrivs det också till nästa högre minnesnivå. Dessutom får varje cacheblock en så kallad smutsig bit, som anger om blocket måste kopieras tillbaka när det byts ut. Detta leder till problem med minnesåtkomst från andra processorer eller DMA -enheter, eftersom de skulle läsa föråldrad information. Detta kan åtgärdas genom cachekoherensprotokoll som t.ex. B. MESI för UMA -system.
Kontinuerligt skrivande (genomskrivning)
Blocket som ska skrivas lagras omedelbart i nästa högre minnesnivå. Detta säkerställer konsistens. Så att processorn inte behöver vänta varje gång tills blocket lagras i nästa högre minnesnivå (vilket är långsammare än cachen) används en skrivbuffert. Men när detta fylls måste processorn stanna och vänta.

Analogt med ovanstående finns det i princip två alternativ för skrivåtkomst till ett block som inte finns i cacheminnet:

skriva-fördela
Som med en vanlig cachemiss, hämtas blocket från nästa högre minnesnivå. Motsvarande byte som ändrades av skrivåtkomst skrivs sedan över i det block som just kommit.
icke-skriva-fördela
Det skrivs till nästa högre minnesnivå som går förbi cachen, utan att det tillhörande blocket laddas in i cachen. Detta kan vara fördelaktigt för vissa applikationer där mycket skriven data aldrig läses igen. Att använda icke-skriv-allokerar förhindrar att andra, möjligen viktiga block flyttas och minskar därmed misshastigheten.

Vissa instruktionsuppsättningar innehåller instruktioner som gör det möjligt för programmeraren att uttryckligen ange om data som ska skrivas ska skrivas förbi cacheminnet.

Vanligtvis används antingen kombinationen återskrivning med skrivfördelning eller genomskrivning med icke-skrivfördelning . Den första kombinationen har fördelen att successiva skrivåtkomst till samma block (lokalitetsprincip) behandlas fullständigt i cachen (förutom den första missen). Detta är ingen fördel i det andra fallet, eftersom varje skrivåtkomst till huvudminnet ändå måste, varför kombinationen genomskrivning med skrivfördelning är ganska ovanlig. [4]

Cachespolning

En cachespolning gör att hela innehållet i cacheminnet skrivs tillbaka till bakgrundsminnet. Cacheinnehållet förblir för det mesta orört. Ett sådant förfarande är nödvändigt för att återställa konsistensen mellan cachen och bakgrundsminnet. Detta är till exempel nödvändigt när data från huvudminnet krävs av externa enheter, till exempel vid multiprocessorkommunikation eller vid överföring av en del av huvudminnet som används som utmatningsbuffert till DMA -styrenheten.

Andra

Inmatningar i cachen

Följande lagras i cacheminnet för varje cacheblock:

  • De faktiska uppgifterna
  • Dagen (del av adressen)
  • Flera statusbitar, till exempel:
modifierad eller smutsig
Indikerar om detta cacheblock har ändrats (endast för cache-återkoppling).
olika statusbitar beroende på cachekoherensprotokollet , t.ex. B. en bit vardera för:
ägare
Motsvarar "modifierad och delad". Indikerar att blocket har ändrats och finns i andra cacheminne. Ägaren är ansvarig för att uppdatera huvudminnet när blocket tas bort från cacheminnet. Processorn som senast skriver till cacheblocket blir den nya ägaren.
exklusiv
Indikerar att blocket inte har ändrats och inte finns i någon annan cache.
delad
Ibland har olika betydelser: Med MESI indikerar detta att blocket inte har ändrats, men är också tillgängligt i cacheminne för andra processorer (även oförändrat där). Med MOESI betyder det bara att blocket finns i andra processorcacher. 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:

  1. Ein Webcrawler durchsucht das WWW nach neuen oder veränderten Webseiten und lädt sie (zusätzlich) in
  2. den Suchmaschinen-Cache, über den regelmäßig verschiedene Indizes erstellt werden. Über diese Indizes sucht
  3. 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

Einzelnachweise

  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
  5. Ein kurzer Einblick in die Funktionalität des Google-Caches ( Memento vom 28. Juli 2017 im Internet Archive )“ (Mit Suchfunktion)