Cache

Cache /kæʃ/ (auch: Schattenspeicher) bezeichnet in der EDV einen schnellen Puffer-Speicher, der in CPUs heute meist als Level-1- und Level-2-, seltener auch als Level-3-Speicher integriert ist, früher aber auch häufig auf der Hauptplatine zu finden war (bis AMD K-6II-Prozessor). Bei Festplatten befindet sich der Cache auf der Steuerplatine (siehe auch Festplattencache). In ihm werden Daten und – beim CPU-Cache – auch Programminstruktionen zwischengespeichert, wodurch diese bei einem Zugriff schneller zur Bearbeitung bereitstehen. Die Funktionsweise eines Caches beruht auf der so genannten Lokalitätseigenschaft. Vereinfacht dargestellt bedeutet das, dass die Wahrscheinlichkeit, dass Daten nach einem erfolgten Zugriff erneut benötigt werden, um so größer ist, je kürzer der letzte Zugriff auf diese Daten zurückliegt.

Wörtlich aus dem Englischen übersetzt bedeutet Cache (gesprochen wie das Bargeld cash , entlehnt vom französischen cacher - verbergen) „geheimes Lager". Der Name verdeutlicht den Umstand, dass ein Cache seine Arbeit zumeist im Verborgenen verrichtet. Für den Programmierer ist er weitgehend transparent. Seine Existenz tritt nur bei performance-relevanten Optimierungen oder bei selten nötigen Operationen wie etwa dem Cache-Flush in Erscheinung.

Ein Cache ist „heiß", wenn er optimal arbeitet und „kalt", wenn er dies nicht tut. Ein Cache ist nach Inbetriebnahme zunächst kalt, da er noch keine Daten enthält und häufig zeitraubend Daten nachladen muss und wärmt sich dann zunehmend auf, da die zwischengelagerten Daten immer mehr den angeforderten entsprechen und kein Nachladen mehr erforderlich ist. Im Idealzustand werden Datenzugriffe fast ausschließlich aus dem Cache bedient und das Nachladen kann vernachlässigt werden.

Jeder moderne Prozessor besitzt einen oder mehrere Caches. Der Prozessor-Cache arbeitet im Gegensatz zum Hauptspeicher meist mit dem vollen Prozessortakt – mehrere Gigahertz im Vergleich zu mehreren hundert Megahertz. Das hat zur Folge, dass Daten, die sich im Prozessor-Cache befinden, in der Regel sofort (im nächsten Takt) zur Verfügung stehen und die CPU nicht erst auf den langsamen Hauptspeicher warten muss (Dies führt zum Verringern des Von-Neumann-Flaschenhals/Bottleneck der Von-Neumann-Architektur). Die Ausführungsgeschwindigkeit von Programmen kann dadurch enorm gesteigert werden.

Da der Cache viel kleiner ist als der langsamere Hauptspeicher, kann er immer nur Teile des Hauptspeichers zwischenspeichern. Zur Vereinfachung der Cache-Verwaltung wird hierzu nicht das kleinste zugreifbare Speicherelement – in der Regel das Byte – gespeichert, sondern immer gleichgroße Gruppen aufeinanderfolgender Speicherelemente, so genannte Blöcke. Bei der Verwaltung des Caches ist es sinnvoll, immer nur die Blöcke im Cache zu halten, auf die auch häufig zugegriffen wird. Zu diesem Zweck gibt es verschiedene Ersetzungsstrategien. Eine häufig verwendete Variante ist dabei die LRU-Strategie (engl. least recently used), welche immer den am längsten nicht mehr zugegriffenen Block im Cache austauscht.

Aufgrund des erwähnten kleinen Cachespeicherplatzes treten bei Lese/Schreib-Anforderungen des Prozessors folgende Fälle auf:

• Cache-Hit: Der angeforderte Block wurde im Cache gefunden und kann dort sofort bearbeitet werden. Dies bedeutet einen erheblichen Performancegewinn.
• Cache-Miss: Der angeforderte Block ist nicht im Cache. Der Block muss somit aus dem Hauptspeicher geladen werden und wird gegen einen anderen im Cache ersetzt. Dies bedeutet, dass der Prozessor während der Nachlade- und Ersetzungsphase schlimmstenfalls angehalten werden muss (Stall -> Performanceverlust). Es werden 3 Arten von Cache-Misses unterschieden:
  • Compulsory: Der erste Schreib/Lesezugriff auf einen Block ist aus Prinzip ein Miss.
  • Capacity: Der Cache ist voll (Ersetzung eines Blockes notwendig oder größerer Cache)
  • Conflict: Abhängig vom gewählten Ersetzungsverfahren, kann es passieren, dass die Stelle, an der ein Block eingelagert werden soll, bereits belegt ist.

