Cache-Speicher: Funktion, Hits und Grenzen erklärt

Ein Cache ist ein schneller Pufferspeicher (ein Zwischenspeicher). Er hilft, wiederholte Zugriffe auf vergleichsweise langsame Datenspeicher zu vermeiden. Daten, die schon einmal geladen wurden, bleiben im Cache und können später schneller abgerufen werden.

In einer Speicherhierarchie (Speicher, geordnet von schnell und klein bis langsam und groß) liegt der Cache zwischen CPU und Arbeitsspeicher. Auf vielen heutigen Computern arbeiten Prozessorregister in der Regel im Takt der CPU, also genauso schnell wie sie. Prozessorcaches brauchen etwa einige Dutzend Taktzyklen (Arbeitsschritte im Takt der CPU), abhängig vom Level, und der Arbeitsspeicher hunderte Taktzyklen. Das Ziel des Caches ist eine kürzere Zugriffszeit und/oder weniger Zugriffe auf das langsame Hintergrundmedium (den langsameren Speicher hinter dem Cache).

Das lohnt sich nur dort, wo die Zugriffszeit die Gesamtleistung deutlich beeinflusst. Bei CPUs kann ein Cache den Flaschenhals der Von-Neumann-Architektur verringern. Die Ausführungsgeschwindigkeit von Programmen kann dadurch im Mittel enorm gesteigert werden.

Wenn Daten angefragt werden, wird zuerst im Cache nachgesehen. Liegen die Daten dort, nennt man das Cache Hit (Cachetreffer). Liegen sie nicht dort, nennt man das Cache Miss. Beim Lesen heißen die Fälle Read Hit und Read Miss, beim Schreiben Write Hit und Write Miss. Bei einem Miss muss der Zugreifende warten, bis die Daten vom langsamen Hintergrundmedium geladen wurden.

Die Hit Rate ist die Anzahl der Anfragen mit Hit geteilt durch die Anzahl aller Anfragen an diesen Cache. Sie liegt zwischen 0 und 1. Eine Hit Rate von 0,7 (= 70 %) heißt: Bei 70 % aller Anfragen konnte der Cache die Daten sofort liefern, bei 30 % musste er passen. Die Miss Rate ist analog definiert, und es gilt: Miss Rate = 1 − Hit Rate.

Misses haben verschiedene Ursachen. Ein Capacity Miss tritt auf, wenn der Cache zu klein ist: Daten waren im Cache, wurden wieder entfernt und werden erneut gebraucht. Ein Compulsory Miss ist der erstmalige Zugriff auf eine Adresse, deren Daten noch nicht im Cache sind, während der Cache noch freien Platz hat. Wegen der Misses ist die Ausführungszeit eines Zugriffs nicht immer konstant. Das Zeitverhalten ist also schlecht vorhersagbar.

Die Lokalitätseigenschaft beschreibt typische Computerprogramme: Die Wahrscheinlichkeit ist sehr hoch, dass Daten, die gerade benutzt werden, auch in naher Zukunft wieder benötigt werden. Das gilt für Befehle und für Daten. Man unterscheidet zwei Arten.

Zeitliche Lokalität: Auf Adressbereiche, auf die zugegriffen wird, wird mit hoher Wahrscheinlichkeit auch in naher Zukunft wieder zugegriffen. In Schleifen wird zum Beispiel immer wieder auf dieselben Befehle zurückgegriffen. Deshalb hält ein Cache Daten, auf die erst kürzlich zugegriffen wurde. Alte Daten, die lange nicht benutzt wurden, werden verdrängt. Die LRU-Strategie tauscht dafür den Block aus, auf den am längsten nicht mehr zugegriffen wurde.

Räumliche Lokalität: Nach einem Zugriff auf eine Adresse erfolgt mit hoher Wahrscheinlichkeit der nächste Zugriff auf eine Adresse in unmittelbarer Nachbarschaft. Befehle liegen meist nacheinander im Speicher, wenn kein Sprungbefehl dabei ist. Auch Arrays liegen hintereinander im Speicher. Man kann das ausnutzen, indem man bei einem Zugriff gleich die benachbarten Adressbereiche in die nächste Hierarchiestufe bringt. Cache-Nutzdaten werden in Cache-Lines gespeichert, die heutzutage 64 oder 128 Bytes groß sind.

