Cachehierarchie

Wenn man mehrere Caches einsetzt, kann man die Wahrscheinlichkeit eines „Cache-Hit“ noch steigern und damit die Anzahl der Zugriffe auf den Arbeitsspeicher weiter senken. Das ist effektiver und günstiger als ein einzelner, großer Cache. In modernen CPUs wird ein mehrstufiges Cache-Konzept mit klarer Hierarchie eingesetzt. Meistens gibt es drei Hierarchieebenen (engl. Level): 1L-Cache, 2L-Cache und 3L-Cache. Da auf der ersten Ebene häufig parallel auf Befehle und Daten zugegriffen wird, ist der Cache auf dieser Ebene (1st-Level-Cache) oft in einen separaten Befehls- und Datencache unterteilt. Während der schnelle 1st-Level-Cache nur vergleichsweise wenig Daten und Befehle aufnehmen kann, passen in einen langsameren 3rd-Level-Cache auch mehrere Megabyte Daten. Wie die Daten aus dem Arbeitsspeicher auf die einzelnen Caches verteilt werden, wird durch die Cache-Strategie festgelegt:

Exklusive Cache-Strategie

Bei der von AMD-Prozessoren genutzten Strategie wird ein an einer bestimmten Adresse gespeicherter Datenblock nur in einem Cache abgelegt. Wenn die Daten im L1-Cache nicht gefunden wurden, wird der jeweils nächsthöhere Cache abgefragt usw. Wenn in einen bereits gefüllten Cache neue Daten geschrieben werden, wird der zu ersetzende Datenblock jeweils in den Cache der nächsthöheren Ebene verschoben. Die Größe des gepufferten Speicherbereichs ergibt sich aus der Summe der Kapazitäten von L1-, L2- und L3-Cache.

• Der verfügbare Speicherplatz wird effizienter genutzt, aber dafür sind die Zugriffszeiten höher.

Inklusive Cache-Strategie

Bei Intel-CPUs wird ein an einer bestimmten Adresse gespeicherter Datenblock in jedem Cache abgelegt.

Vorteil:

• kürzere Zugriffszeiten, da beim Ersetzen vorhandener Daten keine Übertragung in einen anderen Cache stattfindet und beim Lesezugriff immer auf den schnellsten Cache zugegriffen wird.

Nachteil:

• Es sind größere Caches für dieselbe Menge an Daten nötig als bei einer exklusiven Strategie.

Aufbau

Ein Cache besteht im Wesentlichen aus folgenden Komponenten:

Cache-Controller

Der Cache-Controller steuert und überwacht den Datenaustausch zwischen CPU und Cache. Er überträgt die von der CPU angeforderten Daten vom Cache in den Arbeitsspeicher (und umgekehrt) und sorgt dafür, dass der Cache-Inhalt stets auf dem aktuellen Stand ist.

Mehreren Cache-Zeilen (engl. Cache-Lines)

Da die Zugriffszeit des Arbeitsspeichers relativ lang ist, werden bei jedem Zugriff mehrere Datenworte hintereinander übertragen. Ein solcher Block besteht üblicherweise aus 8 je 64 Bit breiten Datenworten. Im Cache wird jeder Datenblock in einer eigenen Cache-Zeile (engl. „Cache-Lines“) abgelegt. Mehrere Cache-Zeilen bilden einen Satz (engl. „Set“).

Zu jeder Cache-Zeile wird ein sogenanntes Valid-Bit („Gültigkeits“-Bit) gespeichert, das angibt, ob der zugehörige Datenblock überhaupt noch im Arbeitsspeicher vorhanden ist oder nicht. Beim Hochfahren des PCs sind zunächst alle Valid-Bits auf 0 („ungültig“) gesetzt.

Die Anzahl der Cache-Zeilen richtet sich nach der Größe des Cache und der Blockgröße. Beispiel: Ein Cache mit einer Kapazität von 64 KiB und einer Blockgröße von 64 Byte (8 x 8 Byte) hat 1.024 Cache-Zeilen (65.536 / 64).

Tag-Register

Jede Cache-Line ist mit einem eigenen Tag-Register verbunden, in dem die Adresse des entsprechenden Datenblocks im Arbeitsspeicher (Tag) abgelegt wird.

Funktionsweise