Problem: Eine Änderung auf dem Cache führt zwangsläufig zu einer Inkonsistenz, da diese Änderung nicht mehr mit dem Block im Hauptspeicher übereinstimmt. Zur Lösung existieren 2 Techniken:

• Write Through: Wird ein Cacheelement geändert wird auch gleichzeitig sein Pendant im Hauptspeicher geändert. (Nachteil: Verlust des Geschwindigkeitsvorteil des Caches bei Schreibvorgängen, da ja immer auf den Hauptspeicher gewartet werden muss)
• Write Back: Der geänderte Cache-Block wird erst im Hauptspeicher aktualisiert, wenn er ersetzt wird. (Nachteil: Inkonsistenzprobleme bei Mehrprozessorsystemen / Abhilfe schaffen hier Cache-Kohärenz-Protokolle, wie z.B. MESI für UMA-Systeme)

In modernen Prozessoren sind aufgrund beider Nachteile beide Varianten implementiert.

Write-Miss Problem: Ist ein Block im Cache schon ersetzt worden, auf die der Prozessor jetzt schreibend zugreifen will, hat er 2 Möglichkeiten:

• Fetch on Write: Der Block wird einfach vorher nochmal in den Cache eingelesen, damit der Prozessor darauf wieder schreibend zugreifen kann.
• Write Around: Der Block wird unter Umgehung des Caches direkt im Hauptspeicher geändert.

Es existieren 3 Verfahren um Daten im Cache abzulegen:

• direkt abgebildet (direct mapped): Ein eingelagerter Block kann sich nur an einer Stelle befinden (Abbildung auf genau eine Speicherzelle). Die Adressberechnung erfolgt dabei über eine einfache Modulo-Funktion.
• vollassoziativ (fully associative): Hier kann sich ein Block an jeder beliebigen Stelle befinden. Der Block ist somit inhaltsadressierbar.
• satzassoziativ oder mengenassoziativ (set associative): Der Cachespeicher wird hierbei in mehrere Sets aufgeteilt. Diese Sets haben feste Plätze im Cache. Ein neuer Block kann nun innerhalb eines Sets beliebig platziert werden. Mengen-assoziative Caches vereinen somit Direct-Mapped- mit der voll-assoziativen Technik:
  • einfach satzassoziativ = direkt abgebildet
  • n-fach satzassoziativ (bei n Blöcken) = vollassoziativ

Heutige Caches implementieren das mengenassoziative Verfahren.

Jeder Eintrag im Cache besteht aus:

• Valid-Bit
• Tag-Field
• Data-Field

• FIFO (First In First Out): Der jeweils älteste Eintrag wird verdrängt.
• LRU (Least Recently Used): Der Eintrag, auf den am längsten nicht zugegriffen wurde, wird verdrängt.
• LFU (Least Frequently Used): Der am wenigsten gelesene Eintrag wird verdrängt. Dabei werden jedoch keineswegs vollständige Zeitstempel gespeichert, die eine relativ lange Integer-Zahl erfordern würden. Vielmehr werden wenige Bits (zwei sind häufig, aber auch nur eines ist möglich), um einen Cache-Eintrag als mehr oder weniger häufig benutzt zu markieren. Die Aktualisierung der Bits erfolgt parallel zu einer Verdrängung.
• Random: Ein zufälliger Eintrag wird verdrängt.
• CLOCK: Wenn auf ein Datum zugegriffen wird, wird ein Bit gesetzt. Die Daten werden in der Reihenfolge des Zugriffs abgelegt. Bei einem Miss wird in dieser Reihenfolge nach einem Datum ohne gesetztes Bit gesucht, das wird ersetzt. Bei allen dabei gesehen Daten wird das Bit gelöscht. Es wird ebenfalls markiert welches Datum zuletzt in den Cache geladen wurde. Von da beginnt die Suche nach einem Datum was ersetzt werden kann.
• Optimal: Das Verfahren von Belady, bei dem der Speicherbereich verdrängt wird, auf den am längsten nicht zugegriffen werden wird, ist optimal. Es ist allerdings nur dann anwendbar, wenn der komplette Programmablauf im voraus bekannt ist (d. h. er ist ein sogenanntes Offline-Verfahren im Gegensatz zu FIFO und LRU, die Online-Verfahren sind). Der Programmablauf ist aber fast nie im voraus bekannt. Deshalb wird das optimale Verfahren in der Praxis nicht eingesetzt. Allerdings kann der optimale Algorithmus als Vergleich für andere Verfahren dienen.

