Geheugenhiërarchie en caches

Een cache werkt omdat de volgende geheugentoegang vaak verband houdt met een recente toegang. Gedurende een korte periode gebruiken de meeste programma's slechts een klein deel van hun adresruimte. Dit patroon heet lokaliteit. Een cache houdt dat actieve deel dicht bij de processor, waar toegangen snel kunnen worden afgehandeld.

Hergebruik in tijd en ruimte

Temporele lokaliteit betekent dat een gegeven kort na een toegang opnieuw wordt gebruikt. Een lus haalt herhaaldelijk de instructies van zijn lichaam op. Een lopend totaal wordt vaak gelezen en bijgewerkt. Door die gegevens beschikbaar te houden, hoeven ze niet opnieuw uit een langzamer niveau te worden opgehaald.

Ruimtelijke lokaliteit betekent dat gegevens op nabijgelegen adressen worden aangesproken. Bij het doorlopen van een array worden aangrenzende elementen gelezen en bij code zonder sprongen worden opeenvolgende instructies opgehaald. Een cache benut dit door bij een misser een heel blok, ook cachelijn genoemd, op te halen. Nabijgelegen bytes komen aan voordat het programma erom vraagt.

Deze patronen kunnen samengaan. De instructies van een lus liggen naast elkaar en worden herhaaldelijk uitgevoerd, dus heeft de instructiestroom zowel ruimtelijke als temporele lokaliteit. Een array-element dat precies één keer wordt gelezen, wordt niet temporeel hergebruikt, ook al heeft de doorloop van de omringende array ruimtelijke lokaliteit.

Tel blokken bij het doorlopen van een array

Bekijk deze C-lus met gehele getallen van 4 bytes en cacheblokken van 64 bytes:

for (int i = 0; i < 1000; i++) {
    sum += a[i];
}

Een blok bevat $64\mathrm{/}4=16$ gehele getallen. De array neemt $1000\times 4=4000$ bytes in. Als het eerste element op een blokgrens ligt, raakt de doorloop $\lceil 4000\mathrm{/}64\rceil =63$ blokken: 62 volledige blokken en één gedeeltelijk blok.

In een aanvankelijk lege cache zonder vooraf ophalen of verstoring levert de eerste toegang tot elk blok een misser op. De overige elementen in dat blok leveren treffers op. De array veroorzaakt dus 63 missers bij 1000 toegangen, of ongeveer 6,3%. Als je één misser per element telt, zie je alle bruikbare naburige gegevens over het hoofd die met elke misser worden opgehaald.

De bronvariabelen sum en i worden vaak opnieuw gebruikt. Een compiler houdt ze echter meestal in registers, zodat hun hergebruik op bronniveau niet per se toegangen tot de gegevenscache oplevert. Analyseer bij het schatten van cacheverkeer de geheugentoegangen die het gecompileerde programma uitvoert.

De werkverzameling moet passen en samen bewaard kunnen worden

De werkverzameling is de verzameling blokken die tijdens een gekozen tijdvenster wordt gebruikt. Als ze in de cache passen en de plaatsingsregels toestaan dat ze samen worden bewaard, leveren herhaalde toegangen na het eerste laden meestal treffers op. Het tijdvenster is van belang: een heel programma kan enorm zijn terwijl één actieve lus slechts enkele blokken gebruikt.

Capaciteit alleen is niet genoeg. Twee veelgebruikte blokken kunnen op één direct afgebeelde positie worden afgebeeld en elkaar verdringen terwijl andere posities leeg blijven. Een werkverzameling kan dus qua aantal bytes passen en toch niet in de cache blijven.

Verspreide knooppunten van een gekoppelde lijst en willekeurige opvragingen in een grote hashtabel hebben vaak weinig ruimtelijke lokaliteit. Ook een kolomdoorloop van een rijgewijs opgeslagen array slaat veel naburige elementen over. Deze patronen halen bytes binnen die mogelijk ongebruikt blijven voordat ze worden verdrongen. Hardware benut de lokaliteit van het toegangspatroon; door de indeling of doorloop van het programma te veranderen, kun je een groter deel van elk opgehaald blok bruikbaar maken.

Bij geheugentechnologieën worden snelheid, dichtheid, kosten en behoud van gegevens tegen elkaar afgewogen. De processor heeft snelle toegang tot een kleine hoeveelheid gegevens nodig en betaalbare ruimte voor veel meer. SRAM, DRAM en flash voorzien elk in een ander deel van die behoefte.

Vergelijk de cellen

Een SRAM-cel is snel maar neemt aanzienlijk oppervlak in, waardoor SRAM relatief duur per bit is. DRAM-cellen zijn kleiner, zodat DRAM meer capaciteit biedt tegen lagere kosten per bit. Hun lading lekt weg. Bij verversing worden rijen binnen een vast tijdvenster gelezen en hersteld; DDR4 gebruikt bij normale temperatuur een venster van 64 ms. “Statisch” in SRAM betekent geen verversing, niet dat gegevens na stroomuitval bewaard blijven.

Waarom de DRAM-toegangstijd varieert

DRAM is ingedeeld in banken, met rijen en kolommen in elke bank. Bij het activeren van een rij wordt die naar een rijbuffer gekopieerd. Lees- en schrijfbewerkingen selecteren vervolgens kolommen uit die open rij. Om een andere rij in dezelfde bank te openen, moet de bank eerst worden voorgeladen. Bij toegang tot een al open rij is dat wisselen van rij niet nodig.

Opeenvolgende kolommen kunnen in een burst worden overgedragen, wat geschikt is voor het ophalen van een cacheblok. Door verzoeken over banken en kanalen te verdelen kunnen overdrachten overlappen. DDR-geheugen draagt gegevens over op beide klokflanken. Deze eigenschappen verhogen de snelheid waarmee gegevens worden geleverd zonder de wachttijd op de eerste gegevens weg te nemen.

Onderscheid latentie en bandbreedte

Latentie is de vertraging totdat de eerste gegevens aankomen. Bandbreedte is de hoeveelheid die per tijdseenheid wordt overgedragen. Een interface met hoge bandbreedte kan nog steeds een lange initiële vertraging hebben.

Een DDR5-4800-kanaal met een gezamenlijk datapad van 64 bits draagt bijvoorbeeld 8 bytes per overdracht over. De pieksnelheid is $4800\times {10}^6\times 8=\mathrm{38,4}\times {10}^9$ bytes/s, of 38,4 GB/s. De aanhoudende bandbreedte voor een applicatie kan lager zijn doordat opdrachten, rijwisselingen en ander werk tijd kosten.

Als een verzoek 60 ns wacht en daarna een blok van 64 bytes ontvangt met 16 GB/s, is de overdrachtssnelheid 16 bytes/ns. De overdracht duurt $64\mathrm{/}16=4$ ns, wat in totaal ongeveer 64 ns geeft. Alleen de bandbreedte verbeteren verkort het deel van 4 ns, niet de eerste 60 ns.

Flash bewaart gegevens maar schrijft anders

NAND-flashgeheugen leest en programmeert pagina's van enkele KiB. Om een geprogrammeerde pagina opnieuw te gebruiken, moet het grotere wisblok met vele pagina's worden gewist. Pagina's lezen duurt doorgaans tientallen microseconden, programmeren honderden microseconden tot enkele milliseconden en wissen milliseconden.

