Speicherhierarchie und Caches

Ein Cache funktioniert, weil der nächste Speicherzugriff oft mit einem kürzlich erfolgten Zugriff zusammenhängt. Während eines kurzen Zeitabschnitts nutzen die meisten Programme nur einen kleinen Teil ihres Adressraums. Dieses Muster heißt Lokalität. Ein Cache hält diesen aktiven Teil nahe am Prozessor, wo er Zugriffe schnell bedienen kann.

Wiederverwendung in Zeit und Raum

Zeitliche Lokalität bedeutet, ein Element kurz nach dem Zugriff erneut zu verwenden. Eine Schleife holt die Befehle ihres Körpers wiederholt. Eine laufende Summe wird vielfach gelesen und aktualisiert. Bleiben diese Elemente verfügbar, müssen sie nicht erneut aus einer langsameren Ebene geholt werden.

Räumliche Lokalität bedeutet, auf Elemente an benachbarten Adressen zuzugreifen. Beim Durchlaufen eines Arrays werden benachbarte Elemente gelesen, und Code ohne Verzweigungen holt aufeinanderfolgende Befehle. Ein Cache nutzt dies, indem er bei einem Fehlzugriff einen ganzen Block, auch Cachezeile genannt, holt. Benachbarte Bytes treffen ein, bevor das Programm sie anfordert.

Diese Muster können gemeinsam auftreten. Die Befehle einer Schleife liegen nebeneinander und werden wiederholt ausgeführt, sodass der Befehlsstrom sowohl räumliche als auch zeitliche Lokalität aufweist. Ein genau einmal gelesenes Arrayelement wird zeitlich nicht wiederverwendet, obwohl das Durchlaufen des umgebenden Arrays räumliche Lokalität aufweist.

Blöcke beim Durchlaufen eines Arrays zählen

Betrachte diese C-Schleife mit 4 Byte großen Ganzzahlen und 64 Byte großen Cacheblöcken:

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

Ein Block fasst $64\mathrm{/}4=16$ Ganzzahlen. Das Array belegt $1000\times 4=4000$ Byte. Ist sein erstes Element an einer Blockgrenze ausgerichtet, berührt der Durchlauf $\lceil 4000\mathrm{/}64\rceil =63$ Blöcke: 62 volle Blöcke und einen teilweise gefüllten Block.

In einem zunächst leeren Cache ohne Prefetching oder störende Zugriffe schlägt der erste Zugriff auf jeden Block fehl. Die übrigen Elemente in diesem Block treffen. Das Array verursacht somit 63 Fehlzugriffe bei 1000 Zugriffen, also etwa 6,3 %. Würde man einen Fehlzugriff pro Element zählen, übersähe man alle nützlichen benachbarten Daten, die bei jedem Fehlzugriff mitgeladen werden.

Die Quellcodevariablen sum und i werden häufig wiederverwendet. Ein Compiler hält sie jedoch normalerweise in Registern, sodass ihre Wiederverwendung auf Quellcodeebene keine Datencachezugriffe erzeugen muss. Analysiere die Speicherzugriffe, die das kompilierte Programm ausführt, wenn du den Cacheverkehr abschätzt.

Die Arbeitsmenge muss passen und gemeinsam Platz finden

Die Arbeitsmenge ist die Sammlung der Blöcke, die während eines gewählten Zeitfensters verwendet werden. Passen sie in den Cache und erlauben die Platzierungsregeln, dass sie gemeinsam dort liegen, treffen wiederholte Zugriffe nach dem ersten Laden überwiegend. Das Zeitfenster ist entscheidend: Ein ganzes Programm kann riesig sein, während eine aktive Schleife nur wenige Blöcke nutzt.

Die Kapazität allein reicht nicht aus. Zwei häufig genutzte Blöcke können auf einen direkt abgebildeten Eintrag abgebildet werden und sich gegenseitig verdrängen, während andere Einträge leer bleiben. Eine Arbeitsmenge kann daher ihrer Bytezahl nach passen und dennoch nicht im Cache bleiben.

Verstreute Knoten einer verketteten Liste und zufällige Zugriffe auf eine große Hashtabelle weisen oft geringe räumliche Lokalität auf. Auch das spaltenweise Durchlaufen eines zeilenweise gespeicherten Arrays überspringt viele benachbarte Elemente. Diese Muster laden Bytes, die vor ihrer Verdrängung möglicherweise ungenutzt bleiben. Die Hardware nutzt die durch das Zugriffsmuster vorgegebene Lokalität; durch eine Änderung des Datenlayouts oder der Reihenfolge des Durchlaufens kann ein größerer Teil jedes geholten Blocks nützlich werden.

Bei Speichertechnologien stehen Geschwindigkeit, Dichte, Kosten und dauerhafte Speicherung in einem Zielkonflikt. Der Prozessor braucht schnellen Zugriff auf eine kleine Datenmenge und bezahlbaren Platz für sehr viel mehr. SRAM, DRAM und Flash erfüllen unterschiedliche Teile dieses Bedarfs.

Die Zellen vergleichen

Eine SRAM-Zelle ist schnell, belegt aber viel Fläche, wodurch SRAM pro Bit relativ teuer ist. DRAM-Zellen sind kleiner, sodass DRAM mehr Kapazität zu geringeren Kosten pro Bit bietet. Ihre Ladung entweicht. Bei der Auffrischung werden Zeilen innerhalb eines festen Zeitfensters gelesen und wiederhergestellt; DDR4 verwendet bei normalen Temperaturen ein Zeitfenster von 64 ms. „Statisch“ in SRAM bedeutet, dass keine Auffrischung nötig ist, nicht aber, dass die Daten nach einem Stromausfall erhalten bleiben.

Warum die DRAM-Zugriffszeit variiert

DRAM ist in Bänke mit jeweils Zeilen und Spalten unterteilt. Beim Aktivieren einer Zeile wird sie in einen Zeilenpuffer kopiert. Lese- und Schreibzugriffe wählen dann Spalten aus dieser geöffneten Zeile. Um eine andere Zeile derselben Bank zu öffnen, muss die Bank zuerst vorgeladen werden. Ein Zugriff auf eine bereits geöffnete Zeile vermeidet diesen Aufwand für den Zeilenwechsel.

Aufeinanderfolgende Spalten können in einem Burst übertragen werden, was sich zum Holen eines Cacheblocks eignet. Die Verteilung von Anforderungen auf Bänke und Kanäle ermöglicht überlappende Übertragungen. DDR-Speicher überträgt an beiden Taktflanken. Diese Eigenschaften erhöhen die Datenübertragungsrate, ohne die Wartezeit auf die ersten Daten zu beseitigen.

Latenz und Bandbreite unterscheiden

Latenz ist die Verzögerung bis zum Eintreffen der ersten Daten. Bandbreite ist die pro Zeiteinheit übertragene Datenmenge. Eine Schnittstelle mit hoher Bandbreite kann dennoch eine lange anfängliche Verzögerung haben.

Ein DDR5-4800-Kanal mit einem insgesamt 64 Bit breiten Datenpfad überträgt beispielsweise 8 Byte pro Übertragung. Seine Spitzenleistung beträgt $4800\times {10}^6\times 8=\mathrm{38,4}\times {10}^9$ Byte/s oder 38,4 GB/s. Die dauerhaft von Anwendungen erreichte Bandbreite kann geringer sein, weil Befehle, Zeilenwechsel und andere Arbeiten Zeit beanspruchen.

Wartet eine Anforderung 60 ns und empfängt dann einen 64 Byte großen Block mit 16 GB/s, beträgt die Übertragungsrate 16 Byte/ns. Die Übertragung dauert $64\mathrm{/}16=4$ ns, insgesamt also etwa 64 ns. Eine Verbesserung allein der Bandbreite verringert den Anteil von 4 ns, nicht die anfänglichen 60 ns.

Flash behält Daten, behandelt Schreibzugriffe aber anders

NAND-Flash liest und programmiert Seiten von mehreren KiB. Um eine programmierte Seite erneut zu verwenden, muss ihr größerer Löschblock gelöscht werden, der viele Seiten enthält. Das Lesen einer Seite dauert typischerweise einige zehn Mikrosekunden, das Programmieren einige hundert Mikrosekunden bis wenige Millisekunden und das Löschen Millisekunden.

