Cache

ï»ż
Cache

Cache [kĂŠÊƒ] bezeichnet in der EDV einen schnellen Puffer-Speicher, der Zugriffe auf ein langsames Hintergrundmedium oder zeitaufwendige Neuberechnungen nach Möglichkeit vermeidet. Meist werden hierzu

  • Inhalte/Daten gepuffert, die bereits einmal verwendet/berechnet wurden, um beim nĂ€chsten Zugriff schneller zur VerfĂŒgung zu stehen, oder
  • vermutlich bald benötigte Daten vorab vom langsamen Hintergrundmedium geladen und bereitgestellt.

Caches sind als Puffer-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 (entlehnt vom französischen cacher – verbergen[1]) geheimes Lager. Der Name verdeutlicht den Umstand, dass ein Cache seine Arbeit zumeist „transparent“ verrichtet. Wer das Hintergrundmedium verwendet, muss GrĂ¶ĂŸe oder Funktionsweise des Caches prinzipiell also nicht kennen, denn der Cache wird nicht direkt angesprochen. Der Verwender „spricht das Hintergrundmedium an“, und es „antwortet“ stattdessen der Cache - aber genau auf die Art und Weise, wie auch das Hintergrundmedium geantwortet (Daten geliefert) hĂ€tte. Praktisch ist er eine gespiegelte Ressource, die stellvertretend fĂŒr das Original sehr schnell bearbeitet/verwendet wird.

Greifen außer dem Cache-verwendenden GerĂ€t noch weitere auf das Hintergrundmedium zu, so könnte es zu InkohĂ€renzen kommen – um auf ein identisches Datenabbild zugreifen zu können, ist es notwendig, zuvor die Änderungen des Caches in das Hintergrundmedium zu ĂŒbernehmen. Cachestrategien wie Write-Through oder Write-Back sind hier praktikabel. Im Extremfall muss ein kompletter „Cache Flush“ erfolgen. Außerdem muss ggf. der Cache informiert werden, dass sich Daten auf dem Hintergrundmedium geĂ€ndert haben und sein Inhalt nicht mehr gĂŒltig ist.

Inhaltsverzeichnis

Nutzen

Die Ziele beim Einsatz eines Caches sind eine Verringerung der Zugriffszeit und/oder eine Verringerung der Anzahl der Zugriffe auf das langsame Hintergrundmedium. 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 z. B. beim Prozessorcache der meisten (skalaren) Mikroprozessoren der Fall ist, trifft das 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 Bandbreitenanforderung an die Anbindung des Hintergrundmediums (siehe z. B. 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 das Hintergrundmedium. Zum Beispiel wĂŒrde ein moderner Mikroprozessor ohne Cache 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 das Hintergrundmedium zu reduzieren, was sich z. B. in geringeren Kosten fĂŒr dieses 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 Zeitverhalten, da die AusfĂŒhrungszeit eines Zugriffs aufgrund von Cache Misses nicht immer konstant ist; sind die Daten nicht im Cache, muss der Zugreifende warten, bis sie aus dem langsamen Hintergrundmedium geladen wurden. Bei Prozessoren geschieht dies oft bei Zugriffen auf bisher noch nicht verwendete Daten oder beim Laden des nĂ€chsten Programmbefehls bei (weiten) SprĂŒngen.

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 deutlich grĂ¶ĂŸeren, jedoch etwas langsameren Cache (der aber immer noch viel schneller ist als der zu cachende Hintergrundspeicher). Damit kann man die konkurrierenden Ziele von geringer Zugriffszeit und großem Cacheumfang (wichtig fĂŒr Hit Rate) 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 nĂ€her liegt der Cache am schnellen „Benutzer“; die niedrigste Nummer bezeichnet daher den Cache mit der schnellsten 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 langsamen Hintergrundspeicher zugegriffen werden.

Tritt ein Cache Hit z. B. im L3-Cache auf, so werden die angeforderten Daten dem Zugreifer geliefert und zugleich in den L1-Cache ĂŒbernommen; dafĂŒr muss dort eine Cache-Line weichen, die in den L2-Cache "absinkt".

  • Bei einem inklusiven Cache ist jeder Cache-Level fĂŒr sich transparent, d. h. eine Cache-Line, die im L1-Cache ist, ist auch im L2- und L3-Cache vorhanden. Wird die Cache-Line aus dem L1-Cache „verdrĂ€ngt“ (ĂŒberschrieben mit Daten einer anderen Adresse), so muss sonst nichts unternommen werden - sie ist im L2-Cache ja immer noch vorhanden (sofern kein Write-Back o.Ă€. notwendig ist).
  • Bei einem exklusiven Cache ist eine Cache-Line einer Adresse nur einmal in allen Cache-Leveln vorhanden. Eine Cache-Line zu Adresse A im L1-Cache ist nicht zusĂ€tzlich im L2- oder L3-Cache vorhanden. Wird sie aus dem L1-Cache verdrĂ€ngt, so kann sie entweder gĂ€nzlich verworfen werden, oder muss explizit in den L2-Cache kopiert werden. Dort wird somit ebenfalls eine (andere) Cache-Line verdrĂ€ngt, um Platz zu machen fĂŒr die absinkende. Diese andere sinkt nun ihrerseits in den L3-Cache, wo somit eine dritte Cache-Line weichen muss.

Exklusive Cache-Hierarchien erzeugen deutlich mehr Datenverkehr zwischen den Caches. DafĂŒr können so viele Cache-Lines bereitgehalten werden wie die Summe von L1-, L2- und L3-Cache-GrĂ¶ĂŸe, wĂ€hrend beim inklusiven Cache nur die L3-Cache-GrĂ¶ĂŸe maßgebend ist.

Im Hardwarebereich weisen vor allem moderne CPUs zwei oder drei Cacheebenen auf; sonstige GerÀte besitzen 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).