Grenze: Verarbeitet ein Algorithmus ständig neue Daten (zum Beispiel Streaming-Daten), kann ein Cache keine Beschleunigung durch Mehrfach-Zugriffe bewirken. Allenfalls hilft er geringfügig durch read-ahead, also dadurch, dass Daten, die vermutlich bald gebraucht werden, vorab geladen werden.

Ein Cache, der sowohl groß als auch schnell ist, ist technisch aufwändig und damit meist wirtschaftlich nicht sinnvoll. Deshalb kann man mehrere Caches verwenden: einen kleinen schnellen und einen deutlich größeren, aber etwas langsameren. Beide sind noch viel schneller als der zu cachende Hintergrundspeicher. So lassen sich geringe Zugriffszeit und großer Cacheumfang gemeinsam erreichen. Das ist wichtig für die Hit Rate.

Mehrere Caches bilden eine Cachehierarchie. Sie werden als L1, L2 usw. durchnummeriert (Level 1, Level 2). Je niedriger die Nummer, desto näher liegt der Cache am schnellen Benutzer. Der L1-Cache hat die schnellste Zugriffszeit und wird als erstes durchsucht. Enthält er die Daten nicht, wird der meist etwas langsamere, aber größere L2-Cache durchsucht usw. Werden die Daten in keiner Ebene gefunden, ist das ein Cache Miss, und es muss auf den langsamen Hintergrundspeicher zugegriffen werden. Vor allem moderne CPUs haben zwei oder drei Cacheebenen.

Grenzen: Schnelle Speicher sind um Größenordnungen teurer als langsamere. Außerdem ist der Hauptprozessor platzbeschränkt und hat einen verhältnismäßig hohen Kühlungsbedarf. Deshalb kann sehr schneller Speicher nur begrenzt eingesetzt werden. Ein Cache lohnt sich zudem nur dort, wo die Zugriffszeit die Gesamtleistung deutlich beeinflusst. Bei Vektorrechnern spielt die Zugriffszeit eine untergeordnete Rolle, deshalb wird dort üblicherweise auf Caches verzichtet. Und wegen der Misses bleibt das Zeitverhalten schlecht vorhersagbar.

Wird in einen Block geschrieben, der im Cache vorhanden ist (Write Hit), gibt es zwei Möglichkeiten.

Write-through (Durchschreiben): Die Daten werden sowohl in den Cache als auch in den Hauptspeicher geschrieben. Damit ist normalerweise sichergestellt, dass beide gleich sind. Damit der Prozessor nicht jedes Mal warten muss, nutzt man bei write-through einen Pufferspeicher (write buffer). Wenn dieser voll läuft, muss der Prozessor jedoch anhalten und warten.

Write-back (Rückschreiben): Es wird nicht direkt in den Hauptspeicher geschrieben, sondern erst, wenn der entsprechende Cache-Block ersetzt werden muss. Ein Dirty-Bit zeigt an, welche Daten noch nicht im Hauptspeicher stehen. Write-back ist technisch anspruchsvoller, aber schneller als write-through.

Das Problem: Beim write-back sind Cache und Hauptspeicher vorübergehend inkonsistent, der Hauptspeicher enthält veraltete Information. Bei Multiprozessorsystemen hat üblicherweise jeder Prozessor seinen eigenen Cache und greift darüber auf einen gemeinsamen Speicher zu. Cache-Kohärenz sorgt dafür, dass die Caches für dieselbe Speicheradresse nicht unterschiedliche Daten zurückliefern. Eine temporäre Inkonsistenz ist zulässig, wenn sie spätestens bei lesenden Zugriffen identifiziert und behoben wird. Ein Weg dahin ist das Write-Invalidate-Protokoll: Vor dem Verändern einer Kopie müssen alle Kopien in anderen Caches für ungültig erklärt werden.