Programmier- und Löschzyklen verschleißen die Zellen. Dichtes Mehrbit-Flash unterstützt oft einige Tausend Zyklen, während Einbitzellen etwa 100.000 unterstützen können. Controller verwenden Wear-Leveling, um Schreibzugriffe über die Blöcke zu verteilen.

Zur Einordnung: Ein SRAM-Zugriff dauert ungefähr 1 ns, ein DRAM-Zugriff ungefähr 50–100 ns, ein NAND-Lesezugriff ungefähr 25–100 µs und ein Festplattenzugriff ungefähr 5–10 ms. Tatsächliche Geräte unterscheiden sich. Die Hierarchie kombiniert diese Technologien, weil eine einzelne ihre Vorteile bei Geschwindigkeit, Kapazität und Preis nicht zugleich bieten kann.

Die Speicherhierarchie platziert kleinen, schnellen Speicher nahe am Prozessor und zunehmend größeren Speicher weiter entfernt. Lokalität ermöglicht es den kleinen Ebenen, einen großen Anteil der Anforderungen zu bedienen, während die unteren Ebenen Kapazität bereitstellen.

Ebenen und Übertragungseinheiten

Ein typischer Weg führt über Register, L1, L2, L3, Hauptspeicher und Massenspeicher. L1 hat üblicherweise getrennte Befehls- und Datencaches von jeweils etwa 32–64 KiB pro Kern. L2 umfasst oft einige hundert KiB bis wenige MiB pro Kern, während L3 häufig gemeinsam genutzt wird und mehrere bis einige zehn MiB fasst. Der Hauptspeicher fasst viele GiB, der Massenspeicher mehrere hundert GB oder mehr. Entwürfe unterscheiden sich in Größe und gemeinsamer Nutzung.

Bei einem Prozessor mit etwa 3 GHz betragen typische Ladelatenzen für L1 etwa 4–5 Taktzyklen, für L2 12–15, für L3 30–50 und für DRAM 200–300. Ein L1-Cache kann in jedem Taktzyklus eine neue Anforderung annehmen, selbst wenn eine Anforderung mehrere Taktzyklen bis zum Abschluss benötigt: Durchsatz und Latenz beschreiben unterschiedliche Eigenschaften.

Daten werden durch Caches in Blöcken übertragen, die häufig 64 Byte groß sind. Virtueller Speicher verwendet Seiten, häufig 4 KiB groß, wenn Seiteninhalte zwischen Haupt- und Massenspeicher übertragen werden. Eine Cachezeile und eine Seite dienen auf unterschiedlichen Größenskalen ähnlichen Gruppierungszwecken; sie sind nicht dieselbe Übertragungseinheit.

Treffer, Fehlzugriffe und Zeitbedarf

Ein Treffer bedeutet, dass eine Ebene die angeforderten Daten enthält. Ein Fehlzugriff bedeutet, dass sie die Daten von einer unteren Ebene holen muss. Beide Begriffe beziehen sich auf die geprüfte Ebene: Auf einen L1-Fehlzugriff kann dennoch ein L2-Treffer folgen.

Die Trefferrate ist die Anzahl der Treffer geteilt durch die Anzahl der Zugriffe, und die Fehlzugriffsrate ist eins minus Trefferrate. Die Trefferzeit umfasst die Prüfung der Ebene und die Entscheidung, ob die Anforderung trifft. Die Fehlzugriffsverzögerung ist die zusätzliche Zeit, die bei einem Fehlzugriff benötigt wird, um den Block zu holen und bereitzustellen.

Angenommen, ein vereinfachter Cache hat eine Trefferzeit von 1 Taktzyklus, eine Trefferrate von 97 % und eine zusätzliche Fehlzugriffsverzögerung von 100 Taktzyklen. Bei jedem Zugriff fällt 1 Taktzyklus an, bei 3 % kommen weitere 100 hinzu:

Ein Fehlzugriff dauert in diesem Beispiel 101 Taktzyklen. Würde man 100 als gesamte Fehlzugriffszeit verwenden, würde die Trefferprüfung nicht einheitlich berechnet. Selbst bei einer hohen Trefferrate machen sich teure Fehlzugriffe im Mittel bemerkbar.

Wer verwaltet die einzelnen Ebenen?

Der Compiler weist geeignete Werte Registern zu. Die Cachehardware verschiebt Blöcke automatisch, während Lade- und Speicherbefehle sowie das Holen von Befehlen ausgeführt werden. Programme nennen Adressen; sie wählen keine Cacheeinträge aus. Das Betriebssystem verwaltet mit Hardwareunterstützung die Abbildungen des virtuellen Speichers und behandelt Seiten, die in den Hauptspeicher gebracht werden müssen.

Die Trennung von Befehlen und Daten in L1 ermöglicht es einer Pipeline, einen Befehl zu holen und gleichzeitig auf Daten zuzugreifen, ohne um denselben Cacheport zu konkurrieren. Untere Caches sind meist vereinheitlicht und speichern sowohl Befehls- als auch Datenblöcke.

Manche Hierarchien sind inklusiv: Von einem oben vorhandenen Block gibt es auch unten eine Kopie. Andere sind exklusiv oder nichtinklusiv, sodass eine Kopie in jedem unteren Cache nicht garantiert ist. Zeichne eine Hierarchie als Such- und Übertragungsweg, nicht als Zusicherung, dass alle Ebenen identische Teilmengen enthalten.

Ein größerer L1-Cache kann Fehlzugriffe verringern, aber Zugriffsverzögerung und Energiebedarf erhöhen. Größere untere Caches ermöglichen es, L1 schnell zu halten und zugleich viele seiner Fehlzugriffe vor dem DRAM abzufangen. Beurteile diesen Zielkonflikt anhand der Zugriffszeit, nicht allein anhand der Kapazität.

Eine Byteadresse bezeichnet ein Byte im Speicher. Ein Cache holt einen ganzen Block, daher wird bei der Suche zuerst dieser Block bestimmt und anschließend werden die angeforderten Bytes darin ausgewählt. In einem direkt abgebildeten Cache hat jeder Block genau einen möglichen Eintrag.

Die Adresse nach Zweck aufteilen

Bei einer Blockgröße von $2^b$ Byte bilden die niederwertigen $b$ Adressbits den Offset. Teilt man die Byteadresse durch die Blockgröße und verwirft den Rest, erhält man die Blockadresse. Der Rest ist der Offset.

Hat der Cache $E$ Einträge, ist der Index des Eintrags

Ist die Anzahl der Einträge eine Zweierpotenz, besteht der Index aus der Gruppe von Adressbits unmittelbar oberhalb des Offsets. Die verbleibenden hohen Bits bilden das Tag, das dem Cache angibt, welcher der vielen Blöcke mit demselben Index vorhanden ist.

Die Reihenfolge der Felder von den höchst- zu den niederwertigen Bits ist Tag | Index | Offset. Bei einer Adressbreite von $A$ Bits gilt:

Verwende für die Indexberechnung die Anzahl der Einträge. Würdest du den Logarithmus der Kapazität in Byte bilden, würdest du die Offset-Bits ein zweites Mal zählen.

Ein Beispiel mit 16 KiB durchrechnen

Ein direkt abgebildeter Cache mit 16 KiB und 64 Byte großen Blöcken hat $16384\mathrm{/}64=256$ Einträge. Bei 32-Bit-Adressen belegt der Offset 6 Bit, der Index 8 Bit und das Tag $32-8-6=18$ Bit.

Für die Byteadresse 0x1234ABCD ergeben die niederwertigen 6 Bits den Offset 13 oder 0x0D. Entfernt man diese Bits, erhält man die Blockadresse 0x48D2AF. Ihre niederwertigen 8 Bits sind 0xAF, der Index ist also 175. Die verbleibenden Bits ergeben das Tag 0x48D2.

Die Byteadresse lässt sich aus diesen Feldern rekonstruieren: Hänge das Tag, den 8-Bit-Index und den 6-Bit-Offset aneinander. Die Feldbreiten sind wichtig, weil eine Hexadezimalziffer 4 Bit darstellt; die Grenzen müssen nicht zwischen Hexadezimalziffern liegen.

Ein passendes Tag braucht einen gültigen Eintrag