Grundlagen der Nutzbringung

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 „immer die selben“ 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 und nĂŒtzlich sein.

Verarbeitet ein Algorithmus jedoch stĂ€ndig neue Daten (z. B. Streaming-Daten), kann ein Cache keine Beschleunigung durch Mehrfach-Zugriffe bewirken, allenfalls geringfĂŒgig durch read-ahead.

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 SRAM gegenĂŒber 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-, Stack-Segment, 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 Speicheroverhead, 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

Ein Cache besteht aus einer (meist) festen Anzahl EintrÀgen, jeder Eintrag besteht aus:

  • Cache-Line: Die eigentlichen gecacheten Daten (z. B. bei Festplatten 1 Block = 512 Bytes)
  • Adress-Tag: Die Adresse auf dem Hintergrundmedium, wo die gecacheten Daten beginnen
  • Zugriffs-/Verwaltungsinformationen: v. a. Angaben bzgl. der „VerdrĂ€ngungsstrategie“ (s. u.)

(Siehe auch unten bei „EintrĂ€ge im Cache“.)

Blocknummer-Tags statt Adress-Tags

Es wird im Nachfolgenden davon ausgegangen, dass Cache-Lines immer nur von Adressen gelesen und geschrieben werden, deren Adresse durch die (Byte-)LĂ€nge der Cache-Line teilbar ist.

Beispiel:

Eine Cache-Line sei 512 Bytes groß. Dann sei festgelegt, dass Daten nur gelesen/geschrieben werden können mit Startadressen z. B. 0, 512, 1024, 1536, 2048, ... Das Hintertergrundmedium ist also aufgeteilt in Blöcke, die gerade so groß sind wie eine Cache-Line.

Dann muss in den Adress-Tags nicht mehr die gesamte (Start-)Adresse der Daten gespeichert werden, sondern nur noch, der wievielte Datenblock auf dem Hintergrundmedium gecachet ist. Durch die Wahl passender Zahlen (Zweierpotenzen) im BinĂ€rsystem lassen sich so die Tags kĂŒrzer wĂ€hlen; das beschleunigt das PrĂŒfen, ob eine angefragte Adresse im Cache enthalten ist. Außerdem spart es Platz, wenn die Tags kĂŒrzer sind.

Block/Satz-Aufteilung der Tags

Vollassoziativer Cache

Die Blöcke eines Caches können in so genannte SĂ€tze aufgeteilt werden. FĂŒr eine gegebene Adresse ist immer ein ganzer Satz zustĂ€ndig, innerhalb eines Satzes bedienen alle Blöcke also gemeinsam dieselben Adressen. Im Folgenden stehe die Variable m fĂŒr die Gesamtanzahl der Cacheblöcke und n fĂŒr die Anzahl der Blöcke pro Satz, die so genannte AssoziativitĂ€t. Dann besteht der Cache also aus \frac{m}{n} SĂ€tzen.