Programmeer- en wiscycli laten cellen slijten. Compact flashgeheugen met meerdere bits per cel ondersteunt vaak enkele duizenden cycli, terwijl cellen met één bit er ongeveer 100.000 kunnen ondersteunen. Controllers gebruiken slijtageverdeling om schrijfbewerkingen over blokken te spreiden.

Ter vergelijking: een SRAM-toegang duurt ongeveer 1 ns, DRAM ongeveer 50–100 ns, NAND lezen ongeveer 25–100 µs en een schijftoegang ongeveer 5–10 ms. Werkelijke apparaten verschillen. De hiërarchie combineert deze technologieën omdat één technologie hun voordelen in snelheid, capaciteit en prijs niet tegelijk kan bieden.

De geheugenhiërarchie plaatst kleine, snelle opslag dicht bij de processor en steeds grotere opslag verder weg. Dankzij lokaliteit kunnen de kleine niveaus een groot deel van de verzoeken afhandelen, terwijl de lagere niveaus capaciteit bieden.

Niveaus en overdrachtseenheden

Een typisch pad loopt via registers, L1, L2, L3, hoofdgeheugen en opslag. L1 heeft meestal afzonderlijke instructie- en gegevenscaches van elk ongeveer 32–64 KiB per kern. L2 is vaak honderden KiB tot enkele MiB per kern, terwijl L3 vaak wordt gedeeld en enkele tot tientallen MiB bevat. Het hoofdgeheugen bevat vele GiB en de opslag honderden GB of meer. Ontwerpen verschillen in grootte en verdeling.

Op een processor van ongeveer 3 GHz zijn representatieve latentietijden voor laden ongeveer 4–5 cycli voor L1, 12–15 voor L2, 30–50 voor L3 en 200–300 voor DRAM. Een L1-cache kan elke cyclus een nieuw verzoek accepteren, ook als één verzoek meerdere cycli nodig heeft om te worden voltooid: doorvoer en latentie beschrijven verschillende eigenschappen.

Gegevens reizen door caches in blokken, meestal van 64 bytes. Virtueel geheugen gebruikt pagina's, meestal van 4 KiB, bij het verplaatsen van pagina-inhoud tussen geheugen en opslag. Een cachelijn en een pagina dienen een vergelijkbaar doel voor groepering op verschillende schaal; het zijn niet dezelfde overdrachtseenheden.

Treffers, missers en tijd

Een treffer betekent dat een niveau de gevraagde gegevens bevat. Een misser betekent dat het niveau de gegevens van onderaf moet ophalen. Beide woorden hebben betrekking op het niveau dat wordt gecontroleerd: een L1-misser kan nog steeds een L2-treffer zijn.

De trefferfractie is het aantal treffers gedeeld door het aantal toegangen en de misserfractie is één min de trefferfractie. De cachetoegangstijd omvat het controleren van het niveau en het vaststellen of het verzoek een treffer oplevert. De extra vertraging bij een cachemisser is de extra tijd die bij een misser nodig is om het blok op te halen en te leveren.

Stel dat een vereenvoudigde cache een toegangstijd van 1 cyclus, een trefferfractie van 97% en een extra vertraging van 100 cycli bij een misser heeft. Elke toegang kost 1 cyclus, terwijl 3% nog eens 100 cycli kost:

Een misser duurt in dit voorbeeld 101 cycli. Als je 100 als de volledige tijd voor een misser gebruikt, reken je de tijd voor het opzoeken in de cache niet consequent mee. Zelfs bij een hoge trefferfractie blijven dure missers zichtbaar in het gemiddelde.

Wie beheert elk niveau?

De compiler wijst geschikte waarden toe aan registers. Cachehardware verplaatst blokken automatisch tijdens laad- en opslagbewerkingen en het ophalen van instructies. Programma's gebruiken adressen; ze selecteren geen cacheposities. Het besturingssysteem beheert met hardwareondersteuning de afbeeldingen van virtueel geheugen en handelt pagina's af die naar het hoofdgeheugen moeten worden gehaald.

Door L1 op te splitsen voor instructies en gegevens kan een pipeline tegelijk een instructie ophalen en gegevens benaderen zonder om één cachepoort te concurreren. Lagere caches zijn meestal gecombineerd en slaan zowel instructie- als gegevensblokken op.

Sommige hiërarchieën zijn inclusief: een blok dat boven aanwezig is, heeft ook een kopie eronder. Andere zijn exclusief of niet-inclusief, zodat een kopie in elke lagere cache niet gegarandeerd is. Teken een hiërarchie als een zoek- en overdrachtspad, niet als een belofte dat alle niveaus identieke deelverzamelingen bevatten.

Een grotere L1-cache kan missers verminderen, maar de toegangsvertraging en het energieverbruik verhogen. Door grotere lagere caches toe te voegen kan het ontwerp L1 snel houden en veel van de L1-missers opvangen voordat ze DRAM bereiken. Beoordeel die afweging op basis van toegangstijd, niet alleen capaciteit.

Een byteadres geeft één byte in het geheugen aan. Een cache haalt een heel blok op, dus bepaalt de cache bij het opzoeken eerst dat blok en selecteert daarna de gevraagde bytes daarin. In een direct afgebeelde cache heeft elk blok precies één mogelijke positie.

Verdeel het adres naar functie

Bij een blokgrootte van $2^b$ bytes vormen de laagste $b$ adresbits de offset. Door het byteadres door de blokgrootte te delen en de rest weg te laten, krijg je het blokadres. De rest is de offset.

Als de cache $E$ posities heeft, is de positie-index

Als het aantal posities een macht van twee is, bestaat de index uit de groep adresbits direct boven de offset. De resterende hoge bits vormen de adrestag, die de cache vertelt welk van de vele blokken die een index delen aanwezig is.

De veldvolgorde van hoge naar lage bits is adrestag | index | offset. Voor een adresbreedte van $A$ bits geldt:

Gebruik het aantal posities voor de indexberekening. Als je de logaritme van de capaciteit in bytes neemt, tel je de offsetbits een tweede keer.

Werk een voorbeeld met 16 KiB uit

Een direct afgebeelde cache van 16 KiB met blokken van 64 bytes heeft $16384\mathrm{/}64=256$ posities. De offset neemt 6 bits in, de index 8 bits en de adrestag $32-8-6=18$ bits bij adressen van 32 bits.

Voor byteadres 0x1234ABCD geven de laagste 6 bits offset 13, of 0x0D. Als je die bits verwijdert, krijg je blokadres 0x48D2AF. De laagste 8 bits daarvan zijn 0xAF, dus is de index 175. De resterende bits geven adrestag 0x48D2.

Het byteadres kan uit deze velden worden gereconstrueerd: voeg de adrestag, de 8-bitsindex en de 6-bitsoffset samen. De veldbreedtes zijn van belang omdat een hexadecimaal cijfer 4 bits voorstelt; de grenzen hoeven niet tussen hexadecimale cijfers te vallen.

Een overeenkomende adrestag vereist een geldige positie

Elke positie bevat gegevens, een adrestag en een geldigheidsbit. De index selecteert de positie. Een treffer vereist zowel een gezette geldigheidsbit als een overeenkomst tussen de opgeslagen en de gevraagde adrestag. Bij het opstarten kan een positie willekeurige bits bevatten; de geldigheidsbit voorkomt dat die bits voor een geladen blok worden aangezien.