Jeder Eintrag speichert Daten, ein Tag und ein Gültigkeitsbit. Der Index wählt den Eintrag aus. Ein Treffer erfordert sowohl ein gesetztes Gültigkeitsbit als auch die Übereinstimmung des gespeicherten Tags mit dem angeforderten Tag. Beim Start kann ein Eintrag beliebige Bits enthalten; das Gültigkeitsbit verhindert, dass diese Bits für einen geladenen Block gehalten werden.

Sobald der Block vorhanden ist, treffen auch Zugriffe auf andere Bytes in diesem Block. Ein Treffer erfordert nicht dieselbe Byteadresse, mit der der Block geholt wurde.

Metadaten getrennt zählen

Die angegebene Cachekapazität zählt normalerweise nur Daten. Hier enthält jeder Eintrag 512 Datenbits, 18 Tag-Bits und 1 Gültigkeitsbit, also 531 Bits. Der gesamte Speicherbedarf beträgt

Die Daten allein benötigen 131072 Bits. Tags und Gültigkeitsbits fügen 4864 Bits hinzu, etwa 3,7 % des Datenspeichers. Ein Entwurf mit Rückschreibverfahren benötigt außerdem Änderungsbits; komplexere Entwürfe benötigen weitere Steuerzustände.

Der Index verwendet niederwertige Blockadressbits, sodass aufeinanderfolgende Blöcke auf aufeinanderfolgende Einträge verteilt werden. Eine breitere Adresse lässt die Breite von Offset und Index unverändert, wenn Kapazität und Blockgröße gleich bleiben; die zusätzlichen Bits verlängern das Tag.

Ein Cache-Zugriffsprotokoll hält fest, wie jeder Zugriff die gespeicherten Blöcke verändert. Führe für jeden Eintrag einen eigenen Zustand und aktualisiere ihn unmittelbar nach jedem Fehlzugriff. Die nächste Anforderung verwendet den aktualisierten Cache und nicht den Cache im Anfangszustand.

Das Zugriffsprotokoll vorbereiten

Nimm einen direkt abgebildeten Cache mit 64 Byte und vier Einträgen zu je 16 Byte. Er ist anfangs leer. Teile für jede Byteadresse durch 16, um den Block zu finden, und berechne dann Block modulo 4 für den Index. Das Tag ist die durch 4 geteilte Blocknummer, wobei der Nachkommateil verworfen wird. Es gibt 4 Offset-Bits und 2 Index-Bits.

Prüfe bei einem Lesezugriff den ausgewählten Eintrag. Ist er gültig und stimmt das Tag überein, notiere einen Treffer. Andernfalls notiere einen Fehlzugriff, ersetze den Block und das Tag dieses Eintrags und setze sein Gültigkeitsbit. In einem direkt abgebildeten Cache gibt es keine Wahl bei der Ersetzung.

Alle acht Zugriffe verfolgen

Der erste Zugriff füllt Eintrag 0 mit Block 0. Die nächste Adresse, 0x04, liegt noch innerhalb dieses 16-Byte-Blocks und trifft daher, obwohl sie ein anderes Byte bezeichnet. 0x40 gehört zu Block 4. Er hat denselben Index wie Block 0, aber ein anderes Tag und ersetzt daher Block 0.

Das zweite 0x00 schlägt daher fehl. Die frühere Verwendung allein garantiert keinen Treffer: Der Block muss noch vorhanden sein. Die Anforderung an 0x14 lädt Block 1 in Eintrag 1 und lässt Eintrag 0 unverändert.

Anschließend lädt 0x44 Block 4 erneut in Eintrag 0. 0x08 benötigt Block 0 und verdrängt Block 4. Schließlich lädt 0x84 Block 8 in denselben Eintrag. Am Ende enthält Eintrag 0 Block 8 und Eintrag 1 enthält Block 1; die Einträge 2 und 3 bleiben ungültig.

Das Verhalten deuten

Es gibt einen Treffer und sieben Fehlzugriffe, die Trefferrate beträgt also $1\mathrm{/}8=\mathrm{12,5}\mathrm{\%}$. Die Blöcke 0, 4 und 8 konkurrieren um Eintrag 0. Der Cache hat vier Einträge, doch dieses Zugriffsmuster nutzt nur zwei davon. Die wiederholten Verdrängungen entstehen durch Abbildungskonflikte, nicht durch einen Mangel an Gesamtspeicher für die vier verschiedenen Blöcke.

Das Laden eines Blocks macht alle Bytes dieses Blocks verfügbar. Bei einem sequenziellen Durchlauf kann ein Fehlzugriff daher viele folgende Elemente bedienen. Hier beseitigen die konkurrierenden Zugriffe diesen Vorteil wiederholt, bevor das nächste benachbarte Byte angefordert wird.

Für ein zuverlässiges Zugriffsprotokoll benenne Byteadressen und Blocknummern ausdrücklich. Wendet man Modulo 4 direkt auf die Byteadresse an, überspringt man die Division durch die Blockgröße und leitet Anforderungen an die falschen Einträge. Halte die Ersetzung auch dann fest, wenn der neue Block zuvor schon geladen wurde: Jeder Fehlzugriff lädt den angeforderten Block und sein Tag in den ausgewählten Eintrag.

Ein satzassoziativer Cache bietet einem Block mehrere mögliche Einträge, ohne den gesamten Cache zu durchsuchen. Der Index wählt einen Satz aus, und der Block kann jeden Weg in diesem Satz belegen. Das verringert Konflikte zwischen Blöcken mit demselben Index.

Sätze und Felder berechnen

Für die Datenkapazität $C$, die Blockgröße $B$ und die Assoziativität $n$ gilt:

Der Satzindex ist die Blockadresse modulo Anzahl der Sätze. Der Offset hängt weiterhin nur von der Blockgröße ab. Das Tag enthält die verbleibenden hohen Bits.

Ein 8-fach assoziativer Cache mit 32 KiB und 64 Byte großen Blöcken hat 512 Blöcke und 64 Sätze. Bei 32-Bit-Adressen sind Offset, Index und Tag 6, 6 und 20 Bit breit. Die Adresse 0x1234ABCD hat den Offset 13, den Satz 47 und das Tag 0x1234A.

Bei fester Kapazität und Blockgröße halbiert eine Verdopplung der Assoziativität die Anzahl der Sätze. Ein Index-Bit wird zu einem Tag-Bit; die Datenkapazität wächst nicht.

Bei der Suche wird das Tag parallel mit allen gültigen Tags im gewählten Satz verglichen. Ein Weg mit passendem Tag liefert die Daten über einen Multiplexer. Mehr Wege benötigen mehr Vergleiche und Auswahlhardware, was Trefferzeit und Energiebedarf erhöhen kann.

Einen Block erst ersetzen, wenn der Satz voll ist

Verwende zuerst einen ungültigen Weg. Sind alle Wege belegt, verdrängt LRU den Block, dessen letzter Zugriff am längsten zurückliegt. Aktualisiere die Information über die letzte Nutzung sowohl bei Treffern als auch beim Laden. Ein 2-fach assoziativer Satz benötigt nur ein Bit, um seinen LRU-Weg festzuhalten; größere Sätze verwenden oft Pseudo-LRU-Näherungen.

FIFO verdrängt den zuerst geladenen Block, selbst wenn kürzlich darauf zugegriffen wurde. Die zufällige Ersetzung wählt einen zu verdrängenden Block, ohne die vollständige Nutzungsreihenfolge zu speichern. Sie ist einfach und kann in großen Caches eine ähnliche Leistung wie LRU erreichen.

Das kleine Zugriffsprotokoll mit zwei Wegen erneut betrachten

Der Cache mit 64 Byte und 16 Byte großen Blöcken hat nun zwei Sätze mit je zwei Wegen. Die Blöcke 0, 4 und 8 werden auf Satz 0 abgebildet, Block 1 auf Satz 1. Für 0x00, 0x04, 0x40, 0x00, 0x14, 0x44, 0x08, 0x84 lauten die Ergebnisse: Fehlzugriff, Treffer, Fehlzugriff, Treffer, Fehlzugriff, Treffer, Treffer, Fehlzugriff.

Die Blöcke 0 und 4 können gleichzeitig im Cache liegen, sodass die wiederholten Zugriffe auf sie treffen. Unmittelbar vor dem letzten Zugriff wurde Block 0 vor kürzerer Zeit verwendet als Block 4. Das Laden von Block 8 verdrängt bei LRU den Block 4. Vier von acht Zugriffen treffen, gegenüber einem bei der direkt abgebildeten Variante.