Organisation Anzahl der SÀtze AssoziativitÀt
DM m 1
FA 1 m ( = n)
SA \frac{m}{n} n

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

  • direkt abgebildet (engl. direct mapped, kurz DM): n = 1, 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 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): n = m, 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): n wird zwischen 2 und 64 gewĂ€hlt, d. h. die Cacheblöcke sind in SĂ€tzen zu je n Blöcken angeordnet. Hier werden also \frac{m}{n} 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.

Alternative ErklÀrung anhand eines Beispiels

Ein Cache habe 256 EintrĂ€ge Ă  1 Byte, der Adressraum (GrĂ¶ĂŸe des Hintergrundmediums) sei 2^16 = 65536 Bytes. Das Adress-Tag jedes Eintrags muss hier 16 Bit lang sein, da (wegen der Cache-Line-GrĂ¶ĂŸe 1) keine VerkĂŒrzung aufgrund Blocknummer-Tags besteht. Um zu prĂŒfen, ob eine Adresse bereits im Cache vorliegt, muss also ein 16-Bit-Vergleich vorgenommen werden.

  • vollassoziative Organisation: Jeder Eintrag (alle 256) kann jede beliebige Hintergrundadresse cachen. Um möglichst schnell herauszufinden, ob eine Adresse im Cache ist, werden 256 Vergleicher benötigt, die alle gleichzeitig befragt werden, ob die angefragte Adresse mit „ihrem“ Eintrags-Tag ĂŒbereinstimmt.
  • 128-fach assoziativ: Die 256 EintrĂ€ge werden unterteilt in zwei Gruppen (2 „SĂ€tze“): Die erste Gruppe (zu 128 EintrĂ€gen) kĂŒmmert sich um alle geradzahligen Adressen, die zweite Gruppe (die restlichen 128 Cache-EintrĂ€ge) kĂŒmmert sich um die ungeradzahligen Adressen. Dadurch kann schon vor der eigentlichen PrĂŒfung entschieden werden, welcher Satz (gerade oder ungerade) fĂŒr die angefragte Adresse zustĂ€ndig wĂ€re, und es mĂŒssen nur noch 128 Vergleicher befragt werden. Außerdem können die Adress-Tags 1 Bit kĂŒrzer gewĂ€hlt werden, da durch die Wahl des entsprechenden Satzes ja bekannt ist, ob das letzte Bit 0 (gerade) oder 1 (ungerade) ist.
    Die Vergleicher können so angebracht werden, dass sie (umschaltbar) entweder ein „gerades“ Cache-Line-Tag mit der angefragten Adresse vergleichen, oder ein „ungerades“ Cache-Line-Tag. Damit können also (im Vergleich zu „vollassoziativ“) 128 Vergleicher eingespart werden!
  • 64-fach assoziativ: Statt 2 SĂ€tze („gerade“/„ungerade“) gibt es nun 4 SĂ€tze, so dass die SĂ€tze zustĂ€ndig sind fĂŒr Adressen:
    1. Satz: zustĂ€ndig fĂŒr alle Adressen, fĂŒr die gilt: (Adresse dividiert durch 4) ergibt Rest 0
    2. Satz: zustĂ€ndig fĂŒr alle Adressen, fĂŒr die gilt: (Adresse dividiert durch 4) ergibt Rest 1
    3. Satz: zustĂ€ndig fĂŒr alle Adressen, fĂŒr die gilt: (Adresse dividiert durch 4) ergibt Rest 2
    4. Satz: zustĂ€ndig fĂŒr alle Adressen, fĂŒr die gilt: (Adresse dividiert durch 4) ergibt Rest 3
Dadurch werden nur noch 64 Vergleicher benötigt, die Tags können um 2 Bit verkĂŒrzt werden. Nachteil: Wenn ein Programm nur jedes vierte Byte des Hintergrundmediums verwenden möchte, muss immer derselbe Satz dies cachen – die anderen 3 SĂ€tze liegen brach.
  • 32-fach assoziativ: Es wird durch 8 dividiert, Rest 0..7 fĂŒr die 8 SĂ€tze
  • 16-fach assoziativ: Es wird durch 16 dividiert, Rest 0..15 fĂŒr die 16 SĂ€tze
  • 8-fach assoziativ: Es wird durch 32 dividiert, Rest 0..31 fĂŒr die 32 SĂ€tze
  • 4-fach assoziativ: Es wird durch 64 dividiert, Rest 0..63 fĂŒr die 64 SĂ€tze
  • 2-fach assoziativ: Es wird durch 128 dividiert, Rest 0..127 fĂŒr die 128 SĂ€tze
  • direct mapped / 1-fach assoziativ: Division durch 256, der Rest (0..255) ist direkt die Cache-Line-Nummer, die zustĂ€ndig ist.

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 „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 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 LRU-Strategie (engl. least recently used), bei welcher immer der Block ausgetauscht wird, auf den am lĂ€ngsten nicht mehr zugegriffen worden ist. 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.