Zodra het blok aanwezig is, leveren toegangen tot andere bytes in dat blok ook treffers op. Een treffer vereist niet hetzelfde byteadres als waarmee het blok is opgehaald.

Tel metadata afzonderlijk

De opgegeven cachecapaciteit telt gewoonlijk alleen gegevens. Hier bevat elke positie 512 gegevensbits, 18 tagbits en 1 geldigheidsbit, samen 531 bits. De totale opslag is

De gegevens alleen gebruiken 131.072 bits. Adrestags en geldigheidsbits voegen 4.864 bits toe, ongeveer 3,7% van de gegevensopslag. Een ontwerp met terugschrijven heeft ook wijzigingsbits nodig; complexere ontwerpen hebben meer besturingsinformatie nodig.

De index gebruikt lage blokadresbits zodat opeenvolgende blokken over opeenvolgende posities worden verspreid. Bij een breder adres blijven de breedtes van offset en index gelijk als capaciteit en blokgrootte vast blijven; de extra bits verlengen de adrestag.

Een cachetoegangsregistratie legt vast hoe elke toegang de opgeslagen blokken verandert. Houd voor elke positie een afzonderlijke toestand bij en werk die direct na elke misser bij. Het volgende verzoek gebruikt de bijgewerkte cache, niet de cache zoals die er aan het begin uitzag.

Stel de registratie op

Neem een direct afgebeelde cache van 64 bytes met vier posities van 16 bytes. Die is aanvankelijk leeg. Deel voor elk byteadres door 16 om het blok te vinden en bereken daarna blok modulo 4 voor de index. De adrestag is het bloknummer gedeeld door 4, waarbij het gebroken deel wordt weggelaten. Er zijn 4 offsetbits en 2 indexbits.

Bekijk bij een leesbewerking de geselecteerde positie. Als die geldig is en de adrestag overeenkomt, noteer je een treffer. Noteer anders een misser, vervang het blok en de adrestag van die positie en zet de geldigheidsbit. In een direct afgebeelde cache is geen vervangingskeuze mogelijk.

Volg alle acht toegangen

De eerste toegang vult positie 0 met blok 0. Het volgende adres, 0x04, ligt nog steeds binnen dat blok van 16 bytes en levert dus een treffer op, hoewel het een andere byte aanwijst. 0x40 hoort bij blok 4. Het heeft dezelfde index als blok 0 maar een andere adrestag, dus vervangt het blok 0.

De tweede 0x00 mist daardoor. Eerder gebruik alleen garandeert geen treffer: het blok moet nog steeds aanwezig zijn. Het verzoek om 0x14 laadt blok 1 op positie 1 en laat positie 0 ongewijzigd.

Daarna laadt 0x44 blok 4 opnieuw op positie 0. 0x08 heeft blok 0 nodig en verdringt blok 4. Ten slotte laadt 0x84 blok 8 op diezelfde positie. Aan het einde bevat positie 0 blok 8 en positie 1 blok 1; posities 2 en 3 blijven ongeldig.

Interpreteer het gedrag

Er is één treffer en er zijn zeven missers, dus is de trefferfractie $1\mathrm{/}8=\mathrm{12,5}\mathrm{\%}$. Blokken 0, 4 en 8 concurreren om positie 0. De cache heeft vier posities, maar dit toegangspatroon gebruikt er slechts twee. De herhaalde verdringingen worden veroorzaakt door afbeeldingsconflicten, niet door een tekort aan totale opslagruimte voor de vier verschillende blokken.

Door een blok te vullen komen alle bytes van dat blok beschikbaar. Bij een opeenvolgende doorloop kan één misser daardoor veel volgende elementen bedienen. Hier nemen de conflicterende toegangen dat voordeel steeds weg voordat de volgende nabijgelegen byte wordt opgevraagd.

Benoem voor een betrouwbare registratie byteadressen en bloknummers expliciet. Als je modulo 4 rechtstreeks op het byteadres toepast, sla je de deling door de blokgrootte over en stuur je verzoeken naar de verkeerde posities. Noteer de vervanging ook wanneer het nieuwe blok eerder is geladen: elke misser plaatst het gevraagde blok en de bijbehorende adrestag op de gekozen positie.

Een set-associatieve cache geeft een blok meerdere mogelijke posities zonder de hele cache te doorzoeken. De index selecteert een set en het blok kan elke positie in die set innemen. Dit vermindert conflicten tussen blokken die een index delen.

Bereken sets en velden

Voor gegevenscapaciteit $C$, blokgrootte $B$ en associativiteit $n$ geldt:

De setindex is het blokadres modulo het aantal sets. De offset hangt nog steeds alleen af van de blokgrootte. De adrestag bevat de resterende hoge bits.

Een 8-weg cache van 32 KiB met blokken van 64 bytes heeft 512 blokken en 64 sets. Bij 32-bitsadressen zijn de breedtes van offset, index en adrestag 6, 6 en 20 bits. Adres 0x1234ABCD heeft offset 13, set 47 en adrestag 0x1234A.

Bij vaste capaciteit en blokgrootte halveert een verdubbeling van de associativiteit het aantal sets. Eén indexbit wordt een tagbit; er komt geen gegevenscapaciteit bij.

Bij het opzoeken wordt de adrestag parallel vergeleken met alle geldige adrestags in de gekozen set. Een overeenkomende positie levert de gegevens via een selector. Meer posities per set vereisen meer vergelijkingen en selectiehardware, wat de cachetoegangstijd en het energieverbruik kan verhogen.

Vervang pas een blok als de set vol is

Gebruik eerst een ongeldige positie. Als alle posities bezet zijn, verdringt LRU het blok waarvan de laatste toegang het langst geleden is. Werk de informatie over recent gebruik bij treffers én bij het vullen bij. Een 2-weg set heeft maar één bit nodig om de LRU-positie bij te houden; grotere sets gebruiken vaak pseudo-LRU-benaderingen.

FIFO verdringt het blok dat het eerst is geladen, ook als het onlangs is aangesproken. Willekeurige vervanging kiest een te vervangen blok zonder volledige informatie over recent gebruik bij te houden. Die methode is eenvoudig en kan in grote caches bijna even goed presteren als LRU.

Bekijk de kleine registratie opnieuw met twee posities per set

De cache van 64 bytes met blokken van 16 bytes heeft nu twee sets van twee posities. Blokken 0, 4 en 8 worden op set 0 afgebeeld, terwijl blok 1 op set 1 wordt afgebeeld. Voor 0x00, 0x04, 0x40, 0x00, 0x14, 0x44, 0x08, 0x84 zijn de resultaten misser, treffer, misser, treffer, misser, treffer, treffer, misser.

Blokken 0 en 4 kunnen naast elkaar bestaan, dus leveren herhaalde toegangen ertoe treffers op. Vlak voor de laatste toegang is blok 0 recenter gebruikt dan blok 4. Bij het laden van blok 8 verdringt LRU blok 4. Vier van de acht toegangen leveren een treffer op, tegenover één in de direct afgebeelde versie.