Beim Zugriff auf einen Cache muss zuerst überprüft werden, ob für die angegebene Adresse bereits eine Zeile im Cache existiert. Dabei werden die höherwertigen Bits der Adresse (gelb) mit dem Inhalt der Tag-Register verglichen. Das erfolgt mit Hilfe spezieller elektronischer Schaltkreise, Komparatoren genannt.

Im Falle einer Übereinstimmung hängt die weitere Vorgehensweise davon ab, ob Daten gelesen oder geschrieben werden sollen.

• Lesezugriff: Zuerst wird überprüft, ob die Cache-Zeile gültig ist, d.h. ob an der Adresse überhaupt (noch) ein Datenblock im Arbeitsspeicher existiert. Nur wenn das Valid-Bit gültig ist (1), wird die Cache-Zeile ausgelesen und die über das Offset adressierten Bytes an die CPU übertragen.
• Schreibzugriff: Die Daten werden in die ausgewählte Cache-Zeile geschrieben. Dabei werden die bereits vorhandenen Daten überschrieben.

Wenn keine Übereinstimmung gefunden wird, spielt die Ersetzungsstrategie eine entscheidende Rolle:

• Beim Lesezugriff wird der adressierte Datenblock als Erstes aus dem Arbeitsspeicher oder dem Cache der höheren Ebene in die Cache-Zeile, die durch die Ersetzungsstrategie bestimmt wurde, übertragen. Das Valid-Bit wird auf 1 (gültig) gesetzt, bevor die Ausgabe an die CPU erfolgt.
• Schreibzugriff: Es gibt zwei Möglichkeiten: Wenn der Cache nicht voll ist, wird die erste freie (ungültige) Cache-Zeile (Valid-Bit = 0) ausgewählt. Anderenfalls bestimmt die gewählte Ersetzungsstrategie eine bereits beschriebene Cache-Zeile. Anschließend werden die Daten von der CPU in die ausgewählte Cache-Zeile geschrieben. Das Valid-Bit wird auf 1 gesetzt, sobald die Cache-Zeile befüllt ist.

Adressformate

Vollassoziativer Cache

Direkt-abbildender und n-fach satzassoziativer Cache

Alternativ kann auch über folgende Methode die Cache-Zeile ermittelt werden: Dazu muss zuerst die Blockgröße in Byte berechnet werden. Sie beträgt im Beispiel 16 Byte (64 Byte / 4 Zeilen = 16). Um diese 4 Zeilen ansprechen zu können, wird eine 2 Bit lange Blockadresse benötigt (2^2 = 4). Um die Cache-Zeile zu erhalten, müssen die Tag-Bits von den höherwertigen Bits der Adresse (ohne Offset) abgezogen werden: 10010 – 10000 = 00010 = 2 dezimal.

Merkmale eines Cache

Neben Zugriffszeit, Kapazität und Datendurchsatz gibt es bei Caches noch weitere wichtige Unterscheidungsmerkmale:

Die Trefferquote (Anzahl Cache-Hits / Anzahl Zugriffe) ist das wichtigste Merkmal eines Cache, da sie maßgeblich für die Verarbeitungsgeschwindigkeit der CPU ist.
Beispiel: Eine CPU mit einer Taktfrequenz von 1 GHz benötigt genau einen Takt für die Ausführung eines einfachen Befehls, das entspricht 1 ns (1 / Taktfrequenz). Bei einem Zugriff auf den Arbeitsspeicher beträgt die Ausführungszeit 11 ns (10 ns Zugriffszeit), bei einem erfolgreichen Cache-Zugriff aber nur 2 ns (1 ns Zugriffszeit). Geht man von einer Cache-Trefferquote von 80% aus, erreicht die CPU eine Geschwindigkeit von 419 Mio. Befehlen/s ( [(1.000 MHz x 0,8) / 2] + [(1.000 MHz x 0,2) / 11] ), bei einer Trefferquote von 95% sind es 525 Mio. Befehle/s ( [(1.000 MHz x 0,95) / 2] + [(1.000 MHz x 0,05) / 11] ). Allein durch eine höhere Trefferquote könnte die CPU-Leistung bereits um 25% gesteigert werden!

Die Trefferquote ist abhängig von:

