Mit Google fortfahren
Cache-Speicher: Funktion, Hits und Grenzen erklärt
Ein Cache-Speicher hält häufig, kürzlich oder wahrscheinlich bald benötigte Daten und Befehle nahe an der CPU bereit. Dadurch muss der Prozessor seltener auf den langsameren Hauptspeicher zugreifen. Das kann Programme beschleunigen – aber nur, wenn der Cache die passenden Inhalte enthält.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wo liegt der Cache in der Speicherhierarchie?
Eine CPU benötigt fortlaufend Befehle und Daten. Nicht alle Speicher sind jedoch gleich schnell, groß oder nah am Prozessor.
Eine vereinfachte Speicherhierarchie lautet:
- Register befinden sich in der CPU und halten gerade unmittelbar benötigte Werte.
- Cache-Speicher hält ausgewählte Daten- und Befehlsblöcke für schnelle Zugriffe bereit.
- RAM, der Hauptspeicher, enthält aktuell benötigte Programme und Daten in größerer Menge.
- Sekundärspeicher wie SSD oder HDD bewahrt Programme und Dateien langfristig auf.
Je näher eine Ebene an der CPU liegt, desto schneller kann sie typischerweise erreicht werden. Sehr schneller Speicher ist jedoch nur in begrenzter Größe sinnvoll. Deshalb verbindet die Hierarchie kleine schnelle mit größeren langsameren Speichern.
Cache-Speicher
Ein Cache ist ein kleiner, schneller Zwischenspeicher zwischen einem schnellen Verbraucher und einer langsameren Datenquelle. Beim CPU-Cache ist die CPU der Verbraucher und der Hauptspeicher die langsamere Quelle.
Stell dir einen Arbeitsplatz in einer Bibliothek vor. Das Buch auf deinem Tisch erreichst du sofort. Für ein Buch im Regal musst du aufstehen. Ein Buch aus dem Magazin zu holen dauert noch länger.
Der Tisch entspricht dem besonders schnellen Speicher nahe an der CPU. Weil dort nur wenige Bücher Platz haben, solltest du die wahrscheinlich benötigten Bücher bereitlegen. Genauso muss ein Cache auswählen, welche Daten er aufnimmt und behält.
Was geschieht bei Hit und Miss?
Bei jeder passenden Speicheranfrage prüft das System, ob die benötigte Information im Cache liegt.
Cache Hit
Ein Cache Hit ist ein Treffer: Die angeforderten Daten befinden sich im Cache und können von dort geliefert werden.
Cache Miss
Ein Cache Miss ist ein Fehlschlag: Die Daten fehlen im Cache. Sie müssen aus einer langsameren Speicherebene geladen werden.
Ein typischer Zugriff läuft so ab:
- Die CPU fordert Daten oder einen Befehl an.
- Zuerst wird die schnellste passende Cacheebene geprüft.
- Bei einem Hit erhält die CPU die Daten aus dem Cache.
- Bei einem Miss wird in der nächsten Ebene gesucht.
- Die geladenen Daten können für spätere Zugriffe in den Cache übernommen werden.
Die Hit Rate ist der Anteil der Treffer an allen Cacheanfragen. Die Miss Rate ist der Anteil der Fehlschläge.
$$\text{Miss Rate}=1-\text{Hit Rate}$$
Eine Hit Rate von 0,7 bedeutet: 70 Prozent der Anfragen sind Treffer. Die Miss Rate beträgt daher 0,3 beziehungsweise 30 Prozent.
Das bedeutet nicht, dass ein Programm genau 70 Prozent schneller läuft. Die tatsächliche Wirkung hängt unter anderem davon ab, wie lange Hits und Misses dauern und welche anderen Arbeiten das Programm ausführt.
Ein Hit ist schnell. Ein Miss kostet zusätzliche Zeit, weil mindestens eine langsamere Ebene angesprochen werden muss.
Warum kann ein kleiner Cache wirksam sein?
Ein Cache ist viel kleiner als der Hauptspeicher. Trotzdem kann er viele Anfragen beantworten, weil Programme oft nicht völlig zufällig auf Speicher zugreifen. Sie zeigen Lokalität.
Zeitliche Lokalität
Zeitliche Lokalität bedeutet: Kürzlich verwendete Daten oder Befehle werden wahrscheinlich bald erneut benötigt. Beispiele sind ein wiederholt ausgeführter Schleifenbefehl oder eine häufig gelesene Variable.
Räumliche Lokalität
Räumliche Lokalität bedeutet: Nach einem Speicherzugriff werden wahrscheinlich bald benachbarte Adressen benötigt. Das geschieht etwa beim nacheinander erfolgenden Lesen von Arrayelementen oder Programmbefehlen.
Daten werden deshalb meist nicht als einzelne Bytes, sondern blockweise übertragen. Eine solche Verwaltungseinheit heißt Cache-Line. Sie enthält einen zusammenhängenden Speicherbereich und zusätzliche Verwaltungsinformationen, beispielsweise zur Gültigkeit und Zuordnung.
Ein Programm liest die Elemente eines Arrays der Reihe nach. Wird mit dem ersten Element zugleich ein Block benachbarter Elemente geladen, können spätere Zugriffe auf Elemente dieses Blocks Hits sein. Das nutzt räumliche Lokalität.
Liest eine Schleife denselben Zähler immer wieder, nutzt der Cache dagegen zeitliche Lokalität.
Gegenbeispiel: Verarbeitet ein Algorithmus fortlaufend neue, weit auseinanderliegende Daten und verwendet sie nicht erneut, ist die Trefferwahrscheinlichkeit geringer. Ein Cache garantiert deshalb keine Beschleunigung.
Wie arbeiten L1, L2 und L3 zusammen?
Ein einzelner Cache kann nicht zugleich beliebig groß und maximal schnell sein. Prozessoren verwenden deshalb meist mehrere Cacheebenen.
- L1 ist die kleinste und schnellste der drei Ebenen und liegt direkt am Prozessorkern. Häufig gibt es getrennte L1-Caches für Befehle und Daten.
- L2 ist größer, aber langsamer als L1. Er kann einem Kern zugeordnet oder geteilt sein.
- L3 ist typischerweise noch größer und langsamer als L2 und wird häufig von mehreren Kernen gemeinsam genutzt.
Zuerst wird die schnellste Ebene geprüft. Verfehlt L1, folgt L2; danach kann L3 folgen. Erst nach weiteren Misses ist ein Zugriff auf den Hauptspeicher nötig.
Die CPU benötigt einen Befehl:
- Liegt er im L1-Instruktionscache, entsteht sofort ein Hit.
- Fehlt er dort, wird die nächste Cacheebene geprüft.
- Wird er beispielsweise in L3 gefunden, kann er zur CPU geliefert und zugleich in eine schnellere Ebene übernommen werden.
- Ist dort kein Platz, muss gegebenenfalls eine andere Cache-Line weichen.
Bei einer inklusiven Hierarchie kann eine Line aus L1 zusätzlich in tieferen Ebenen vorhanden sein. Bei einer exklusiven Hierarchie liegt eine Adresse über die Ebenen hinweg nur einmal vor. Beide Formen verteilen Kapazität und Datenverkehr unterschiedlich.
Welche Grenzen und Verwaltungsprobleme gibt es?
Cacheplatz ist begrenzt. Soll eine neue Cache-Line aufgenommen werden, muss möglicherweise eine vorhandene Line verdrängt werden. Eine Ersetzungsstrategie entscheidet, welche Line weicht.
- LRU verdrängt bevorzugt die am längsten nicht verwendete Line.
- FIFO verdrängt den ältesten Eintrag.
- Random wählt eine Line zufällig aus.
- Pseudo-LRU nähert LRU mit geringerem Verwaltungsaufwand an.
Keine Strategie kennt bei einem laufenden allgemeinen Programm sicher alle zukünftigen Zugriffe. Eine unpassend verdrängte Line kann deshalb kurz darauf erneut benötigt werden und einen Miss verursachen.
Vertiefung: Ursachen für Misses
- Compulsory Miss: Auf eine Adresse wird zum ersten Mal zugegriffen.
- Capacity Miss: Die benötigten Daten passen insgesamt nicht in den Cache.
- Conflict Miss: Mehrere Speicherblöcke konkurrieren aufgrund der Cacheorganisation um dieselben möglichen Plätze.
- Coherency Miss: In einem Mehrkernsystem wird eine Kopie durch eine Änderung in einem anderen Cache ungültig.
Viele Misses bedeuten daher nicht automatisch, dass der Computer zu wenig RAM besitzt.
Was passiert beim Schreiben?
Bei Write-Through wird eine Änderung sofort in den Cache und in die nächste Speicherebene geschrieben. Das erzeugt mehr unmittelbaren Speicherverkehr.
Bei Write-Back wird zunächst nur die Cachekopie geändert. Sie wird als verändert oder dirty markiert und später zurückgeschrieben. Das kann wiederholte Schreibzugriffe beschleunigen, verlangt aber sorgfältige Verwaltung.
Besitzen mehrere Prozessorkerne Kopien derselben Daten, müssen Cache-Kohärenzprotokolle dafür sorgen, dass die Kerne keine widersprüchlichen Werte verwenden. Bei Softwarecaches erfüllt die Invalidierung eine verwandte Aufgabe: Eine veraltete Kopie wird als ungültig markiert oder ersetzt.
Ein Kern ändert einen Wert in seinem Cache. Ein anderer Kern besitzt noch eine ältere Kopie. Ohne Kohärenzregel könnten beide Kerne mit unterschiedlichen Werten weiterarbeiten. Das System muss die alte Kopie deshalb aktualisieren oder ungültig machen.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Cache-Speicher
- Zweck
- schnelle Zugriffe
- weniger Hauptspeicherzugriffe
- Trefferverhalten
- Cache Hit
- Cache Miss
- Lokalität
- zeitliche Wiederverwendung
- benachbarte Adressen
- Hierarchie
- L1
- L2
- L3
- Verwaltung
- Ersetzung
- Schreibstrategie
- Kohärenz und Invalidierung
- Grenze
- begrenzte Kapazität
- unvorhersehbare Misses
- mögliche veraltete Kopien
- Zweck