Associativiteit kan eerste-toegangsmissers niet wegnemen en een werkverzameling die groter is dan de capaciteit niet passend maken. Ook kan associativiteit geen conflicten voorkomen wanneer meer dan n veelgebruikte blokken om één n-weg set concurreren. Een herhaalde cyclus van n+1 van zulke blokken kan LRU elke keer laten missen. Door arrays op te vullen kun je veranderen op welke sets ze worden afgebeeld; meer posities per set kiezen is maar één mogelijke reactie op een conflictprobleem.

Een cachemisser is een gebeurtenis met zowel een mechanisme als een oorzaak. Het mechanisme beschrijft hoe het verzoek wordt afgehandeld. De oorzaak verklaart waarom het benodigde blok ontbrak en welke ontwerpwijziging kan helpen.

Handel een leesmisser af

In een eenvoudige pipeline die instructies op volgorde uitvoert, detecteert de cache een ongeldige positie of een niet-overeenkomende adrestag en wacht de processor. De cache vraagt het blok op bij het volgende niveau. Als het gekozen te vervangen blok gewijzigd is, moeten de gewijzigde gegevens door terugschrijven worden bewaard. Het binnenkomende blok wordt met zijn adrestag en geldigheidsbit geplaatst en de wachtende toegang wordt voltooid. Bij een misser in de instructiecache wordt op dezelfde manier op het blok van de instructie gewacht en daarna de instructie opnieuw opgehaald.

Bij het gevraagde woord eerst wordt het benodigde woord als eerste in het terugkerende blok opgevraagd. Bij vroegtijdig hervatten kan de uitvoering doorgaan zodra dat woord aankomt. Een niet-blokkerende cache kan andere treffers afhandelen en openstaande missers bijhouden terwijl een processor die instructies buiten de programmavolgorde uitvoert onafhankelijk werk doet. Deze mechanismen verminderen de wachttijd; ze laten de oorspronkelijke gegevensafhankelijkheid niet verdwijnen.

Gebruik de drie C's

Pas eerst de test voor eerste toegang toe. De eerste toegang tot een blok is een eerste-toegangsmisser, ook als de bestemmingspositie al bezet is. Vergelijk bij latere missers de werkelijke cache met een volledig associatieve LRU-cache met dezelfde gegevenscapaciteit en blokgrootte, waarbij beide dezelfde toegangsgeschiedenis ontvangen.

In de eerdere registratie met vier posities veroorzaken blokken 0, 4, 1 en 8 elk één eerste-toegangsmisser. De direct afgebeelde cache mist ook bij de herhaalde toegangen tot blokken 0 en 4. Een volledig associatieve cache met vier posities kan alle vier verschillende blokken bewaren, dus zijn die drie herhaalde missers conflictmissers. Er zijn geen capaciteitsmissers.

Kies een wijziging die de oorzaak aanpakt

Meer capaciteit kan een grotere werkverzameling vasthouden. Meer associativiteit kan ervoor zorgen dat conflicterende blokken naast elkaar passen. Een grotere blokgrootte kan ruimtelijke lokaliteit benutten door bij elke vulling meer bruikbare naburige gegevens binnen te halen.

Blokgrootte heeft tegengestelde effecten. Bij een vaste gegevenscapaciteit betekenen grotere blokken dat minder blokken tegelijk aanwezig zijn. Ongebruikte bytes nemen cacheruimte in, niet-gerelateerde bruikbare blokken kunnen worden verdrongen en elke overdracht kan langer duren. De misserfractie daalt vaak eerst als de blokgrootte groeit en stijgt daarna wanneer deze kosten zwaarder wegen dan de bruikbare ruimtelijke lokaliteit.

Een grotere cache kan ook een langere opzoektijd hebben en extra posities per set vereisen meer vergelijkingshardware. Beoordeel wijzigingen aan de hand van de gemiddelde toegangstijd, inclusief cachetoegangstijd en extra vertraging bij een misser, in plaats van aan te nemen dat een lagere misserfractie een sneller ontwerp garandeert.

In multicore-systemen kan het ongeldig maken na een schrijfbewerking van een andere kern coherentiemissers veroorzaken. Door vooraf ophalen kan een blok vóór de eerste gevraagde toegang binnenkomen, zodat een misser bij die toegang wordt verborgen die extra capaciteit alleen niet kan voorkomen.

Een opslaginstructie verandert een waarde, dus heeft de hiërarchie een regel nodig om die verandering naar beneden door te geven. Daarbij zijn twee afzonderlijke keuzes betrokken: wat gebeurt er als een opslaginstructie een treffer oplevert en wat als die mist?

Direct doorschrijven en terugschrijven

Een wijzigingsbit legt vast dat een blok in een cache met terugschrijven wijzigingen bevat die nog niet naar het volgende niveau zijn geschreven. Een ongewijzigd te vervangen blok hoeft niet te worden teruggeschreven. De gewijzigde gegevens van een te vervangen blok moeten worden bewaard voordat de positie opnieuw kan worden gebruikt. De laadbewerkingen van de processor halen de nieuwe waarde uit de cache, ook terwijl de lagere kopie ouder is.

Bij 100 opslaginstructies naar één variabele van 4 bytes in de cache stuurt direct doorschrijven zonder samenvoeging 100 schrijfbewerkingen, of 400 bytes aan gegevens. Terugschrijven kan die wijzigingen combineren in één schrijfbewerking van een blok van 64 bytes bij verdringing. Deze vergelijking telt de gegevens van de bijwerkingen, zonder de eerste vulling en protocoloverhead.

Het voordeel hangt af van hergebruik. Herhaaldelijk naar één blok schrijven geeft terugschrijven de kans om bijwerkingen te combineren; schrijfbewerkingen verspreid over veel blokken kunnen leiden tot veel verdringingen van gewijzigde blokken. Lagere caches gebruiken vaak terugschrijven om het verkeer naar DRAM te beperken. L1-gegevenscaches kunnen beide strategieën gebruiken.

Een schrijfbuffer verbergt wachttijd, geen verkeer

Een schrijfbuffer zet schrijfbewerkingen die nog naar een lager niveau moeten in een wachtrij. Bij direct doorschrijven kan de processor doorgaan zodra een opslaginstructie in de buffer staat, in plaats van te wachten tot het lagere geheugen klaar is. Het lagere niveau loopt bij naarmate de gebufferde schrijfbewerkingen worden verwerkt; het kan tijdelijk achterlopen op de waarde in de cache.

De buffer heeft een eindige capaciteit. Als opslaginstructies lang genoeg sneller binnenkomen dan het lagere niveau ze accepteert, raakt de buffer vol en wacht de processor. Een buffer verandert wanneer de processor wacht, niet de blijvend haalbare bandbreedte van de bestemming.

Zonder buffering of overlap wordt een basis-CPI van 1 gelijk aan $1+\mathrm{0,1}\times 100=11$ als 10% van de instructies opslaginstructies zijn en elke opslaginstructie 100 wachtcycli toevoegt. Buffering kan veel van deze vertraging verbergen als de bestemming het gemiddeld bijhoudt.

Behandel een schrijfmisser afzonderlijk

Bij cachetoewijzing bij een schrijfmisser wordt het ontbrekende blok eerst in de cache opgehaald en daarna wordt de opslaginstructie erop toegepast. Dit gaat goed samen met terugschrijven, omdat latere toegangen en schrijfbewerkingen dat blok opnieuw kunnen gebruiken. Bij geen cachetoewijzing bij een schrijfmisser wordt de opslaginstructie naar beneden gestuurd zonder deze cache te vullen. Dit gaat goed samen met direct doorschrijven en kan voorkomen dat bruikbare blokken worden verdrongen tijdens een eenmalige uitvoerstroom.