• der internen Organisation des Cache: Vollassoziativ, direkt-abbildend („Direct-Mapped“) oder n-fach satzassoziativ
• der Verdrängungs- oder Ersetzungsstrategie: Da nicht alle Daten in den Cache passen, muss durch eine Ersetzungsstrategie bestimmt werden, welche Cache-Zeilen zuerst ersetzt werden (zufällig, LRU oder Pseudo-LRU).
• der Schreibstrategie: Sie legt fest, wann die im Cache geänderten Cache-Zeilen in den nächsthöheren Cache bzw. in den Arbeitsspeicher geschrieben werden (write-through oder write-back).

Organisation

Die interne Organsation des Cache wird hauptsächlich durch die Assoziativität bestimmt. Sie legt fest, auf wie viele Cache-Zeilen eine Adresse im Speicher abgebildet werden kann.

Hinweis: In den folgenden Beispielen wird von einer Adressbreite von 32 Bit und einer Blöckgröße von 16 Byte ausgegangen. Ein Cache mit einer Größe von 8 KiB (8.192 Bytes) besteht folglich aus 512 Cache-Zeilen (8.192 / 16 = 512).

Vollassoziativ (Assoziativität = m)

n-fach-satzassoziativ (Assoziativität = n)

Ersetzungsstrategien

Caches sind um ein Vielfaches kleiner als Arbeitsspeicher und wären deshalb sehr schnell überfüllt. Um dies zu vermeiden, müssen Daten im Cache regelmäßig ersetzt werden. Welche Daten zuerst überschrieben werden sollen, entscheidet die Ersetzungsstrategie. Die am häufigsten anzutreffenden Strategien sind:

LRU (Least Recently Used)

Es wird zuerst die Cache-Zeile ausgewählt, auf die zuletzt am wenigsten zugegriffen wurde. Jede Zeile wird dazu mit einem Zähler versehen, der bei jedem Zugriff für jede Zeile um eins erhöht und damit sozusagen das „Alter“ des Eintrags darstellt. Die Zeile mit dem höchsten Alter wird ersetzt. Je mehr Cache-Einträge vorhanden sind, desto mehr Bit müssen für den Zähler reserviert werden. Für große Caches ist dieses Verfahren deshalb ungeeignet.

Pseudo-LRU

Intel führte deshalb ein Pseudo-LRU-Verfahren ein, bei dem ein binärer Entscheidungsbaum zur Auswahl der Cache-Zeile genutzt wird, auf die zuletzt am wenigsten zugegriffen wurde. In jeder Zeile werden drei Bits gespeichert, die jeweils für einen Knoten stehen:

Zufallsgenerator

Die einfachste und platzsparendste Methode ist der Einsatz eines Algorithmus, der die Cache-Zeile zufällig auswählt. Es wird kein Speicherplatz für zusätzliche Bits benötigt.

Schreibstrategien

Die Schreibstrategie legt fest, zu welchem Zeitpunkt die geänderte Cache-Zeile in den Speicher der darüber liegenden Ebene geschrieben worden soll.

Write-Back-Strategie (write-back = zurückschreiben)

Der geänderte Datenblock wird zunächst nur in die Cache-Zeile geschrieben. Erst wenn diese ersetzt wird, schreibt der Cache-Controller die Daten zurück in den Cache der höheren Ebene bzw. in den Arbeitsspeicher. Um feststellen zu können, ob einzelne Bytes seit dem letzten Zugriff auf die Zeile verändert wurden, ist neben dem Valid-Bit ein zusätzliches Status-Bit notwendig: Das Dirty- oder Modified-Bit (modified = verändert). Nachteil: Bis zum Ersetzungszeitpunkt ist die Kopie des Datenblocks nicht mehr mit dem „Original“ in der höheren Ebene identisch. Das ist vor allem bei Mehrkern-CPUs mit einem gemeinsamen Cache der höheren Ebene problematisch, da die anderen CPUs nichts von der Inkonsistenz wissen und auf veraltete Daten zugreifen könnten. Abhilfe schaffen sogenannte Cache-Kohärenz-Protokolle.

Write-Through-Strategie (write-through = durchschreiben)

Der geänderte Datenblock wird gleichzeitig in die Cache-Zeile und in den Cache der höheren Ebene bzw. den Arbeitsspeicher übertragen. Nachteil: Damit die CPU nicht jedes Mal warten muss, bis die Daten in den langsameren Speicher übertragen wurden, ist der Einsatz eines zusätzlichen Zwischenspeichers erforderlich.