VerdrÀngungsstrategien

  • 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 seltensten 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 verwendet (zwei sind hĂ€ufig, aber auch nur eines ist möglich), um einen Cacheeintrag 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.
  • Climb: Bei der Climb-Strategie wird eine neue Seite stets unten im Speicher eingesetzt und steigt bei jedem Zugriff eine Ebene nach oben. Muss eine Seite ausgetauscht werden, so wird die unterste Seite ersetzt.
  • CLOCK: Daten werden im Cache in der Reihenfolge des Zugriffs abgelegt. Wenn auf ein Datum zugegriffen wird, wird fĂŒr diesen Cacheblock ein Bit gesetzt. Bei einem Miss wird von vorne nach hinten nach dem ersten Datum ohne gesetztes Bit gesucht, dieses wird ersetzt. Bei allen dabei durchgegangenen Daten wird das Bit gelöscht. Es wird ebenfalls markiert, welches Datum zuletzt in den Cache geladen wurde. Von dort beginnt die Suche nach einem Datum, welches ersetzt werden kann.
  • Optimal: Das Verfahren von Laszlo Belady, bei dem derjenige 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 so genanntes Offline-Verfahren, im Gegensatz zu FIFO und LRU, die Online-Verfahren sind). Der Programmablauf ist aber fast nie im voraus bekannt; deshalb kann das optimale Verfahren in der Praxis nicht eingesetzt werden. Allerdings kann der optimale Algorithmus als Vergleich fĂŒr andere Verfahren dienen.

Schreibstrategie

Bei einem Schreibzugriff auf einen Block, der im Cache vorhanden ist, gibt es prinzipiell zwei Möglichkeiten:

  • ZurĂŒckkopieren (write-back)
Beim Schreiben wird der zu schreibende Block nicht sofort in der nĂ€chsthöheren Speicherebene abgelegt, sondern zunĂ€chst im Cache. Dabei entsteht eine Inkonsistenz zwischen Cache und zu cachendem Speicher. Letzterer enthĂ€lt somit veraltete Information. Erst wenn das Wort aus dem Cache verdrĂ€ngt wird, wird es auch in die nĂ€chsthöhere Speicherebene geschrieben. Dazu bekommt jeder Cacheblock ein so genanntes Dirty Bit, das anzeigt, ob der Block beim Ersetzen zurĂŒckkopiert werden muss. Das fĂŒhrt bei Speicherzugriff durch andere Prozessoren oder DMA-GerĂ€te zu Problemen, weil diese veraltete Informationen lesen wĂŒrden. Abhilfe schaffen hier Cache-KohĂ€renz-Protokolle wie z. B. MESI fĂŒr UMA-Systeme.
  • DurchgĂ€ngiges Schreiben (write-through)
Der zu schreibende Block wird sofort in der nÀchsthöheren Speicherebene abgelegt. Damit ist die Konsistenz gesichert. Damit der Prozessor nicht jedes Mal warten muss bis der Block in der nÀchsthöheren Speicherebene (die ja langsamer als der Cache ist) abgelegt ist, benutzt man einen Pufferspeicher (write buffer). Wenn dieser voll lÀuft, muss der Prozessor jedoch anhalten und warten.

Analog zu Obigem gibt es bei einem Schreibzugriff auf einen Block, der nicht im Cache vorhanden ist, prinzipiell ebenso zwei Möglichkeiten:

  • write-allocate
Wie bei einem normalen Cache Miss wird der Block aus der nĂ€chsthöheren Speicherebene geholt. Die entsprechenden Bytes, die durch den Schreibzugriff geĂ€ndert wurden, werden danach im gerade frisch eingetroffenen Block ĂŒberschrieben.
  • non-write-allocate