Dit zijn onafhankelijke strategiekeuzes. Als je weet dat een cache direct doorschrijft, weet je daarmee nog niet of bij een schrijfmisser een lijn wordt toegewezen; een registratie moet beide strategieën specificeren.

Een misser in een cache met terugschrijven die een gewijzigd blok voor vervanging kiest, omvat zowel uitgaande gegevens als de binnenkomende vulling. Dit verhoogt de extra vertraging, tenzij buffers of overlap een deel van het werk verbergen. Andere kernen en I/O-apparaten hebben ook een consistent beeld nodig wanneer het lagere geheugen verouderde gegevens bevat. Coherentie en systeemmechanismen coördineren die zichtbaarheid; een wijzigingsbit alleen legt slechts openstaande wijzigingen vast.

Een hoge trefferfractie is nuttig, maar geen volledige prestatiemaat. Een klein aantal dure missers kan het gemiddelde domineren en een ontwerp dat meer missers voorkomt kan toch verliezen als het opzoeken te langzaam wordt.

Begin met fracties en tijdsdefinities

De twee fracties tellen op tot één. Zet percentages vóór het vermenigvuldigen om in fracties: 5% is 0,05.

De gemiddelde geheugentoegangstijd, of AMAT, is

Elk verzoek controleert de cache, ook verzoeken die missen. De extra vertraging komt na die opzoeking. Je kunt ook de cachetoegangstijd wegen met de trefferfractie en de totale tijd voor een misser met de misserfractie; uitwerken geeft dezelfde formule.

Bij een cachetoegangstijd van 1 cyclus, 5% missers en een extra vertraging van 100 cycli is de AMAT $1+\mathrm{0,05}\times 100=6$ cycli. Bij 2 GHz duurt elke cyclus 0,5 ns, dus is dit 3 ns. Reken alles uit in cycli of alles in tijd en zet zo nodig het eindresultaat om.

Vergelijk volledige ontwerpen

Cache A heeft een opzoektijd van 1,0 ns en 5% missers. Cache B heeft een opzoektijd van 1,2 ns en 3,5% missers. Bij een extra vertraging van 50 ns geldt:

B wint omdat het voorkomen van dure missers de langzamere opzoeking ruimschoots goedmaakt. Als de extra vertraging daalt naar 10 ns, duurt A 1,5 ns en B 1,55 ns. Nu wint A. De waarde van een verbetering van de misserfractie staat in verhouding tot de extra vertraging die ermee wordt vermeden.

Weeg instructie- en gegevenstoegangen correct

Stel dat elke instructie gemiddeld één instructieophaling en 0,3 gegevenstoegangen oplevert. De misserfractie voor instructies is 2% en die voor gegevens 4%. Bij 100 instructies zijn er 100 ophalingen en 30 gegevenstoegangen. Het verwachte aantal missers is $100\times \mathrm{0,02}+30\times \mathrm{0,04}=\mathrm{3,2}$ op 130 toegangen.

De gecombineerde misserfractie is daarom $\frac{\mathrm{0,02}+\mathrm{0,3}\times \mathrm{0,04}}{\mathrm{1,3}}\mathrm{.}$ Bij gelijke cachetoegangstijden van 1 cyclus en extra vertragingen van 100 cycli is de AMAT ongeveer 3,46 cycli per geheugentoegang. Rechtstreeks het gemiddelde van 2% en 4% nemen zou de twee soorten toegang ten onrechte even zwaar laten meetellen.

Schat de extra vertraging door overdracht

Een blokverzoek kan een initiële latentie omvatten, gevolgd door overdrachtstijd. Bij 60 ns latentie, een lijn van 64 bytes en 16 GB/s bandbreedte duurt de overdracht 4 ns, zodat de extra vertraging ongeveer 64 ns is. Bij 3 GHz zijn er 3 cycli/ns, dus is dat 192 cycli.

Controleer wat de opgegeven tijden in een opgave omvatten. Als de volledige toegangstijd bij een misser wordt gegeven, trek dan de tijd voor het opzoeken in de cache af voordat je dat getal als extra vertraging bij een misser gebruikt. Als je de opzoektijd tweemaal meetelt, wordt de AMAT overschat.

AMAT meet de tijd per geheugentoegang. CPI meet het aantal cycli per uitgevoerde instructie. Om ze te verbinden tel je hoeveel instructie- en gegevensverzoeken elke instructie oplevert en hoeveel wachtcycli die verzoeken toevoegen.

Tel de wachttermen op

Voor een eenvoudige processor die instructies op volgorde uitvoert en waarvan de cachetreffers in de basis-CPI zijn opgenomen, voegt een misser waarvan de vertraging niet overlapt de extra vertraging toe. Met instructiemisserfractie $m_I$, gegevenstoegangen per instructie $f_D$, gegevensmisserfractie $m_D$ en extra vertraging $P$ in cycli geldt:

Elke instructie heeft in dit model één verzoek om de instructie op te halen. Alleen laad- en opslaginstructies doen gegevensverzoeken, dus vermenigvuldig je hun misserfractie met hun frequentie. Als hun extra vertragingen verschillen, gebruik je in elke term een afzonderlijke vertraging.

Van verzoeken naar wachtcycli

Neem een basis-CPI van 1,0, een instructiemisserfractie van 2%, een laad- en opslagfrequentie van 30%, een gegevensmisserfractie van 4% en een extra vertraging van 100 cycli bij een misser. Instructiewachtcycli zijn $\mathrm{0,02}\times 100=\mathrm{2,0}$ cycli per instructie. Gegevenswachtcycli zijn $\mathrm{0,3}\times \mathrm{0,04}\times 100=\mathrm{1,2}$. De totale CPI is 4,2.

Met een perfecte cache zou de CPI terugkeren naar 1,0. Bij dezelfde klokfrequentie en hetzelfde aantal uitgevoerde instructies zou dat een versnellingsfactor van 4,2 opleveren. De gegevensmisserfractie is tweemaal zo groot als de instructiemisserfractie, maar instructiemissers kosten in totaal meer tijd omdat elke instructie wordt opgehaald en slechts 30% gegevens aanspreekt.

Vul AMAT niet rechtstreeks in als CPI. AMAT is per toegang en omvat de tijd voor een treffer. De CPI-berekening hier telt alleen wachtcycli op boven op de basisuitvoering die al is meegeteld.

Een hogere klokfrequentie laat elke geheugenwachttijd meer cycli kosten

De DRAM-latentie in nanoseconden wordt niet korter wanneer de klokfrequentie van de processor stijgt. Een verdubbeling van de klokfrequentie zet dezelfde geheugenwachttijd van 100 cycli om in 200 cycli bij de nieuwe frequentie. De CPI van het voorbeeld wordt

Elke nieuwe cyclus duurt half zo lang, dus verandert de relatieve uitvoeringstijd van 4,2 oude cycli per instructie naar het equivalent van 3,7 oude cycli. De versnellingsfactor is $\mathrm{4,2}\mathrm{/}\mathrm{3,7}\approx \mathrm{1,14}$, ruim onder twee.

Verbeteringen verplaatsen de bottleneck