Cache-Kohärenz

Damit ein Prozessor nicht irgendwann mit veralteten Daten arbeitet und dann falsche Ergebnisse ausgibt, müssen zwei Voraussetzungen erfüllt sein:

• Die Kopien der Datenblöcke im Cache müssen stets mit den entsprechenden Originalen im Arbeitsspeicher identisch sein.
• Der Cache von CPU A muss immer auf dem gleichen Stand sein wie der Cache von CPU B (z.B. L1 von CPU A = L1 von CPU B).

Diesen Sachverhalt bezeichnet man als Cache-Kohärenz (von lat. cohaerentia = Zusammenhang).

Um eine veränderte oder ungültige Cache-Zeile zu erkennen, gibt es bereits das Modified- bzw. Valid-Bit. Wenn jeder CPU-Kern direkt auf die Caches der anderen Kerne zugreifen und dort die entsprechenden Zeilen überprüfen und beschreiben könnte, wäre es möglich, die Caches auf dem gleichen Stand zu halten. Da dieses Verfahren aber sehr aufwändig wäre und ein sehr hohes Datenaufkommen verursachen würde, setzt man Cache-Kohärenz-Protokolle ein. Ein häufig eingesetztes Protokoll ist MESI. Die Abkürzung steht für die vier Zustände, die eine Cache-Zeile annehmen kann.

• (M)odified – Geändert: Die Cache-Zeile wurde nur in diesem Cache geändert, befindet sich aber auch noch in einem anderen Cache und ist nicht mehr mit den Daten im Arbeitsspeicher identisch. Die Zeile muss deshalb erst in den Speicher zurückgeschrieben und dann der Zustand auf „Shared“ geändert werden.
• (E)xclusive: Die Cache-Zeile befindet sich nur in diesem Cache und ist mit den Daten im Arbeitsspeicher identisch. Mögliche Zielzustände: Shared oder Modified.
• (S)hared – Geteilt: Die Cache-Zeile befindet sich in mehreren Caches und ist mit den Daten im Arbeitsspeicher identisch – der Idealzustand. Möglicher Zielzustand: Invalid.
• (I)nvalid – Ungültig: Die Daten sind nicht mehr verfügbar oder veraltet.

Eine Zuständsänderung wird entweder durch die Aktivitäten der CPU-Kerne oder explizit über Steuersignale ausgelöst. Dabei hören Cache-Controller ständig den zentralen Verteiler ab, über den die Geräte miteinander kommunizieren. Dieses Verfahren nennt sich „Snooping“ (von engl. to snoop = schnüffeln).

Beispiel mit zwei CPU-Kernen

Besondere Caches

Es gibt eine Reihe spezialisierter Caches, die nur eine bestimmte Art von Daten aufnehmen.

Micro-Operation-Cache

Um zu vermeiden, dass ein Befehl nach jeder Fetch-Phase erneut dekodiert werden muss, werden bereits dekodierte Mikroinstruktionen in einem eigenen Cache abgelegt.

TLB (Translation Lookaside Buffer)

Ein Programm arbeitet anders als der Prozessor nicht mit physischen Speicheradressen, sondern mit logischen Adressen. [Mehr dazu unter Speicherverwaltung] Damit diese in einem zeitaufwändigen Prozess nicht jedes Mal erst umgewandelt werden müssen, wird zu jeder logischen Adresse die zugehörige physische Adresse in diesem speziellen Cache abgelegt.

BTB (Branch Target Buffer = Sprungziel-Puffer)

Der BTB enthält zu jedem Sprungbefehl die Adresse des Sprungziels. [Mehr dazu unter Sprungvorhersage] Er ist ebenfalls wie ein Cache aufgebaut, als Adress-Tag werden die niedrigstwertigen n Bit der Adresse des Sprungbefehls verwendet (n hängt von der Anzahl der Einträge ab).

Victim-Cache

Der Victim-Cache (engl. für Opfer) enthält nur Datenblöcke, die aus einem anderen Cache verdrängt, also gewissermaßen zugunsten eines anderen, aktuelleren Datenblocks „geopfert“ wurden. Es handelt sich hierbei um einen vollassoziativen Cache, der vor allem das gegenseitige Überschreiben bei Caches mit geringer Assoziativität verhindern soll (siehe direkt-abbildender Cache).