Es wird am Cache vorbei in die nĂ€chsthöhere Speicherebene geschrieben, ohne dass der dazugehörige Block in den Cache geladen wird. Das kann fĂŒr manche Anwendungen Vorteile bringen, bei denen viele geschriebene Daten nie wieder gelesen werden. Durch die Verwendung von non-write-allocate verhindert man das VerdrĂ€ngen von anderen, möglicherweise wichtigen Blöcken und reduziert somit die Miss Rate.

Einige BefehlssÀtze enthalten Befehle, die es dem Programmierer ermöglichen, explizit anzugeben, ob zu schreibende Daten am Cache vorbeizuschreiben sind.

Normalerweise wird entweder die Kombination write-back mit write-allocate oder write-through mit non-write-allocate verwendet. Die erste Kombination hat den Vorteil, dass aufeinander folgende Schreibzugriffe auf denselben Block (LokalitĂ€tsprinzip) komplett im Cache abgewickelt werden (bis auf den ersten Miss). Dies gibt im zweiten Fall keinen Vorteil, da sowieso jeder Schreibzugriff zum Hauptspeicher muss, weshalb die Kombination write-through mit write-allocate eher unĂŒblich ist.[2]

Cache Flush

Ein Cache Flush („Pufferspeicher-Leerung“) bewirkt das komplette ZurĂŒckschreiben des Cacheinhaltes in den Hintergrundspeicher. Dabei bleibt der Cacheinhalt meist unangetastet. Ein solches Vorgehen ist nötig, um die Konsistenz zwischen Cache und Hintergrundspeicher wiederherzustellen. Notwendig ist das zum Beispiel immer dann, wenn Daten aus dem Hauptspeicher von externen GerĂ€ten benötigt werden, unter anderem bei Multiprozessor-Kommunikation oder bei der Übergabe eines als Ausgabepuffer benutzten Teils des Hauptspeichers an den DMA-Controller.

Sonstiges

EintrÀge im Cache

FĂŒr jeden Cacheblock wird im Cache folgendes gespeichert:

  • die eigentlichen Daten
  • der Tag (ein Teil der Adresse)
  • mehrere Statusbits wie:
    • modified bzw. dirty: Gibt an, ob dieser Cacheblock geĂ€ndert wurde (nur beim Write-Back-Cache).
    • diverse Statusbits je nach Cache-KohĂ€renz-Protokoll, z. B. je ein Bit fĂŒr:
      • owner: Äquivalent zu „modified & shared“. Gibt an, dass der Block geĂ€ndert wurde und in anderen Caches vorhanden ist. Der Owner ist dafĂŒr verantwortlich, den Hauptspeicher zu aktualisieren, wenn er den Block aus seinem Cache entfernt. Derjenige Prozessor, der zuletzt auf den Cacheblock schreibt, wird neuer Owner.
      • exclusive: Gibt an, dass der Block nicht geĂ€ndert wurde und in keinem anderen Cache vorhanden ist.
      • shared: Hat teilweise unterschiedliche Bedeutungen: Bei MESI gibt das an, dass der Block nicht geĂ€ndert wurde, aber auch in Caches anderer Prozessoren vorhanden ist (dort ebenso unverĂ€ndert). Bei MOESI bedeutet es nur, dass der Block in anderen Prozessorcaches vorhanden ist. Hier ist auch erlaubt, dass der Block verĂ€ndert wurde, also inkonsistent zum Hauptspeicher ist. In diesem Fall gibt es aber einen „Owner“ (s. u.), der fĂŒr das Updaten des Hauptspeichers verantwortlich ist.
    • invalid: Zeigt an, ob der Block frei (also mit ungĂŒltigen Daten befĂŒllt) oder belegt (also mit gĂŒltigen Daten befĂŒllt) ist.

Heiße und kalte Caches

Ein Cache ist „heiß“, wenn er optimal arbeitet, also gefĂŒllt ist und nur wenige Cache Misses hat; ist das nicht der Fall, gilt der Cache als „kalt“. 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 weniger Nachladen erforderlich ist. Im Idealzustand werden Datenzugriffe fast ausschließlich aus dem Cache bedient und das Nachladen kann vernachlĂ€ssigt werden.

Beispiele

Prozessor-Cache

(Siehe auch: Befehlscache)