Als de basis-CPI daalt van 1,0 naar 0,5 terwijl de geheugenwachtcycli op 3,2 blijven, wordt de totale CPI 3,7. Wachtcycli nemen nu $\mathrm{3,2}\mathrm{/}\mathrm{3,7}\approx 86\mathrm{\%}$ van de cycli in beslag. Een betere kern maakt de ongewijzigde geheugenvertraging tot een groter deel van de uitvoeringstijd, een voorbeeld van de wet van Amdahl.

Het eenvoudige model telt alle vertragingen door missers als wachtcycli. Uitvoering buiten de programmavolgorde en niet-blokkerende caches kunnen missers laten overlappen met nuttig werk of andere missers. Prestatietellers in de hardware en metingen van de uitvoeringstijd zijn nodig om die overlap op een echte machine te beoordelen. Houd bij het vergelijken van ontwerpen met dit model dezelfde instructiestroom aan en vermeld welke vertragingen al in de basis-CPI zijn opgenomen.

Een lagere cache vermindert de extra vertraging die bij een L1-misser wordt betaald. Die cache heeft een eigen opzoektijd en misserfractie, dus moeten de verwachte kosten van de hiërarchie rekening houden met de fractie verzoeken die elk niveau bereikt.

Houd de noemer bij de fractie

De lokale misserfractie van een niveau is het aantal missers gedeeld door de verzoeken aan dat niveau. De globale misserfractie is het aantal missers gedeeld door alle geheugenverzoeken van de processor.

Als L1 in 4% van de gevallen mist en L2 bij 25% van die verzoeken mist, bereikt slechts $\mathrm{0,04}\times \mathrm{0,25}=\mathrm{0,01}$, of 1% van de oorspronkelijke verzoeken, het geheugen. Een lokale L2-misserfractie van 25% zegt op zichzelf niets over de fractie van alle verzoeken die het geheugen bereikt: L1 heeft de stroom eerst gefilterd.

Voor twee achtereenvolgens gecontroleerde niveaus geldt:

Hier zijn $H_1$ en $H_2$ opzoektijden, $m_1$ en $m_2$ lokale misserfracties en is $P$ de extra vertraging van het geheugen. Alleen L1-missers betalen de L2-opzoektijd. Alleen missers in beide niveaus betalen de extra vertraging van het geheugen.

Reken van binnen naar buiten

Gebruik een L1-toegangstijd van 1 cyclus, een L1-misserfractie van 4%, een L2-toegangstijd van 12 cycli, een lokale L2-misserfractie van 25% en een extra vertraging van het geheugen van 200 cycli. Een verzoek dat L2 bereikt, kost gemiddeld $12+\mathrm{0,25}\times 200=62$ extra cycli. Dus geldt

Zonder L2 zou AMAT $1+\mathrm{0,04}\times 200=9$ cycli zijn. Het opzoeken in L2 voegt werk toe aan elke L1-misser, maar voorkomt dat de meeste van die verzoeken de veel grotere geheugenvertraging betalen.

Vervang $m_2$ binnen de haakjes niet door de globale L2-misserfractie van 1%. Dan zou je tweemaal met de L1-misserfractie vermenigvuldigen. Een equivalente uitgeschreven vorm gebruikt de globale fractie rechtstreeks:

Voeg L3 toe volgens dezelfde logica

Bij een L3-toegangstijd van 40 cycli en een lokale misserfractie van 40% is de L3-afhandelingsterm $40+\mathrm{0,4}\times 200=120$ cycli. De L2-term wordt $12+\mathrm{0,25}\times 120=42$ cycli. De totale AMAT is $1+\mathrm{0,04}\times 42=\mathrm{2,68}$ cycli.

De volledige uitdrukking is $H_1+m_1(H_2+m_2(H_3+m_{3}P))\mathrm{.}$ L3 wordt alleen meegerekend voor verzoeken die in beide hogere niveaus missen. Een niveau met een zeer langzame opzoektijd of zeer weinig treffers kan meer vertraging toevoegen dan het bespaart.

Gebruik aantallen per instructie voor de CPI

Stel dat de basis-CPI 1 is, L1 0,032 missers per instructie oplevert en het geheugen 100 cycli toevoegt. Zonder L2 is de CPI $1+\mathrm{0,032}\times 100=\mathrm{4,2}$. Voeg een L2-cache van 10 cycli toe met een lokale misserfractie van 25%:

Bij dezelfde klokfrequentie is de versnellingsfactor $\mathrm{4,2}\mathrm{/}\mathrm{2,12}\approx \mathrm{1,98}$. De waarde 0,032 is al het aantal missers per instructie, dus zou een extra vermenigvuldiging met de toegangsfrequentie die frequentie tweemaal meetellen.

Virtueel geheugen scheidt de adressen die een programma gebruikt van de plaatsen waar de gegevens in het hoofdgeheugen staan. Elk proces krijgt een eigen virtuele adresruimte. Hardware vertaalt adressen met behulp van afbeeldingen van het besturingssysteem en controleert of elke gevraagde toegang is toegestaan.

Vervang het paginanummer en behoud de offset

Een pagina is een gebied met virtuele adressen van vaste grootte. Een paginakader is een plaats ter grootte van een pagina in het fysieke geheugen. Bij pagina's van 4 KiB bevat elke pagina 4096 bytes, dus heeft de paginaoffset 12 bits nodig. De resterende hoge bits van het virtuele adres vormen het virtuele paginanummer, of VPN.

Een paginatabelitem, of PTE, beeldt een VPN af op een fysiek paginanummer, of PPN. De vertaling vervangt het paginanummer maar behoudt de offset: binnen het fysieke paginakader wordt dezelfde bytepositie geselecteerd.

Voor virtueel adres 0x00403A7C geven de laagste 12 bits offset 0xA7C en is het VPN 0x00403. Als dat VPN op PPN 0x02F1C wordt afgebeeld, is het fysieke adres 0x02F1CA7C. Een 12-bitsoffset toevoegen komt overeen met het PPN met 4096 vermenigvuldigen en de offset optellen; het onverschoven PPN optellen zou het verkeerde adres geven.

Een afbeelding omvat toegangsrechten

Een PTE legt geldigheid, een fysiek paginanummer en rechten zoals lezen, schrijven, uitvoeren en gebruikerstoegang vast. Toegangs- en wijzigingsbits registreren gebruik en wijzigingen. Een bevoorrecht processorregister geeft de paginatabel aan; RISC-V gebruikt satp. Gebruikersprogramma's kunnen deze afbeeldingen niet vrij herschrijven.

Afzonderlijke paginatabellen laten hetzelfde virtuele adres in verschillende processen naar verschillende fysieke gegevens verwijzen. Ze maken ook gericht delen mogelijk: twee processen kunnen virtuele pagina's op hetzelfde fysieke paginakader afbeelden, bijvoorbeeld om alleen-lezen bibliotheekcode te delen. Isolatie en delen zijn beide gevolgen van gecontroleerde afbeeldingen.

Een paginafout vereist aandacht van het besturingssysteem

Een paginafout is een uitzondering die optreedt wanneer de vertaling of de controle van de toegangsrechten niet normaal kan worden voltooid. Een opslaginstructie naar een alleen-lezen afbeelding kan een paginafout veroorzaken, ook als de pagina al in het geheugen staat.