Assoziativität kann weder obligatorische Fehlzugriffe beseitigen noch eine Arbeitsmenge in den Cache passen lassen, die größer als seine Kapazität ist. Sie kann auch keine Konflikte verhindern, wenn mehr als n häufig genutzte Blöcke um einen n-fach assoziativen Satz konkurrieren. Ein wiederholter Zyklus aus n+1 solchen Blöcken kann dazu führen, dass LRU jedes Mal einen Fehlzugriff verzeichnet. Padding von Arrays kann ihre Satzzuordnung verändern; mehr Wege sind nur eine mögliche Reaktion auf ein Konfliktproblem.

Ein Cache-Fehlzugriff ist ein Ereignis mit einem Ablauf und einer Ursache. Der Ablauf beschreibt, wie die Anforderung bedient wird. Die Ursache erklärt, warum der benötigte Block fehlte und welche Entwurfsänderung helfen könnte.

Einen Lesefehlzugriff behandeln

In einer einfachen Pipeline mit Ausführung in Befehlsreihenfolge erkennt der Cache einen ungültigen Eintrag oder ein nicht übereinstimmendes Tag, und der Prozessor hält an. Der Cache fordert den Block von der nächsten Ebene an. Ist der zur Verdrängung ausgewählte Block verändert, müssen seine geänderten Daten durch Zurückschreiben erhalten werden. Der eintreffende Block wird zusammen mit seinem Tag und Gültigkeitsbit eingetragen, und der wartende Zugriff wird abgeschlossen. Ebenso wartet ein Fehlzugriff im Befehlscache auf den Block des Befehls und holt den Befehl anschließend erneut.

Critical Word First fordert das benötigte Wort im zurückkehrenden Block zuerst an. Der frühzeitige Neustart ermöglicht die Fortsetzung der Ausführung, sobald dieses Wort eintrifft. Ein nichtblockierender Cache kann andere Treffer bedienen und ausstehende Fehlzugriffe verfolgen, während ein Prozessor mit Ausführung außerhalb der Befehlsreihenfolge unabhängige Arbeit erledigt. Diese Mechanismen verringern die Wartezeit; sie beseitigen die ursprüngliche Datenabhängigkeit nicht.

Die drei C verwenden

Prüfe zuerst, ob es sich um den ersten Zugriff handelt. Der erste Zugriff auf einen Block ist obligatorisch, auch wenn sein Zieleintrag bereits belegt ist. Vergleiche bei späteren Fehlzugriffen den tatsächlichen Cache mit einem vollassoziativen LRU-Cache gleicher Datenkapazität und Blockgröße, wobei beide dieselbe Zugriffsfolge erhalten.

Im früheren Zugriffsprotokoll mit vier Einträgen verursachen die Blöcke 0, 4, 1 und 8 jeweils einen obligatorischen Fehlzugriff. Der direkt abgebildete Cache verzeichnet auch bei den wiederholten Zugriffen auf die Blöcke 0 und 4 Fehlzugriffe. Ein vollassoziativer Cache mit vier Einträgen kann alle vier verschiedenen Blöcke halten, sodass diese drei erneuten Fehlzugriffe konfliktbedingt sind. Kapazitätsbedingte Fehlzugriffe gibt es nicht.

Eine Änderung wählen, die die Ursache angeht

Eine größere Kapazität kann eine größere Arbeitsmenge halten. Eine höhere Assoziativität kann ermöglichen, dass konkurrierende Blöcke gemeinsam im Cache liegen. Eine größere Blockgröße kann räumliche Lokalität nutzen, indem bei jedem Laden mehr nützliche benachbarte Daten mitgebracht werden.

Die Blockgröße hat gegenläufige Auswirkungen. Bei fester Datenkapazität bedeuten größere Blöcke weniger gleichzeitig gespeicherte Blöcke. Ungenutzte Bytes belegen Cacheplatz, andere nützliche Blöcke können verdrängt werden und jede Übertragung kann länger dauern. Die Fehlzugriffsrate fällt bei wachsender Blockgröße häufig zunächst und steigt dann, wenn diese Kosten den Nutzen räumlicher Lokalität überwiegen.

Ein größerer Cache kann auch eine längere Suchzeit haben, und zusätzliche Wege benötigen mehr Vergleichshardware. Beurteile Änderungen anhand der mittleren Zugriffszeit einschließlich Trefferzeit und Fehlzugriffsverzögerung, statt anzunehmen, dass eine niedrigere Fehlzugriffsrate einen schnelleren Entwurf garantiert.

In Mehrkernsystemen kann die Invalidierung nach einem Schreibzugriff eines anderen Kerns kohärenzbedingte Fehlzugriffe verursachen. Prefetching kann einen erstmals benötigten Block vor dem anfordernden Zugriff laden und so einen Fehlzugriff verbergen, den zusätzliche Kapazität allein nicht vermeiden kann.

Ein Speicherbefehl verändert einen Wert, daher braucht die Hierarchie eine Regel, um diese Änderung nach unten weiterzugeben. Dabei sind zwei Entscheidungen getrennt zu treffen: Was geschieht bei einem Treffer des Speicherbefehls und was bei einem Fehlzugriff?

Durchschreib- und Rückschreibverfahren

Ein Änderungsbit hält fest, dass ein Block beim Rückschreibverfahren Änderungen enthält, die noch nicht in die nächste Ebene geschrieben wurden. Ein unveränderter zu verdrängender Block muss nicht zurückgeschrieben werden. Bei einem veränderten müssen die geänderten Daten erhalten werden, bevor sein Eintrag wiederverwendet werden kann. Die Ladebefehle des Prozessors erhalten den neuen Wert aus dem Cache, auch wenn die untere Kopie noch älter ist.

Bei 100 Speicherbefehlen auf eine zwischengespeicherte 4 Byte große Variable sendet das Durchschreibverfahren ohne Zusammenfassung 100 Schreibzugriffe oder 400 Byte Nutzdaten. Das Rückschreibverfahren kann diese Änderungen bei der Verdrängung zu einem Schreibzugriff auf einen 64 Byte großen Block zusammenfassen. Dieser Vergleich zählt die Nutzdaten der Aktualisierung und lässt das anfängliche Laden und den Protokollaufwand aus.

Der Nutzen hängt von der Wiederverwendung ab. Wiederholte Schreibzugriffe auf einen Block geben dem Rückschreibverfahren die Möglichkeit, Aktualisierungen zusammenzufassen; über viele Blöcke verstreute Schreibzugriffe können zur Verdrängung vieler veränderter Blöcke führen. Untere Caches verwenden häufig das Rückschreibverfahren, um den Datenverkehr zum DRAM zu begrenzen. L1-Datencaches können beide Strategien verwenden.

Ein Schreibpuffer verbirgt Wartezeit, nicht Datenverkehr

Ein Schreibpuffer stellt ausstehende Schreibzugriffe auf die untere Ebene in eine Warteschlange. Beim Durchschreibverfahren kann der Prozessor fortfahren, sobald ein Speicherbefehl im Puffer steht, statt auf den Abschluss durch den unteren Speicher zu warten. Die untere Ebene holt auf, während die gepufferten Speicherbefehle abgearbeitet werden; sie kann vorübergehend hinter dem zwischengespeicherten Wert zurückbleiben.

Der Puffer hat eine endliche Kapazität. Treffen Speicherbefehle lange genug schneller ein, als die untere Ebene sie annimmt, füllt er sich und der Prozessor hält an. Ein Puffer verändert, wann der Prozessor wartet, nicht die dauerhaft verfügbare Bandbreite des Ziels.

Ohne Pufferung oder Überlappung wird aus einem Basis-CPI-Wert von 1 der Wert $1+\mathrm{0,1}\times 100=11$, wenn 10 % der Befehle speichern und jeder Speicherbefehl 100 Wartezyklen hinzufügt. Pufferung kann einen großen Teil dieser Verzögerung verbergen, wenn das Ziel im Mittel Schritt hält.

Einen Schreibfehlzugriff gesondert behandeln

Das Write-Allocate-Verfahren holt den fehlenden Block in den Cache und führt dann den Speicherbefehl aus. Es passt gut zum Rückschreibverfahren, weil spätere Zugriffe und Schreibvorgänge diesen Block wiederverwenden können. Das No-Write-Allocate-Verfahren sendet den Speicherbefehl nach unten, ohne diesen Cache zu füllen. Es passt gut zum Durchschreibverfahren und kann vermeiden, dass bei einer einmaligen Ausgabefolge nützliche Blöcke verdrängt werden.