Ein Cache-Flush bewirkt das komplette Zurückschreiben des Cache-Inhaltes in den Hauptspeicher. Dabei bleibt der Cache-Inhalt meist unangetastet. Ein solches Vorgehen ist nötig, wenn man die Cache-Hauptspeicher-Konsistenz wiederherstellen möchte.

Notwendig ist das immer dann, wenn die Daten von externer Hardware benötigt werden. Beispiele: Multiprozessor-Kommunikation; Übergabe eines als Ausgabe-Puffer benutzten Teils des Hauptspeichers an den DMA-Controllers; Hardware-Register. Wobei letztere normalerweise gar nicht als „cache-bar" eingestuft werden, d.h. bei ihrem Zugriff wird der Cache umgangen.

Der Level-1-Cache hält die aktuellen Adressen, Befehle und Zwischenergebnisse auf Vorrat, damit diese nicht langwierig aus „entfernterem" Speicher aufgerufen werden müssen. Dieser Cache liegt stets direkt im Prozessorkern und hat in der Regel eine Größe von 8 bis 256 KiB.

Der Level-2-Cache puffert größere aktuell zu verarbeitende Datenbestände, auch unter Umständen ganze Programmabschnitte. In der günstigsten Anordnung liegt dieser Cache wie der Level-1-Cache auf dem Prozessorchip (on-Die) und wird mit der vollen Prozessortaktrate angesprochen. Liegt der L2-Cache außerhalb der CPU, also z.B. auf einer „entfernteren" Platine, so muss die Taktrate in der Regel halbiert werden. Der L2-Cache ist in der Regel zwischen 256 und 2048 KiB groß.

Insbesondere wenn der L2-Cache on-Die vorliegt, kann eine weitere Stufe, der Level-3-Cache noch einmal eine Beschleunigung des Speicherzugriffs bedeuten.

Stufung des Datenzugriffs im Computer von „schnell" nach „langsam":

1. die Daten liegen in einem Register des Prozessors

2. die Daten liegen im Level-1-Cache des Prozessors

3. die Daten liegen im Level-2-Cache

a) auf dem Prozessorchip

b) nicht auf dem Prozessorchip, auf einer „entfernteren" Platine

4. die Daten liegen im Level-3-Cache (nicht auf dem Prozessorchip)

5. die Daten müssen aus dem regulären Arbeitsspeicher gelesen werden

6. die Daten müssen extern gelesen werden (von z.B. der Festplatte)

a) die Daten liegen in einem Laufwerks-Cache (Speicher in der Ansteuerungselektonik (Controller oder im Laufwerksgehäuse))

b) die Daten werden magnetisch/optisch gelesen

7. die Daten müssen noch (z.B. per Scanner oder Tastatur) eingegeben werden.

Moderne Festplatten besitzen ebenfalls einen eigenen eingebauten Cache (meist 1-16, mittlerweile auch 32 MiB groß). Er sorgt hier für enorm reduzierte Anfragezeiten bei Cache-Hits (wenige Nanosekunden im Vergleich zu einigen Millisekunden). Siehe dazu Festplattencache.

Selbst heutige Speicher (SDRAM, DDR-SDRAM, RDRAM, ...) besitzen selber noch einmal einen schnelleren Cache. Der Grund ist, dass der Hauptspeicher fast aller PCs mit dynamischem Speicher bestückt ist, welcher zwar billiger, aber aufgrund seiner Refresh-Zyklen auch langsamer ist. Deshalb besitzt jeder RAM-Baustein einen kleinen Cache in Form eines statischen Speichers.

Das Wort "Cache" trifft man auch in der Software an. Hier beschreibt es dasselbe Prinzip wie bei der Hardwareimplementierung: Daten werden für einen schnelleren Zugriff auf ein schnelleres Medium zwischengespeichert.

Beispiele:

• Browser-Cache: (Netz -> Festplatte)
• Anwendungen: (Festplatte -> Hauptspeicher)

• Speicherhierarchie

• Artikel über Cache bei arstechnica.com (englisch)
• Cache leeren in verschiedenen Browsern

• Rechnerarchitektur