Bei CPUs kann der Cache direkt im Prozessor integriert oder extern auf der Hauptplatine platziert sein. Oftmals gibt es mehrere Ebenen (Level), die aufeinander aufbauen. Kleinere Level sind dabei typischerweise schneller, haben aber aus KostengrĂŒnden eine kleinere GrĂ¶ĂŸe. Je nach Ort des Caches arbeitet dieser mit unterschiedlichen Taktfrequenzen: Der L1 (Level 1, am nĂ€chsten an der CPU) ist fast immer direkt im Prozessor (d. h. auf dem Die) integriert und arbeitet daher mit dem vollen Prozessortakt – also u. U. mehrere Gigahertz. Ein externer Cache hingegen wird oftmals nur mit einigen hundert Megahertz getaktet.

Aktuelle Prozessoren (z. B. AMD Phenom II, Intel-Core-i-Serie, IBM Power 7) besitzen ĂŒberwiegend drei Cache-Level L1, L2 und L3. GĂ€ngige GrĂ¶ĂŸen fĂŒr L1-Caches sind 4 bis 256 KiB pro Prozessorkern, der L2-Cache ist 64 KiB bis 512 KiB (meist ebenfalls pro Kern), der L3-Cache 2 bis 32 MiB (fĂŒr alle Kerne gemeinsam). Bei kostengĂŒnstigeren Versionen wird mitunter der L3-Cache weggelassen oder abgeschaltet, dafĂŒr ist der L2-Cache teilweise etwas vergrĂ¶ĂŸert. Prozessorcache als Extra-Chip auf dem Mainboard wird heute nicht mehr gebaut, als Extra-Die im selben Chip-GehĂ€use (siehe Multi Chip Package) nur noch selten.

In jedem Fall ist eine Protokollierung erforderlich, um die KohĂ€renz der Daten (z. B. zwischen Caches und Hauptspeicher) sicherzustellen. Dazu dienen Flags, die einen Speicherbereich (typischerweise eine ganze line von 512 Byte) als „dirty“, also geĂ€ndert, markieren (s. o. bei Schreibstrategie). Das Problem verschĂ€rft sich bei mehreren Cachelevels und mehreren Prozessoren oder Prozessorkernen.