Diese Strategien werden unabhängig voneinander gewählt. Dass ein Cache das Durchschreibverfahren nutzt, sagt für sich allein nicht, ob bei einem Schreibfehlzugriff eine Cachezeile angelegt wird; ein Zugriffsprotokoll muss beide Strategien angeben.

Ein Fehlzugriff beim Rückschreibverfahren, der einen veränderten Block zur Verdrängung auswählt, umfasst neben dem eingehenden Laden auch ausgehende Daten. Das erhöht die Verzögerung, sofern Puffer oder Überlappung nicht einen Teil der Arbeit verbergen. Auch andere Kerne und Ein-/Ausgabegeräte benötigen eine konsistente Sicht, wenn der untere Speicher veraltet ist. Kohärenz- und Systemmechanismen koordinieren diese Sichtbarkeit; ein Änderungsbit allein hält nur ausstehende Änderungen fest.

Eine hohe Trefferrate ist nützlich, aber kein vollständiges Leistungsmaß. Wenige teure Fehlzugriffe können den Mittelwert bestimmen, und ein Entwurf, der mehr Fehlzugriffe vermeidet, kann dennoch unterliegen, wenn seine Suche zu langsam wird.

Mit Raten und Zeitdefinitionen beginnen

Die beiden Anteile ergeben zusammen eins. Wandle Prozentangaben vor dem Multiplizieren in Anteile um: 5 % sind 0,05.

Die mittlere Speicherzugriffszeit oder AMAT ist

Jede Anforderung prüft den Cache, auch Anforderungen, die fehlschlagen. Die Fehlzugriffsverzögerung ist die zusätzliche Verzögerung nach dieser Suche. Gleichwertig kannst du die Trefferzeit mit dem Trefferanteil und die gesamte Fehlzugriffszeit mit dem Fehlzugriffsanteil gewichten; durch Ausmultiplizieren ergibt sich dieselbe Formel.

Bei einer Trefferzeit von 1 Taktzyklus, 5 % Fehlzugriffen und einer zusätzlichen Verzögerung von 100 Taktzyklen beträgt die AMAT $1+\mathrm{0,05}\times 100=6$ Taktzyklen. Bei 2 GHz dauert jeder Taktzyklus 0,5 ns, das sind also 3 ns. Rechne entweder vollständig in Taktzyklen oder vollständig in Zeiteinheiten und wandle bei Bedarf das Endergebnis um.

Vollständige Entwürfe vergleichen

Cache A hat eine Suchzeit von 1,0 ns und 5 % Fehlzugriffe. Cache B hat eine Suchzeit von 1,2 ns und 3,5 % Fehlzugriffe. Bei einer Fehlzugriffsverzögerung von 50 ns gilt:

B gewinnt, weil die vermiedenen teuren Fehlzugriffe seine langsamere Suche mehr als ausgleichen. Sinkt die Verzögerung auf 10 ns, benötigt A 1,5 ns und B 1,55 ns. Nun gewinnt A. Der Nutzen einer verbesserten Fehlzugriffsrate ist proportional zur vermiedenen Verzögerung.

Befehls- und Datenzugriffe richtig gewichten

Angenommen, jeder Befehl erzeugt im Mittel einen Befehlsabruf und 0,3 Datenzugriffe. Die Fehlzugriffsrate für Befehle beträgt 2 % und die für Daten 4 %. Bei 100 Befehlen gibt es 100 Befehlsabrufe und 30 Datenzugriffe. Erwartet werden $100\times \mathrm{0,02}+30\times \mathrm{0,04}=\mathrm{3,2}$ Fehlzugriffe bei 130 Zugriffen.

Der kombinierte Fehlzugriffsanteil beträgt daher $\frac{\mathrm{0,02}+\mathrm{0,3}\times \mathrm{0,04}}{\mathrm{1,3}}\mathrm{.}$ Bei gleichen Trefferzeiten von 1 Taktzyklus und Fehlzugriffsverzögerungen von 100 Taktzyklen beträgt die AMAT etwa 3,46 Taktzyklen pro Speicherzugriff. Würde man 2 % und 4 % direkt mitteln, erhielten die beiden Zugriffsarten fälschlich dasselbe Gewicht.

Eine Übertragungsverzögerung abschätzen

Eine Blockanforderung kann eine anfängliche Latenz und anschließend eine Übertragungszeit umfassen. Bei 60 ns Latenz, einer 64 Byte großen Cachezeile und 16 GB/s Bandbreite dauert die Übertragung 4 ns, sodass die zusätzliche Verzögerung etwa 64 ns beträgt. Bei 3 GHz gibt es 3 Taktzyklen/ns, das sind also 192 Taktzyklen.

Prüfe, was die Zeitangabe einer Aufgabe umfasst. Gibt sie eine vollständige Fehlzugriffszeit an, ziehe die Trefferprüfung ab, bevor du den Wert als zusätzliche Fehlzugriffsverzögerung behandelst. Würdest du die Suche doppelt berechnen, überschätztest du die AMAT.

Die AMAT misst die Zeit pro Speicherzugriff. Der CPI-Wert misst Taktzyklen pro ausgeführtem Befehl. Um beides zu verbinden, zähle, wie viele Befehls- und Datenanforderungen jeder Befehl erzeugt und wie viele Wartezyklen diese Anforderungen hinzufügen.

Die Warteterme addieren

Bei einem einfachen Prozessor mit Ausführung in Befehlsreihenfolge, dessen Cache-Treffer im Basis-CPI-Wert enthalten sind, fügt ein nicht überlappter Fehlzugriff seine zusätzliche Verzögerung hinzu. Mit der Befehlsfehlzugriffsrate $m_I$, den Datenzugriffen pro Befehl $f_D$, der Datenfehlzugriffsrate $m_D$ und der Verzögerung $P$ in Taktzyklen gilt:

In diesem Modell erzeugt jeder Befehl eine Anforderung zum Holen des Befehls. Nur Lade- und Speicherbefehle erzeugen Datenanforderungen, daher multipliziere ihre Fehlzugriffsrate mit ihrer Häufigkeit. Unterscheiden sich ihre Verzögerungen, verwende in jedem Term eine eigene Verzögerung.

Von Anforderungen zu Wartezyklen rechnen

Der Basis-CPI-Wert sei 1,0, die Befehlsfehlzugriffsrate 2 %, die Häufigkeit von Lade- und Speicherbefehlen 30 %, die Datenfehlzugriffsrate 4 % und die Fehlzugriffsverzögerung 100 Taktzyklen. Die Befehlswartezyklen betragen $\mathrm{0,02}\times 100=\mathrm{2,0}$ Taktzyklen pro Befehl. Die Datenwartezyklen betragen $\mathrm{0,3}\times \mathrm{0,04}\times 100=\mathrm{1,2}$. Der gesamte CPI-Wert ist 4,2.

Mit einem perfekten Cache würde der CPI-Wert wieder auf 1,0 sinken. Bei gleichem Takt und gleicher Befehlsanzahl wäre das ein 4,2-facher Speedup. Die Datenfehlzugriffsrate ist doppelt so hoch wie die Befehlsfehlzugriffsrate, dennoch kosten Befehlsfehlzugriffe insgesamt mehr Zeit, weil jeder Befehl geholt wird und nur 30 % auf Daten zugreifen.

Setze die AMAT nicht direkt als CPI-Wert ein. Die AMAT gilt pro Zugriff und enthält die Bedienzeit bei Treffern. Die CPI-Berechnung addiert hier nur Wartezyklen über die bereits gezählte Basisausführung hinaus.

Ein schnellerer Takt erhöht die Kosten jedes Speicherwartens in Taktzyklen

Die DRAM-Latenz in Nanosekunden sinkt nicht, wenn der Prozessortakt steigt. Eine Verdopplung des Takts macht aus derselben Speicherwartezeit von 100 Taktzyklen beim neuen Takt 200 Taktzyklen. Der CPI-Wert des Beispiels wird zu

Jeder neue Taktzyklus ist halb so lang, sodass sich die relative Ausführungszeit von 4,2 alten Taktzyklen pro Befehl auf umgerechnet 3,7 alte Taktzyklen ändert. Der Speedup beträgt $\mathrm{4,2}\mathrm{/}\mathrm{3,7}\approx \mathrm{1,14}$ und liegt damit weit unter zwei.