Als een benodigde pagina in het hoofdgeheugen ontbreekt, verkrijgt het besturingssysteem een fysiek paginakader, leest het de pagina uit de opslag, werkt het de afbeelding bij en start het de instructie opnieuw. Een gewijzigde pagina die wordt vervangen moet mogelijk eerst worden teruggeschreven. Sommige fouten worden zonder opslag afgehandeld, zoals het instellen van een afbeelding naar een bestaande pagina of het afhandelen van kopiëren bij schrijven. Een toegang die het systeem niet kan toestaan kan daarentegen eindigen in een procesfout.

Paginafouten waarvoor opslag nodig is, zijn duur. Bij 3 GHz kost een vertraging van 50 µs 150.000 cycli en kost 1 ms 3.000.000 cycli. Grote pagina's spreiden de overdrachtskosten over veel bytes. Een virtuele pagina kan elk geschikt paginakader innemen en gewijzigde pagina's worden teruggeschreven omdat elke opslaginstructie doorsturen naar de opslag te langzaam zou zijn.

Paginatabellen gebruiken ook geheugen

Een vlakke tabel voor virtuele adressen van 32 bits en pagina's van 4 KiB heeft $2^{32-12}=2^{20}$ items nodig. Bij 4 bytes per item is dat 4 MiB per proces. Echte ontwerpen gebruiken tabellen met meerdere niveaus om te voorkomen dat één enorme vlakke tabel voor ijl gevulde adresruimtes moet worden toegewezen; RISC-V Sv39 gebruikt drie niveaus.

Virtueel geheugen omvat adresvertaling, beveiliging en delen, ook wanneer elke gebruikte pagina in DRAM past. Paging met opslag is één toepassing van dat mechanisme, niet het hele doel.

Adresvertaling kan meerdere leesbewerkingen van de paginatabel vereisen voordat een gegevenstoegang doorgaat. Paginatabelitems kunnen treffers opleveren in gewone caches, maar die leesbewerkingen voegen nog steeds werk toe. De vertaalbuffer, of TLB, bewaart recent gebruikte vertalingen, zodat de meeste toegangen het doorlopen van de paginatabel kunnen vermijden.

Volg een toegestane toegang

Het virtuele paginanummer wordt opgezocht in de TLB. Een overeenkomend item levert het fysieke paginanummer en informatie over de toegangsrechten. Na controle van de rechten identificeert het fysieke adres de gegevens in de cachehiërarchie.

Bij een TLB-misser wordt de vertaling verkregen door de paginatabel te doorlopen. Als de afbeelding geldig is en het verzoek toestaat, wordt de vertaling in de TLB geplaatst en gaat de toegang verder. RISC-V en x86-64 gebruiken hiervoor gewoonlijk hardware; sommige architecturen gebruiken softwareafhandelaars. Als de afbeelding het verzoek niet kan afhandelen, veroorzaakt de processor een paginafout voor het besturingssysteem.

Een TLB-misser kan dus samengaan met een treffer of een misser in de gegevenscache. De misser zegt dat de vertaling in de TLB ontbrak, niet dat de pagina in DRAM ontbrak. Omgekeerd kan een TLB-treffer samengaan met een cachemisser of een fout in de toegangsrechten bij een verboden toegang. Vertaling en aanwezigheid van gegevens beantwoorden verschillende vragen.

Tel het geheugen dat door vertalingen wordt gedekt

Het TLB-bereik is het aantal items maal de paginagrootte. Een TLB met 64 items en pagina's van 4 KiB dekt tegelijk 256 KiB. Met pagina's van 2 MiB dekken 64 items 128 MiB. Toegang tot veel verschillende pagina's kan de vertaalcapaciteit uitputten, ook als van elke pagina slechts enkele bytes worden gebruikt.

TLB's op het eerste niveau bevatten vaak tientallen items; lagere TLB-niveaus kunnen honderden of duizenden items bevatten. Hun items omvatten paginanummertags, fysieke afbeeldingen, toegangsrechten en vaak adresruimte-identificatoren. Lokaliteit binnen pagina's en hergebruik bij nabijgelegen toegangen houden de trefferfractie voor vertalingen hoog.

Als bijvoorbeeld 1% van de toegangen vereist dat de paginatabel gedurende 30 cycli wordt doorlopen en de tijd van een TLB-treffer verder wordt verborgen, voegt het doorlopen gemiddeld $\mathrm{0,01}\times 30=\mathrm{0,3}$ cycli per toegang toe. Dit voorbeeld gaat ervan uit dat het doorlopen normaal wordt voltooid en laat de afhandeling van paginafouten buiten beschouwing.

Laat indexering en vertaling overlappen

Een fysiek geïndexeerde, fysiek getagde cache wacht op een fysiek adres voordat die een set selecteert. Een virtueel geïndexeerde, fysiek getagde cache, of VIPT-cache, begint een set te lezen terwijl de TLB vertaalt en vergelijkt daarna fysieke adrestags.

Het eenvoudige VIPT-ontwerp haalt alle index- en blokoffsetbits uit de paginaoffset, omdat vertaling die bits behoudt. Dit vereist

Bij pagina's van 4 KiB heeft een 8-weg cache van 32 KiB 4 KiB per positie en voldoet die. Een 12-weg cache van 48 KiB voldoet ook. Een 8-weg cache van 64 KiB heeft 8 KiB per positie en heeft een paginanummerbit nodig voor de indexering, dus vereist die meer posities per set of een aanvullende afhandeling.

Houd bewaarde afbeeldingen actueel

Vertalingen behoren bij adresruimtes. Bij een contextwisseling kunnen oude items worden verwijderd of met adresruimte-identificatoren, of ASID's, worden onderscheiden. Wijzigingen in afbeeldingen vereisen overeenkomstig onderhoud van de vertaalcache; RISC-V biedt sfence.vma. Als een pagina uit het geheugen wordt verdrongen, mag de oude vertaling ervan niet bruikbaar blijven in de TLB. De TLB bevat afbeeldingen en toegangsrechten, terwijl gewone caches de gegevens en instructies van het programma bevatten.

Code die rekening houdt met de cache gebruikt opgehaalde bytes voordat hun blok wordt verdrongen. Begin met de adressen die de binnenste lus genereert. Vraag vervolgens welke gegevens opnieuw worden gebruikt, hoe ver toegangen uit elkaar liggen en of die blokken samen in de cache kunnen worden bewaard.

Doorloop arrays in opslagvolgorde

C en C++ slaan rechthoekige arrays op in rijgewijze opslagvolgorde. Aangrenzende kolommen van één rij liggen naast elkaar in het geheugen. Fortran, MATLAB en Julia gebruiken kolomgewijze opslagvolgorde; NumPy-arrays gebruiken standaard rijgewijze opslagvolgorde. Een efficiënte binnenste doorloop volgt de werkelijke indeling.

Een C-array double a[1024][1024] neemt 8 MiB in. Elke rij beslaat 8192 bytes. Bij cachelijnen van 64 bytes bevat elke lijn acht doubles. Een rijdoorloop kan alle acht gebruiken voordat die verdergaat, wat in een eenvoudig model met ophalen op verzoek ongeveer één eerste-toegangsmisser per acht toegangen geeft.