Moderne Prozessoren haben getrennte L1-Caches fĂŒr Programme und Daten (Lese- und Schreibcache), teilweise ist das auch noch beim L2 der Fall (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 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-Flaschenhals weiter verringert werden kann. Ein Nachteil ist, dass selbstmodifizierender Code nicht sehr gut auf modernen Prozessoren lĂ€uft. Allerdings wird diese Technik aus SicherheitsgrĂŒnden sowie wegen der schlechten ÜberprĂŒfbarkeit heute ohnehin nur noch sehr selten verwendet.

Laufwerks-Cache

Bei Festplatten befindet sich der Cache auf der Steuerplatine (siehe Festplattencache) oder einer extra Platine, dem Festplattenkontroller.

Auch die meisten Laufwerke fĂŒr optische Speicher besitzen Caches, um die oftmals im dreistelligen Millisekundenbereich liegenden Zugriffszeiten und Schwankungen im Datenstrom (z. B. durch Synchronisierungsprobleme) aufzufangen.

Software-Caches

Caches können auch bei Software genutzt werden, dabei ist dasselbe Prinzip wie bei der Hardwareimplementierung gemeint: Daten werden fĂŒr einen schnelleren Zugriff auf ein schnelleres Medium zwischengespeichert.

Beispiele:

  • Festplattencache (vom Betriebssystem verwaltet): Festplatte → Hauptspeicher
  • Anwendungsdaten (Memoisation): Rechnung → Hauptspeicher
  • Browser-Cache: Netz → (Festplatte / Arbeitsspeicher)
  • Webserver: Datenbank → HTML-Datei

Software-Caches, welche die Festplatte als schnelleres Medium verwenden, werden meist in Form von temporÀren Dateien angelegt.

Man spricht auch von Caching, wenn ein Betriebssystem gewisse Ressourcen – wie z. B. Funktionsbibliotheken oder Schriftarten – vorerst im Arbeitsspeicher belĂ€sst, obwohl sie nach Ende ihrer Benutzung nicht mehr gebraucht werden. So lange kein Speichermangel herrscht, können sie im Arbeitsspeicher verbleiben, um dann ohne Nachladen von der Festplatte sofort zur VerfĂŒgung zu stehen, wenn sie wieder gebraucht werden. Wenn allerdings die Speicherverwaltung des Betriebssystems einen Speichermangel feststellt, werden diese Ressourcen als erste gelöscht.

Einzelnachweise

  1. ↑ Andrew S. Tanenbaum, James Goodman: Computerarchitektur. 4. Auflage. Pearson Studium, MĂŒnchen 2001, ISBN 3-8273-7016-7 (deutsch), S. 92.
  2. ↑ John Hennessy, David Patterson: Computer Architecture. A Quantitative Approach. 4th Edition. Morgan Kaufmann Publishers, ISBN 978-0-12-370490-0 (engl.), S. C-11–C-12.

Weblinks

Wiktionary Wiktionary: Cache â€“ BedeutungserklĂ€rungen, Wortherkunft, Synonyme, Übersetzungen

Wikimedia Foundation.

Synonyme:

Schlagen Sie auch in anderen WörterbĂŒchern nach:

  • cachĂ© — cachĂ© 
   Dictionnaire des rimes

  • Cache — Saltar a navegaciĂłn, bĂșsqueda Diagrama de una memoria cache de CPU. En informĂĄtica, una cache o cachĂ© (esta Ășltima Ășnica forma reconocida por la RAE[1] 
   Wikipedia Español

  • cache- — ⇒CACHE , Ă©lĂ©ment prĂ©f. ÉlĂ©ment de compos., dĂ©verbal de cacher, servant Ă  la formation de subst. masc., appartenant notamment au vocab. des jeux, de la mode ou de la technol. et dĂ©signant des objets ou instruments dont on se sert pour cacher. A.… 
   EncyclopĂ©die Universelle

  • CachĂ© — CachĂ©, tambiĂ©n escrito cache puede referirse a: InformĂĄtica CachĂ© (informĂĄtica), es un conjunto de datos duplicados de otros originales. CachĂ© web, es la que almacena documentos web. CachĂ© Robson CachĂ© de disco DNS cache poisoning Coherencia de… 
   Wikipedia Español

  • cache — 1. (ka ch ) s. f. Lieu propre Ă  cacher ou Ă  se cacher. ‱   On n est pas peu embarrassĂ© Ă  inventer dans toute une maison une cache fidĂšle, MOL. l Av. I, 4. ‱   Il dit au roi : Je sais, sire, une cache, Et ne crois pas qu autre que moi la sache, LA 
   Dictionnaire de la Langue Française d'Émile LittrĂ©

  • cachĂ© — cachĂ©, Ă©e (ka chĂ©, chĂ©e) part. passĂ©. 1°   DĂ©robĂ© Ă  la vue. Serpent cachĂ© sous l herbe, sous terre. CachĂ© aux regards du peuple. J ai tenu ce proscrit cachĂ© chez moi. Écueils cachĂ©s. Sentiers cachĂ©s. Il y a quelque piĂ©ge cachĂ©. ‱   On m Ă©levait… 
   Dictionnaire de la Langue Française d'Émile LittrĂ©

  • cache-cƓur — [ kaʃkɶr ] n. m. ‱ 1952; de 1. cacher et cƓur ♩ Gilet court, Ă  col en V trĂšs Ă©chancrĂ©, croisĂ© sur la poitrine, utilisĂ© dans l habillement ou en layette. Des cache cƓurs. ● cache cƓur nom masculin invariable Corsage court dont les devants en… 
   EncyclopĂ©die Universelle

  • cachĂ© — 1. AdaptaciĂłn grĂĄfica de la voz francesa cachet, usada en español con los sentidos de ‘distinciĂłn o elegancia’: «Hay quien nace [...] con estilo y caché» (VergĂ©s Cenizas [R. Dom. 1980]); y ‘cotizaciĂłn o remuneraciĂłn de un artista’: «¿QuĂ© mĂ©ritos… 
   Diccionario panhispĂĄnico de dudas

  • CachĂ© — DonnĂ©es clĂ©s RĂ©alisation Michael Haneke ScĂ©nario Michael Haneke Acteurs principaux Daniel Auteuil Juliette Binoche Maurice BĂ©nichou SociĂ©tĂ©s de production Les Films du Losange 
   WikipĂ©dia en Français

  • Cache — Cache, OK U.S. city in Oklahoma Population (2000): 2371 Housing Units (2000): 952 Land area (2000): 3.388615 sq. miles (8.776472 sq. km) Water area (2000): 0.014556 sq. miles (0.037701 sq. km) Total area (2000): 3.403171 sq. miles (8.814173 sq.… 
   StarDict's U.S. Gazetteer Places


Share the article and excerpts

Direct link

 Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.