Verbesserungen verschieben den Engpass

Sinkt der Basis-CPI-Wert von 1,0 auf 0,5, während die Speicherwartezyklen bei 3,2 bleiben, wird der gesamte CPI-Wert zu 3,7. Wartezyklen beanspruchen nun $\mathrm{3,2}\mathrm{/}\mathrm{3,7}\approx 86\mathrm{\%}$ der Taktzyklen. Eine Verbesserung des Kerns macht die unveränderte Speicherverzögerung zu einem größeren Anteil der Laufzeit, ein Beispiel für das amdahlsche Gesetz.

Das einfache Modell zählt alle Fehlzugriffsverzögerungen als Wartezyklen. Ausführung außerhalb der Befehlsreihenfolge und nichtblockierende Caches können Fehlzugriffe mit nützlicher Arbeit oder anderen Fehlzugriffen überlappen. Um diese Überlappung auf einem realen Rechner zu beurteilen, benötigt man Hardwarezähler und Laufzeitmessungen. Halte beim Vergleich von Entwürfen mit diesem Modell den Befehlsstrom gleich und gib an, welche Verzögerungen bereits im Basis-CPI-Wert enthalten sind.

Ein unterer Cache verringert die Verzögerung bei einem L1-Fehlzugriff. Er hat eine eigene Suchzeit und Fehlzugriffsrate, daher müssen die erwarteten Kosten der Hierarchie den Anteil der Anforderungen berücksichtigen, der jede Ebene erreicht.

Den Nenner der Rate beachten

Die lokale Fehlzugriffsrate einer Ebene ist die Anzahl ihrer Fehlzugriffe geteilt durch die Anzahl der Anforderungen an diese Ebene. Ihre globale Fehlzugriffsrate ist die Anzahl ihrer Fehlzugriffe geteilt durch alle Speicheranforderungen des Prozessors.

Schlagen 4 % der Zugriffe in L1 und davon 25 % in L2 fehl, erreichen nur $\mathrm{0,04}\times \mathrm{0,25}=\mathrm{0,01}$ oder 1 % der ursprünglichen Anforderungen den Hauptspeicher. Eine lokale L2-Fehlzugriffsrate von 25 % sagt für sich allein nichts über den Anteil aller Anforderungen aus, die den Hauptspeicher erreichen: L1 hat den Strom zuerst gefiltert.

Für zwei nacheinander geprüfte Ebenen gilt:

Dabei sind $H_1$ und $H_2$ Suchzeiten, $m_1$ und $m_2$ lokale Fehlzugriffsanteile und $P$ die zusätzliche Hauptspeicherverzögerung. Nur bei L1-Fehlzugriffen fällt die L2-Suche an. Nur bei Fehlzugriffen in beiden Ebenen fällt die Hauptspeicherverzögerung an.

Von innen nach außen auswerten

Verwende eine L1-Trefferzeit von 1 Taktzyklus, eine L1-Fehlzugriffsrate von 4 %, eine L2-Trefferzeit von 12 Taktzyklen, eine lokale L2-Fehlzugriffsrate von 25 % und eine Hauptspeicherverzögerung von 200 Taktzyklen. Eine Anforderung, die L2 erreicht, benötigt im Mittel $12+\mathrm{0,25}\times 200=62$ zusätzliche Taktzyklen. Somit gilt

Ohne L2 betrüge die AMAT $1+\mathrm{0,04}\times 200=9$ Taktzyklen. Die L2-Suche erzeugt bei jedem L1-Fehlzugriff zusätzliche Arbeit, verhindert aber bei den meisten dieser Anforderungen die viel größere Hauptspeicherverzögerung.

Setze die globale L2-Fehlzugriffsrate von 1 % innerhalb der Klammern nicht für $m_2$ ein. Das würde den L1-Fehlzugriffsanteil zweimal multiplizieren. Eine gleichwertige ausmultiplizierte Form verwendet die globale Rate direkt:

L3 nach derselben Logik hinzufügen

Bei einer L3-Trefferzeit von 40 Taktzyklen und einer lokalen Fehlzugriffsrate von 40 % beträgt der L3-Bedienterm $40+\mathrm{0,4}\times 200=120$ Taktzyklen. Der L2-Term wird zu $12+\mathrm{0,25}\times 120=42$ Taktzyklen. Die gesamte AMAT beträgt $1+\mathrm{0,04}\times 42=\mathrm{2,68}$ Taktzyklen.

Der vollständige Ausdruck lautet $H_1+m_1(H_2+m_2(H_3+m_{3}P))\mathrm{.}$ L3 wird nur bei Anforderungen berechnet, die in beiden oberen Ebenen fehlschlagen. Eine Ebene mit einer sehr langsamen Suche oder sehr wenigen Treffern kann mehr Verzögerung hinzufügen, als sie einspart.

Für den CPI-Wert Raten pro Befehl verwenden

Angenommen, der Basis-CPI-Wert ist 1, L1 erzeugt 0,032 Fehlzugriffe pro Befehl und der Hauptspeicher fügt 100 Taktzyklen hinzu. Ohne L2 beträgt der CPI-Wert $1+\mathrm{0,032}\times 100=\mathrm{4,2}$. Füge einen L2-Cache mit einer Trefferzeit von 10 Taktzyklen und einer lokalen Fehlzugriffsrate von 25 % hinzu:

Bei gleichem Takt beträgt der Speedup $\mathrm{4,2}\mathrm{/}\mathrm{2,12}\approx \mathrm{1,98}$. Der Wert 0,032 gibt bereits Fehlzugriffe pro Befehl an; ein weiterer Faktor für die Zugriffshäufigkeit würde diese Häufigkeit also doppelt zählen.

Virtueller Speicher trennt die von einem Programm verwendeten Adressen von den Plätzen, an denen seine Daten im Hauptspeicher liegen. Jeder Prozess erhält seinen eigenen virtuellen Adressraum. Die Hardware übersetzt Adressen anhand von Abbildungen des Betriebssystems und prüft, ob jeder angeforderte Zugriff erlaubt ist.

Die Seitennummer ersetzen, den Offset erhalten

Eine Seite ist ein Bereich virtueller Adressen mit fester Größe. Ein Seitenrahmen ist ein seitengroßer Platz im physischen Speicher. Bei 4-KiB-Seiten enthält jede Seite 4096 Byte, sodass der Seitenoffset 12 Bit benötigt. Die verbleibenden hohen Bits der virtuellen Adresse bilden die virtuelle Seitennummer oder VPN.

Ein Seitentabelleneintrag oder PTE bildet eine VPN auf eine physische Seitennummer oder PPN ab. Die Übersetzung ersetzt die Seitennummer, erhält aber den Offset: Im physischen Seitenrahmen wird dieselbe Byteposition ausgewählt.

Für die virtuelle Adresse 0x00403A7C ergeben die niederwertigen 12 Bits den Offset 0xA7C, und die VPN ist 0x00403. Wird diese VPN auf die PPN 0x02F1C abgebildet, lautet die physische Adresse 0x02F1CA7C. Das Anhängen eines 12-Bit-Offsets entspricht der Multiplikation der PPN mit 4096 und der Addition des Offsets; die Addition der unverschobenen PPN würde die falsche Adresse ergeben.

Eine Abbildung umfasst Berechtigungen

Ein PTE hält die Gültigkeit, eine physische Seitennummer und Berechtigungen wie Lesen, Schreiben, Ausführen und Benutzerzugriff fest. Zugriffs- und Änderungsbits halten Nutzung und Veränderung fest. Ein privilegiertes Prozessorregister bezeichnet die Seitentabelle; RISC-V verwendet satp. Benutzerprogramme können diese Abbildungen nicht beliebig umschreiben.

Getrennte Seitentabellen ermöglichen es, dass dieselbe virtuelle Adresse in verschiedenen Prozessen unterschiedliche physische Daten bezeichnet. Sie erlauben auch eine gezielte gemeinsame Nutzung: Zwei Prozesse können virtuelle Seiten auf denselben physischen Seitenrahmen abbilden, etwa um schreibgeschützten Bibliothekscode zu teilen. Sowohl Isolation als auch gemeinsame Nutzung ergeben sich aus kontrollierten Abbildungen.