Een kolomdoorloop maakt stappen van 8192 bytes tussen opeenvolgende toegangen. Die raakt 1024 verschillende lijnen voordat nabijgelegen gegevens in de volgende kolom opnieuw worden gebruikt. Die lijnen nemen 64 KiB in en overschrijden daarmee een L1-cache van 32 KiB. Ze conflicteren ook: in een cache met 64 sets behoudt een stapgrootte van 128 lijnen de setindex. Een 8-weg set kan geen 1024 concurrerende lijnen bevatten.

Als je een rij opvult tot 1032 doubles, wordt de stapgrootte 8256 bytes, of 129 lijnen. Opeenvolgende rijen gaan dan telkens één set verder modulo 64, waardoor de verzoeken worden gespreid. Opvulling pakt afbeeldingsconflicten aan; de hoeveelheid gegevens blijft van belang.

Verwissel lussen als het resultaat behouden blijft

Verwisseling van lusvolgorde verandert welke lus binnen een andere loopt. Bij rijgewijze matrixvermenigvuldiging doorloopt de volgorde i, j, k een rij van A, maar een kolom van B. In een model met grote gegevensstromen en weinig hergebruik tussen doorgangen kost dit ongeveer $1\mathrm{/}8+1=\mathrm{1,125}$ missers per binnenste iteratie.

Bij i, k, j doorloopt de binnenste lus rijen van B en C, terwijl één element van A opnieuw wordt gebruikt. Als je voor beide rijen een nieuwe stroom telt, geeft dat ongeveer $1\mathrm{/}8+1\mathrm{/}8=\mathrm{0,25}$ missers per iteratie, 4,5 keer minder. Als de herhaaldelijk bijgewerkte rij van C aanwezig blijft, nadert het aantal 0,125. Cachecapaciteit en conflicten bepalen welk hergebruik behouden blijft.

Verwisseling moet het vereiste gedrag van de berekening behouden. Afhankelijkheden, overlappende pointers en de evaluatievolgorde van drijvendekommabewerkingen kunnen aanpassingen beperken; compilers hebben bewijs nodig dat een wijziging is toegestaan.

Haal de velden op die je gebruikt

Een array van structuren groepeert alle velden van één object. Een structuur van arrays groepeert één veld over objecten heen. Als een deeltjesrecord acht doubles in één lijn van 64 bytes bevat, haalt het optellen van alleen x over één miljoen uitgelijnde records ongeveer 64 MB op. Een afzonderlijke aaneengesloten array x haalt ongeveer 8 MB op en gebruikt elke binnengehaalde double. Code die alle deeltjesvelden samen gebruikt, kan baat hebben bij de oorspronkelijke structuurindeling.

Gekoppelde knooppunten kunnen verspreid liggen en elk volgend adres kan afhangen van een zojuist geladen pointer. Aaneengesloten arrays of pools van knooppunten kunnen de lokaliteit verbeteren. Compacte veelgebruikte velden laten ook meer actieve gegevens binnen elk niveau passen.

Meet de uitvoeringstijd en relevante prestatietellers in de hardware vóór en na een wijziging. Cachemissers kunnen een langzame lus verklaren, maar berekeningen, bandbreedte of sprongen kunnen de beperkende factor zijn. Houd de invoer en resultaten vergelijkbaar zodat een snelheidsverschil de beoordeelde wijziging weerspiegelt.

Verwisseling van lusvolgorde verbetert de toegangsvolgorde. Blokgewijze verwerking, ook wel verwerking in rekenblokken genoemd, gaat verder door een klein gebied met gegevens actief te houden totdat het nuttige hergebruik is voltooid. Vooraf ophalen verplaatst een toekomstige overdracht naar een eerder moment, zodat de vertraging overlapt met nuttig werk.

Houd een groep rekenblokken aanwezig

Bij blokgewijze vermenigvuldiging van vierkante matrices dragen één blok van A en één blok van B bij aan één blok van C. Een blok met zijde $b$ bevat $b^2$ elementen. Door herhaaldelijk op deze kleine blokken te werken, worden gegevens opnieuw gebruikt voordat de verwerking naar het volgende gebied gaat.

Voor doubles van 8 bytes vereisen drie blokken $3b^2\times 8=24b^2$ bytes. In een cache van 32 KiB is de capaciteitsgrens

Een zijde van 32 gebruikt 24.576 bytes, of 24 KiB, en laat enige ruimte over voor andere gegevens. Als je 36 kiest alleen omdat de berekening dat toestaat, blijft veel minder ruimte over en kunnen conflicten optreden. Capaciteit is een eerste schatting; werkelijke blokgroottes worden op basis van metingen afgestemd.

Een blokgewijze doorloop laat de buitenste lus stappen maken ter grootte van het blok. De bovengrenzen van de binnenste lussen stoppen bij de kleinste waarde van het blokeinde en de matrixgrootte. Als een dimensie bijvoorbeeld 70 is en blokken een zijde van 32 hebben, bevat het laatste blok slechts zes elementen langs die dimensie. Een laatste blok van volledige grootte zou buiten de array toegang zoeken.

Schat wat hergebruik bespaart

In een vereenvoudigd model met grote matrices en lijnen van 64 bytes heeft de eenvoudige volgorde i, j, k ongeveer $\mathrm{1,125}{N}^3$ missers wanneer doorlopen rijen bij de volgende doorgang niet meer in de cache staan. Een blokgewijze versie kan dit verminderen tot ongeveer $N^3\mathrm{/}(4b)$, aangenomen dat de drie gebruikte blokken in de cache blijven en zonder rekening te houden met conflicten.

Voor $N=1024$ en $b=32$ zijn deze schattingen ongeveer 1,2 miljard en 8,4 miljoen missers, een factor 144. Beide versies voeren nog steeds ongeveer $2N^3$ drijvendekommabewerkingen uit. De besparing zit in herhaalde gegevensverplaatsing, niet in het aantal rekenbewerkingen van de vermenigvuldiging. Het model beschrijft ideaal hergebruik; de gemeten versnellingsfactor hangt ook af van bandbreedte, uitvoering en andere overhead.

Haal vroeg genoeg vooraf op om latentie te verbergen

Hardware die vooraf ophaalt, herkent stromen zoals opeenvolgende toegangen of toegangen met constante stapgrootte. Die vraagt lijnen op voordat ze nodig zijn voor een toegang. Ook software kan vragen om gegevens vooraf op te halen, bijvoorbeeld met __builtin_prefetch van GCC of Clang.

Het tijdstip is van belang. Een verzoek dat te laat wordt gedaan, laat de gevraagde toegang wachten. Een verzoek dat te vroeg wordt gedaan, kan een lijn binnenhalen die vóór gebruik weer wordt verdrongen. Een onnauwkeurig verzoek verbruikt bandbreedte en cacheruimte zonder het programma te helpen. Bij het volgen van pointers is vooraf ophalen moeilijker omdat het volgende adres vaak pas bekend wordt nadat het huidige knooppunt aankomt.

Tijdig vooraf ophalen kan latere missers bij opvragen omzetten in treffers, maar de lijnen reizen nog steeds door de hiërarchie. Het verbergt latentie zonder de vereiste hoeveelheid gegevens voor een opeenvolgende doorloop te verminderen. Blokgewijze verwerking helpt wanneer waarden opnieuw worden gebruikt; een eenmalige doorloop heeft geen herhaalde gegevens om te bewaren en kan al door de geheugenbandbreedte worden begrensd.