Cache

Cache bezeichnet in der EDV eine Methode, um Inhalte, die bereits einmal vorlagen, beim nächsten Zugriff schneller zur Verfügung zu stellen. Caches sind als Puffer (Informatik)Puffer-Datenspeicher|Speicher realisiert, die Kopien zwischenspeichern. Sie können als Hardware- oder Softwarestruktur ausgebildet sein.

Gründe für den Einsatz eines Caches sind ein (relativ gesehen) langsamer Zugriff auf ein Hintergrundmedium oder ein relativ hoher Aufwand, oft benötigte Daten neu zu generieren.

Wörtlich aus dem Englischen übersetzt bedeutet Cache (gesprochen käsch, entlehnt vom französischen Andrew S. Tanenbaum, James Goodman: Computerarchitektur. 4. Auflage. Pearson Studium, München 2001, ISBN 3-8273-7016-7 (deutsch), S. 92. geheimes Lager. Der Name verdeutlicht den Umstand, dass ein Cache seine Arbeit zumeist im Verborgenen verrichtet. Ein Programmierer muss dessen Größe oder Funktionsweise prinzipiell also nicht kennen, denn der Cache ist als solches abstrakt und wird nicht direkt angesprochen. Praktisch ist er eine gespiegelte Ressource, die stellvertretend für das Original bearbeitet werden kann. Damit alle Geräte auf ein identisches Speicherabbild zugreifen können, ist es notwendig, die Änderungen des Caches in den Hauptspeicher zu übernehmen. Cachestrategien wie Write-Through oder Write-Back sind hier praktikabel. Im Extremfall muss ein kompletter „Cache Flush“ erfolgen.

Nutzen

Die Ziele beim Einsatz eines Caches sind eine Verringerung der Zugriffszeit bzw. eine Verringerung der Anzahl der Zugriffe auf den zu cachenden Speicher. Das bedeutet insbesondere, dass sich der Einsatz von Caches nur dort lohnt, wo die Zugriffszeit auch signifikanten Einfluss auf die Gesamtleistung hat. Während das bei den meisten (skalaren) Mikroprozessoren der Fall ist, trifft das beispielsweise nicht auf Vektorrechner zu, wo die Zugriffszeit keine sehr wichtige Rolle spielt. Deswegen wird dort üblicherweise auch auf Caches verzichtet, weil diese keinen oder nur wenig Nutzen bringen.

Ein weiterer wichtiger Effekt beim Einsatz von Caches ist die verringerte Datenübertragungsrate|Bandbreitenanforderung an die nächsthöhere Speicherebene der Speicherhierarchie. Weil oftmals der Großteil der Anfragen vom Cache beantwortet werden kann („Cache Hit“, s. u.), sinkt die Anzahl der Zugriffe und damit die Bandbreitenanforderung an den zu cachenden Speicher. Ein moderner Mikroprozessor ohne Cache würde selbst mit unendlich kleiner Zugriffszeit des Hauptspeichers dadurch ausgebremst, dass nicht genügend Speicherbandbreite zur Verfügung steht, weil durch den Wegfall des Caches die Anzahl der Zugriffe auf den Hauptspeicher und damit die Anforderung an die Speicherbandbreite stark zunehmen würde. Ein Cache kann daher also auch genutzt werden, um die Bandbreitenanforderungen an den zu cachenden Speicher zu reduzieren, was sich z. B. in geringeren Kosten für diesen niederschlagen kann.

Bei CPUs kann der Einsatz von Caches somit zum Verringern des Von-Neumann-Flaschenhalses der Von-Neumann-Architektur beitragen. Die Ausführungsgeschwindigkeit von Programmen kann dadurch im Mittel enorm gesteigert werden.

Ein Nachteil von Caches ist das schlecht vorhersagbare Echtzeitverhalten, da die Ausführungszeit eines Befehls aufgrund von Cache Misses nicht immer konstant ist.

Cachehierarchie

Da es technisch nicht oder nur sehr schwer möglich ist, einen Cache zu bauen, der gleichzeitig sowohl groß als auch schnell ist, kann man mehrere Caches verwenden – z. B. einen kleinen schnellen und einen großen langsameren Cache (der aber immer noch Größenordnungen schneller ist als der zu cachende Speicher). Damit kann man die konkurrierenden Ziele von geringer Zugriffszeit und Cachegröße (wichtig für Cache Hits und Misses gemeinsam realisieren.

Existieren mehrere Caches, so bilden diese eine Cachehierarchie, die Teil der Speicherhierarchie ist. Die einzelnen Caches werden nach ihrer Hierarchieebene (engl. level) durchnummeriert, also Level-1 bis Level-n oder kurz L1, L2 usw. Je niedriger die Nummer, desto hardwarenäher ist der Cache; die niedrigste Nummer bezeichnet daher den Cache mit der kleinsten Zugriffszeit, dieser wird also als erstes durchsucht. Enthält der L1-Cache die benötigten Daten nicht, wird der (meist etwas langsamere, aber größere) L2-Cache durchsucht usw. Das geschieht solange, bis die Daten entweder in einer Cacheebene gefunden (ein „Cache Hit“, s. u.) oder alle Caches ohne Erfolg durchsucht wurden (ein „Cache Miss“, s. u.). In letzterem Fall muss auf den verhältnismäßig langsamen Speicher zugegriffen werden.

Im Hardwarebereich weisen vor allem moderne CPUs zwei oder drei Cacheebenen auf; sonstige Geräte besitzen aber meist nur eine Cacheebene. Im Softwarebereich wird meist nur eine Cacheebene benutzt, eine prominente Ausnahme bilden aber Webbrowser, die zwei Ebenen nutzen (Arbeitsspeicher und Festplatte).

Cachegröße

Um den Nutzen des meist mehrere Größenordnungen kleineren Caches im Vergleich zum Hintergrundspeicher zu maximieren, werden bei der Funktionsweise und Organisation eines Caches die Lokalitätseigenschaften der Zugriffsmuster ausgenutzt. Beobachtet man beispielsweise die Aktivität eines laufenden Programms auf einem Prozessor über ein kurzes Zeitintervall, so stellt man fest, dass wiederholt auf wenige kleine Speicherbereiche (z. B. Code innerhalb Schleifen, Steuervariablen, lokale Variablen und Prozedurparameter) zugegriffen wird. Darum können bereits kleine Caches mit einigen Kilobytes sehr wirksam sein.

Prozessor-Cache

Bei CPUs kann der Cache direkt im Prozessor integriert oder extern auf der Hauptplatine platziert sein. Je nach Ort des Caches arbeitet dieser mit unterschiedlichen Taktfrequenzen: Der L1 ist fast immer direkt im Prozessor integriert und arbeitet daher mit dem vollen Taktsignal|Prozessortakt – also u. U. mehrere Gigahertz. Ein externer Cache hingegen wird oftmals nur mit einigen hundert Megahertz getaktet.

Gängige Größen für L1-Caches sind 4 bis 256  Byte/KiB und für den L2-Cache 64 KiB bis 12 MiB.

Moderne Prozessoren haben getrennte L1-Caches für Programme und Daten (Lese- und Schreibcache), teilweise ist das auch noch beim L2 der Fall (Itanium 2|Montecito). Man spricht hier von einer Harvard-Cachearchitektur. Das hat den Vorteil, dass man für die unterschiedlichen Zugriffsmuster für das Laden von Programmcode und Daten unterschiedliche Cachedesigns verbauen kann. Außerdem kann man bei getrennten Caches diese räumlich besser zu den jeweiligen Einheiten auf dem Prozessor-Die (Halbleitertechnik)|Die platzieren und damit die kritischen Pfade beim Prozessorlayout verkürzen. Des Weiteren können Instruktionen und Daten gleichzeitig gelesen/geschrieben werden, wodurch der Von-Neumann-Architektur#von-Neumann-Flaschenhals|Von-Neumann-Flaschenhals weiter verringert werden kann. Ein Nachteil ist, dass selbstmodifizierender Code nicht sehr gut auf modernen Prozessoren läuft. Allerdings wird diese Technik heute ohnehin nur noch sehr selten verwendet.

Laufwerks-Cache

Bei Festplatten befindet sich der Cache auf der Steuerplatine (siehe Festplattencache).

Auch die meisten Laufwerke für Optischer Speicher/optische Speicher besitzen Caches, um die oftmals im dreistelligen Millisekundenbereich liegenden Zugriffszeiten aufzufangen.

Lokalitätsausnutzung

Da Caches schnell sein sollen, verwendet man für sie meist eine andere (schnellere) Speichertechnologie als für den zu cachenden Speicher (zum Beispiel Static Random Access Memory|SRAM gegenüber Dynamic random access memory|DRAM, DRAM gegenüber Magnetscheibe etc.). Daher sind Caches meist wesentlich teurer in Bezug auf das Preis-Bit-Verhältnis, weswegen Caches deutlich kleiner ausgelegt werden. Das führt dazu, dass ein Cache nicht alle Daten gleichzeitig vorrätig haben kann. Um das Problem zu lösen, welche Daten denn nun im Cache gehalten werden sollen, werden Lokalitätseigenschaften der Zugriffe ausgenutzt:

• zeitliche (temporale) Lokalität: Da sich Zugriffe auf Daten wiederholen (z. B. beim Abarbeiten einer Programmschleife), ist es eher wahrscheinlich, dass auf Daten, auf die schon einmal zugegriffen wurde, auch noch ein weiteres Mal zugegriffen wird. Diese Daten sollten also bevorzugt im Cache gehalten werden. Dadurch ergibt sich auch eine Notwendigkeit, alte Daten, die lange nicht benutzt wurden, aus dem Cache zu entfernen, um Platz für neuere zu machen. Diesen Vorgang nennt man auch „Verdrängung“.
• räumliche (spatiale) Lokalität: Da Programmcode und -daten nicht wild verstreut im Adressraum herumliegen, sondern „hintereinander“ und teilweise auch nur in bestimmten Adressbereichen angeordnet sind (Code-, Daten-, Stapelspeicher|Stack-Segment, Dynamischer Speicher|Heap etc.), ist es bei einem stattgefundenen Zugriff auf eine bestimmte Adresse wahrscheinlich, dass auch auf eine „naheliegende“ Adresse (sprich: Betrag der Differenz der beiden Adressen sehr klein) zugegriffen wird. Bei der Abarbeitung eines Programms wird z. B. ein Befehl nach dem anderen abgearbeitet, wobei diese „nacheinander“ im Speicher liegen (wenn es kein Sprung ist). Viele Datenstrukturen wie Arrays liegen ebenfalls „hintereinander“ im Speicher.

Die räumliche Lokalität ist der Grund, warum man bei Caches nicht einzelne Bytes, sondern die Daten ganzer Adressbereiche („Cacheblock“ oder manchmal auch „Cache-Line“ genannt) speichert. Zusätzlich erleichtert das die Implementierung und verringert Speicher Overhead (EDV)|overhead, da man nicht für jedes Datenbyte dessen Adresse im Speicher festhalten muss, sondern nur für jeden Cacheblock (der aus vielen Bytes besteht). Die Wahl der Blockgröße ist ein wichtiger Designparameter für einen Cache, der die Leistung stark beeinflussen kann, positiv wie auch negativ.

Organisation

Je nachdem, wie stark man diese Aufteilung vornimmt, spricht man von einer der drei Cacheorganisationsarten:

• direkt abgebildet (engl. direct mapped, kurz DM): [math]\displaystyle{ n=1 }[/math], d. h. jeder Block repräsentiert einen eigenen Satz, es gibt also so viele Sätze wie Blöcke. Somit ist für eine gegebene Adresse exakt ein Cacheblock zuständig. Es existiert also eine direkte Funktion (Mathematik)|Abbildung zwischen Hintergrundspeicheradresse und Cacheblöcken, daher der Name. Bei einer Anfrage an einen solchen Cache muss man nur einen einzelnen Cacheblock auslesen (genauer gesagt den zugehörigen Tag überprüfen, s. u.), was den Hardwareaufwand für die Tag-Vergleicher minimiert. Im Gegenzug ist die Effizienz des Caches eingeschränkt, da möglicherweise freie Cacheblöcke vorhanden sind, die nicht genutzt werden, siehe Conflict Miss unten.
• vollassoziativ (engl. fully associative, kurz FA): [math]\displaystyle{ n=m }[/math], d. h. es gibt nur einen Satz, der alle Blöcke beinhaltet. Somit kann jede Adresse in jedem Cacheblock gecachet werden. Bei einer Anfrage an den Cache ist es daher notwendig, alle Cache-Tags zu überprüfen. Da Caches möglichst schnell sein müssen, wird das parallel ausgeführt, was den notwendigen Hardwareaufwand an Tag-Vergleichern vergrößert. Der Vorteil ist aber, dass der Cache stets Daten aufnehmen kann, solange noch ein beliebiger Cacheblock frei ist.
• satzassoziativ bzw. mengenassoziativ (engl. set associative, kurz SA): [math]\displaystyle{ n }[/math] wird zwischen 2 und 64 gewählt, d. h. die Cacheblöcke sind in Sätzen zu je [math]\displaystyle{ n }[/math] Blöcken angeordnet. Hier werden also [math]\displaystyle{ \frac{m}{n} }[/math] direkt abgebildete Caches vollassoziativ (also frei) angewählt. Diesen Cache nennt man dann n-fach satzassoziativ oder kurz n-fach assoziativ. Diese Cacheform stellt einen Kompromiss aus Hardwareaufwand und Effizienz des Caches dar: Gegenüber einem DM-Cache gewinnt man Effizienz, gegenüber einem FA-Cache spart man Hardware.

Die ersten beiden sind ein Spezialfall des satzassoziativen Caches. Der direkt abgebildete und der vollassoziative Cache lassen sich somit vom satzassoziativen Cache ableiten: n=1 führt zu einem direkt abgebildeten Cache, n=m zu einem vollassoziativen Cache.

Cache Hits und Misses

Den Vorgang, dass die Daten einer Anfrage an einen Cache in selbigem vorrätig sind, bezeichnet man als „Cache Hit“ (dt. Cachetreffer), den umgekehrten Fall als „Cache Miss“ (dt. „Cache-Verfehlen“).

Um quantitative Maßzahlen für die Bewertung der Effizienz eines Caches zu erhalten, definiert man zwei Größen:

• Hit Rate: Die Anzahl der Anfragen, bei denen ein Cache Hit auftrat geteilt durch die Anzahl der insgesamt an diesen Cache gestellten Anfragen. Wie man aus der Definition leicht sehen kann, liegt diese Größe zwischen Null und Eins. Eine Hit Rate von z. B. 0,7 (oder auch 70 %) bedeutet, dass bei 70 % aller Anfragen an den Cache dieser die Daten sofort liefern konnte und bei 30 % aller Anfragen passen musste.
• Miss Rate: Diese ist analog zur Hit Rate als die Anzahl der Anfragen definiert, bei denen die Daten nicht im Cache vorhanden waren geteilt durch die Anzahl der gesamten Anfragen. Es gilt: Miss Rate = 1 − Hit Rate.

Dabei werden drei Arten von Cache Misses unterschieden:

• Capacity: Der Cache ist zu klein. Daten waren im Cache vorrätig, wurden aber wieder aus dem Cache entfernt. Erfolgt dann ein erneuter Zugriff auf diese Adresse, so wird dieser Miss als „Capacity Miss“ bezeichnet. Abhilfe schafft nur ein größerer Cache.
• Conflict: Durch die satzassoziative Organisation (gilt somit auch für DM-Caches) ist es möglich, dass in einem Satz nicht mehr genug Platz ist, während in anderen Sätzen noch freie Cacheblocks vorhanden sind. Dann muss in dem überfüllten Satz ein Block entfernt werden, obwohl der Cache eigentlich noch Platz hat. Wird auf diesen entfernten Block erneut zugegriffen, so bezeichnet man diesen Cache Miss als „Conflict Miss“. Abhilfe schafft eine Erhöhung der Cacheblocks pro Satz – also eine Erhöhung der Assoziativität. Bei vollassoziativen Caches (welche nur einen Satz haben) gibt es prinzipbedingt keine Conflict Misses.
• Compulsory: Beim erstmaligen Zugriff auf eine Adresse befinden sich normalerweise die dazugehörigen Daten noch nicht im Cache. Diesen Miss bezeichnet man als „Compulsory Miss“. Er ist nicht oder nur schwer zu verhindern. Moderne Prozessoren besitzen hiergegen „Prefetching|Prefetcher“-Einheiten, die selbstständig spekulativ Daten in die Caches laden, wenn dort noch Platz ist. Damit soll die Anzahl der Compulsory Misses verringert werden.

Diese drei Typen bezeichnet man auch kurz als „Die drei C“. In Multiprozessorsystemen kann beim Einsatz eines Cache-Kohärenz-Protokolls vom Typ Write-Invalidate-Protokoll|Write-Invalidate noch ein viertes „C“ hinzukommen, nämlich ein „Coherency Miss“: Wenn durch das Schreiben eines Prozessors in einen Cacheblock der gleiche Block im Cache eines zweiten Prozessors hinausgeworfen werden muss, so führt der Zugriff des zweiten Prozessors auf eine Adresse, die durch diesen entfernten Cacheblock abgedeckt war, zu einem Coherency Miss.

Arbeitsweise

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 Least recently used|LRU-Strategie (engl. least recently used), welche immer den am längsten nicht mehr zugegriffenen Block im Cache austauscht. Moderne Prozessoren (AMD Athlon u. v. m.) implementieren meist eine Pseudo-LRU-Ersetzungsstrategie, die also fast wie echtes LRU arbeitet, aber leichter in Hardware zu implementieren ist.

Weblinks

• Artikel über CPU-Cache bei arstechnica.com (englisch)
• Cache leeren in verschiedenen Browsern
• Cache und Hauptspeicher Online Seminar
• Kurzüberblick Cache im Elektronik-Kompendium