Ein Seitenfehler erfordert die Behandlung durch das Betriebssystem

Ein Seitenfehler ist eine Ausnahme, die ausgelöst wird, wenn die Übersetzung oder ihre Berechtigungsprüfungen nicht normal abgeschlossen werden können. Ein Speicherbefehl auf eine schreibgeschützte Abbildung kann einen Seitenfehler auslösen, selbst wenn die Seite bereits im Hauptspeicher liegt.

Fehlt eine benötigte Seite im Hauptspeicher, beschafft das Betriebssystem einen physischen Seitenrahmen, liest die Seite aus dem Massenspeicher, aktualisiert die Abbildung und startet den Befehl erneut. Eine veränderte zu verdrängende Seite muss möglicherweise zuerst zurückgeschrieben werden. Manche Seitenfehler werden ohne Massenspeicher aufgelöst, etwa durch das Einrichten einer Abbildung auf eine vorhandene Seite oder die Behandlung von Copy-on-Write. Ein Zugriff, den das System nicht erlauben kann, kann stattdessen mit einem Prozessfehler enden.

Seitenfehler mit Massenspeicherzugriff sind teuer. Bei 3 GHz kostet eine Verzögerung von 50 µs 150.000 Taktzyklen und 1 ms kostet 3.000.000. Große Seiten verteilen Übertragungskosten auf viele Bytes. Eine virtuelle Seite kann jeden geeigneten Seitenrahmen belegen, und veränderte Seiten nutzen das Rückschreibverfahren, weil die Weiterleitung jedes Speicherbefehls an den Massenspeicher zu langsam wäre.

Auch Seitentabellen verbrauchen Speicher

Eine flache Tabelle für virtuelle 32-Bit-Adressen und 4-KiB-Seiten benötigt $2^{32-12}=2^{20}$ Einträge. Bei 4 Byte pro Eintrag sind das 4 MiB pro Prozess. Reale Entwürfe verwenden mehrstufige Tabellen, um bei dünn belegten Adressräumen nicht eine riesige flache Tabelle anlegen zu müssen; RISC-V Sv39 verwendet drei Ebenen.

Virtueller Speicher umfasst Adressübersetzung, Schutz und gemeinsame Nutzung, selbst wenn jede verwendete Seite in den DRAM passt. Das Auslagern auf den Massenspeicher ist eine Anwendung dieses Mechanismus, nicht sein gesamter Zweck.

Die Adressübersetzung kann mehrere Seitentabellen-Lesezugriffe erfordern, bevor ein Datenzugriff fortgesetzt wird. Seitentabelleneinträge können in gewöhnlichen Caches treffen, aber diese Lesezugriffe erzeugen dennoch zusätzliche Arbeit. Der Translation Lookaside Buffer oder TLB speichert kürzlich verwendete Übersetzungen zwischen, sodass die meisten Zugriffe einen Seitentabellendurchlauf vermeiden können.

Einen erlaubten Zugriff verfolgen

Die virtuelle Seitennummer wird im TLB gesucht. Ein passender Eintrag liefert die physische Seitennummer und Berechtigungsinformationen. Nach den Berechtigungsprüfungen bezeichnet die physische Adresse die Daten in der Cachehierarchie.

Bei einem TLB-Fehlzugriff beschafft ein Seitentabellendurchlauf die Übersetzung. Ist die Abbildung gültig und erlaubt die Anforderung, wird die Übersetzung in den TLB eingetragen und der Zugriff fortgesetzt. RISC-V und x86-64 verwenden normalerweise Hardwareeinheiten für den Durchlauf; manche Architekturen verwenden Softwareroutinen. Kann die Abbildung die Anforderung nicht bedienen, löst der Prozessor einen Seitenfehler für das Betriebssystem aus.

Ein TLB-Fehlzugriff kann daher mit einem Datencache-Treffer oder einem Datencache-Fehlzugriff einhergehen. Er besagt, dass die Übersetzung im TLB fehlte, nicht, dass die Seite im DRAM fehlte. Umgekehrt kann ein TLB-Treffer mit einem Cache-Fehlzugriff oder einem Berechtigungsfehler bei einem verbotenen Zugriff einhergehen. Übersetzung und Vorhandensein von Daten beantworten unterschiedliche Fragen.

Den durch Übersetzungen abgedeckten Speicher zählen

Die TLB-Reichweite ist die Anzahl der Einträge multipliziert mit der Seitengröße. Ein TLB mit 64 Einträgen und 4-KiB-Seiten deckt gleichzeitig 256 KiB ab. Bei 2-MiB-Seiten decken 64 Einträge 128 MiB ab. Zugriffe auf viele verschiedene Seiten können die Übersetzungskapazität erschöpfen, selbst wenn nur wenige Bytes jeder Seite genutzt werden.

TLBs der ersten Ebene enthalten oft einige zehn Einträge; untere TLB-Ebenen können einige hundert oder tausend enthalten. Ihre Einträge umfassen Seitennummern-Tags, physische Abbildungen, Berechtigungen und häufig Adressraumkennungen. Lokalität innerhalb von Seiten und Wiederverwendung bei benachbarten Zugriffen halten die Trefferraten der Übersetzung hoch.

Benötigen beispielsweise 1 % der Zugriffe einen Seitentabellendurchlauf von 30 Taktzyklen und wird die TLB-Trefferzeit ansonsten verborgen, fügen die Durchläufe im Mittel $\mathrm{0,01}\times 30=\mathrm{0,3}$ Taktzyklen pro Zugriff hinzu. Dieses Beispiel setzt voraus, dass die Durchläufe normal abgeschlossen werden, und schließt die Behandlung von Seitenfehlern aus.

Indizierung und Übersetzung überlappen

Ein physisch indizierter und physisch getaggter Cache wartet auf eine physische Adresse, bevor er seinen Satz auswählt. Ein virtuell indizierter und physisch getaggter Cache oder VIPT-Cache beginnt einen Satz zu lesen, während der TLB übersetzt, und vergleicht anschließend physische Tags.

Der einfache VIPT-Entwurf entnimmt alle Index- und Blockoffset-Bits dem Seitenoffset, weil die Übersetzung diese Bits erhält. Dies erfordert

Bei 4-KiB-Seiten hat ein 8-fach assoziativer Cache mit 32 KiB 4 KiB pro Weg und erfüllt die Bedingung. Auch ein 12-fach assoziativer Cache mit 48 KiB erfüllt sie. Ein 8-fach assoziativer Cache mit 64 KiB hat 8 KiB pro Weg und benötigt ein Seitennummernbit für die Indizierung, braucht also mehr Wege oder eine zusätzliche Behandlung.

Zwischengespeicherte Abbildungen aktuell halten

Übersetzungen gehören zu Adressräumen. Ein Kontextwechsel kann alte Einträge löschen oder sie durch Adressraumkennungen oder ASIDs unterscheiden. Änderungen an Abbildungen erfordern die entsprechende Pflege des Übersetzungscaches; RISC-V stellt sfence.vma bereit. Wird eine Seite aus dem Hauptspeicher verdrängt, darf ihre alte Übersetzung im TLB nicht nutzbar bleiben. Der TLB enthält Abbildungen und Zugriffsrechte, während gewöhnliche Caches die Daten und Befehle des Programms enthalten.

Code, der das Cacheverhalten berücksichtigt, nutzt geholte Bytes, bevor ihr Block verdrängt wird. Beginne mit den Adressen, die die innere Schleife erzeugt. Frage dann, welche Daten wiederverwendet werden, wie weit die Zugriffe auseinanderliegen und ob diese Blöcke gemeinsam im Cache liegen können.

Arrays in Speicherreihenfolge durchlaufen

C und C++ speichern rechteckige Arrays zeilenweise. Benachbarte Spalten einer Zeile liegen im Speicher nebeneinander. Fortran, MATLAB und Julia speichern spaltenweise; NumPy-Arrays werden standardmäßig zeilenweise gespeichert. Der effiziente innere Durchlauf folgt dem tatsächlichen Layout.

Ein C-Array double a[1024][1024] belegt 8 MiB. Jede Zeile benötigt 8.192 Byte. Bei 64 Byte großen Cachezeilen enthält jede Cachezeile acht Double-Werte. Ein zeilenweiser Durchlauf kann alle acht nutzen, bevor er weitergeht; in einem einfachen Modell mit Laden auf Anforderung ergibt das etwa einen Kaltstart-Fehlzugriff pro acht Zugriffe.

Ein spaltenweiser Durchlauf legt zwischen aufeinanderfolgenden Zugriffen 8.192 Byte zurück. Er berührt 1.024 verschiedene Cachezeilen, bevor er in der nächsten Spalte erneut auf benachbarte Daten zugreift. Diese Cachezeilen belegen 64 KiB und überschreiten damit einen L1-Cache mit 32 KiB. Sie stehen auch in Konflikt: In einem Cache mit 64 Sätzen erhält eine Schrittweite von 128 Cachezeilen denselben Satzindex. Ein 8-fach assoziativer Satz kann keine 1.024 konkurrierenden Cachezeilen halten.

Padding einer Zeile auf 1.032 Double-Werte ergibt eine Schrittweite von 8.256 Byte oder 129 Cachezeilen. Aufeinanderfolgende Zeilen rücken dann modulo 64 jeweils um einen Satz weiter und verteilen so die Anforderungen. Padding behebt Abbildungskonflikte; die Datenmenge ist weiterhin relevant.

Schleifen vertauschen, wenn das Ergebnis erhalten bleibt

Die Schleifenvertauschung ändert, welche Schleife innerhalb einer anderen läuft. Bei zeilenweise gespeicherter Matrixmultiplikation durchläuft die Reihenfolge i, j, k eine Zeile von A, aber eine Spalte von B. In einem Modell für große Datenströme mit geringer Wiederverwendung zwischen Durchläufen kostet das etwa $1\mathrm{/}8+1=\mathrm{1,125}$ Fehlzugriffe pro innerer Iteration.

Bei i, k, j durchläuft die innere Schleife Zeilen von B und C, während ein Element von A wiederverwendet wird. Zählt man für beide Zeilen jeweils einen neu geladenen Datenstrom, ergibt das etwa $1\mathrm{/}8+1\mathrm{/}8=\mathrm{0,25}$ Fehlzugriffe pro Iteration, 4,5-mal weniger. Bleibt die wiederholt aktualisierte Zeile von C im Cache, nähert sich die Anzahl 0,125. Cachekapazität und Konflikte entscheiden, welche Wiederverwendung erhalten bleibt.

Die Vertauschung muss das erforderliche Berechnungsverhalten erhalten. Abhängigkeiten, überlappende Zeiger und die Auswertungsreihenfolge von Gleitkommaoperationen können Transformationen einschränken; Compiler benötigen einen Nachweis, dass eine Änderung erlaubt ist.

Die verwendeten Felder holen

Ein Array von Strukturen gruppiert alle Felder eines Objekts. Eine Struktur von Arrays gruppiert ein Feld über mehrere Objekte hinweg. Enthält ein Teilchendatensatz acht Double-Werte in einer 64 Byte großen Cachezeile, werden beim Summieren allein von x über eine Million ausgerichtete Datensätze etwa 64 MB geladen. Ein separates zusammenhängendes x-Array lädt etwa 8 MB und nutzt jeden geholten Double-Wert. Für Code, der alle Teilchenfelder gemeinsam nutzt, kann das ursprüngliche Strukturlayout günstiger sein.

Verkettete Knoten können verstreut liegen, und jede nächste Adresse kann von einem gerade geladenen Zeiger abhängen. Zusammenhängende Arrays oder Knotenpools können die Lokalität verbessern. Kompakte häufig genutzte Felder ermöglichen außerdem, dass mehr aktive Daten in jede Ebene passen.

Miss vor und nach einer Änderung die Laufzeit und relevante Hardwarezähler. Cache-Fehlzugriffe können eine langsame Schleife erklären, aber auch Berechnungen, Bandbreite oder Sprünge können der begrenzende Faktor sein. Halte Eingabe und Ergebnisse vergleichbar, damit ein Geschwindigkeitsunterschied die untersuchte Änderung widerspiegelt.

Schleifenvertauschung verbessert die Zugriffsreihenfolge. Die Blockung, auch Kachelung genannt, geht weiter, indem sie einen kleinen Datenbereich aktiv hält, bis seine nützliche Wiederverwendung abgeschlossen ist. Prefetching zieht eine künftige Übertragung vor, sodass sich ihre Verzögerung mit nützlicher Arbeit überlappt.

Eine Gruppe von Kacheln im Cache halten

Bei der gekachelten Multiplikation quadratischer Matrizen tragen eine Kachel von A und eine Kachel von B zu einer Kachel von C bei. Eine Kachel mit der Seitenlänge $b$ enthält $b^2$ Elemente. Die wiederholte Arbeit an diesen kleinen Kacheln verwendet Daten erneut, bevor der nächste Bereich folgt.

Bei 8 Byte großen Double-Werten benötigen drei Kacheln $3b^2\times 8=24b^2$ Byte. In einem Cache mit 32 KiB liegt die Kapazitätsschranke bei

Eine Seitenlänge von 32 benötigt 24.576 Byte oder 24 KiB und lässt etwas Platz für andere Daten. Wählt man 36 nur deshalb, weil die Rechnung es erlaubt, bleibt viel weniger Platz und es können Konflikte auftreten. Die Kapazität ist eine erste Schätzung; tatsächliche Kachelgrößen werden durch Messungen abgestimmt.

Ein gekachelter Durchlauf erhöht die äußere Schleife um die Kachelgröße. Die inneren Schranken stoppen beim kleineren Wert aus Kachelende und Matrixgröße. Ist beispielsweise eine Dimension 70 und haben Kacheln die Seitenlänge 32, hat die letzte Kachel entlang dieser Dimension nur sechs Elemente. Eine letzte Kachel voller Größe würde über das Array hinaus zugreifen.

Abschätzen, was Wiederverwendung spart

In einem vereinfachten Modell für große Matrizen mit 64 Byte großen Cachezeilen hat die naive Reihenfolge i, j, k etwa $\mathrm{1,125}{N}^3$ Fehlzugriffe, wenn durchlaufene Zeilen beim nächsten Durchgang nicht mehr im Cache liegen. Eine gekachelte Variante kann dies auf etwa $N^3\mathrm{/}(4b)$ verringern, vorausgesetzt, die drei bearbeiteten Kacheln bleiben im Cache und Konflikte werden vernachlässigt.

Für $N=1024$ und $b=32$ betragen diese Schätzungen etwa 1,2 Milliarden und 8,4 Millionen Fehlzugriffe, ein Faktor von 144. Beide Varianten führen weiterhin etwa $2N^3$ Gleitkommaoperationen aus. Die Einsparung liegt in wiederholten Datenübertragungen, nicht in der Anzahl der Rechenoperationen der Multiplikation. Das Modell beschreibt ideale Wiederverwendung; der gemessene Speedup hängt auch von Bandbreite, Ausführung und anderem Aufwand ab.

Früh genug vorausladen, um Latenz zu verbergen

Hardware-Prefetcher erkennen Datenströme wie sequenzielle Zugriffe oder Zugriffe mit konstanter Schrittweite. Sie fordern Cachezeilen an, bevor Zugriffe auf Anforderung sie benötigen. Software kann ebenfalls das Vorausladen anfordern, zum Beispiel mit __builtin_prefetch von GCC oder Clang.

Der Zeitpunkt ist entscheidend. Eine zu spät gestellte Anforderung lässt den anfordernden Zugriff warten. Eine zu früh gestellte Anforderung kann eine Cachezeile laden, die vor ihrer Verwendung wieder verdrängt wird. Eine ungenaue Anforderung verbraucht Bandbreite und Cacheplatz, ohne dem Programm zu helfen. Das Verfolgen von Zeigern lässt sich schwerer durch Prefetching unterstützen, weil die nächste Adresse oft erst bekannt wird, nachdem der aktuelle Knoten eingetroffen ist.

Rechtzeitiges Prefetching kann spätere Fehlzugriffe auf Anforderung in Treffer verwandeln, aber die Cachezeilen durchlaufen weiterhin die Hierarchie. Es verbirgt Latenz, statt die benötigten Nutzdaten eines sequenziellen Durchlaufs zu verringern. Kachelung hilft, wenn Werte wiederverwendet werden; ein einmaliger Durchlauf hat keine wiederholt verwendeten Daten, die gehalten werden müssten, und kann bereits durch die Speicherbandbreite begrenzt sein.