Cache

Grundprinzip und Nutzen

Ein Cache ist in der Informationstechnik ein schneller Pufferspeicher. Er verhindert wiederholte Zugriffe auf vergleichsweise langsame Datenspeicher oder aufwendige Neuberechnungen: Bereits geladene oder erzeugte Daten bleiben vorübergehend im Cache und können bei erneutem Bedarf schneller abgerufen werden. Daten können außerdem vorsorglich vom Hintergrundmedium geladen werden, wenn sie vermutlich bald gebraucht werden (read-ahead). Ein Cache kann Hardware sein, etwa Speicherchips, oder Software, etwa temporäre Dateien oder reservierter Speicherplatz.

Ziele sind kürzere Zugriffszeiten und/oder weniger Zugriffe auf das langsame Hintergrundmedium. Dadurch sinkt auch die erforderliche Datenübertragungsrate; das Hintergrundmedium kann langsamer angebunden sein, was Kosten senken kann. Bei CPUs kann dies den Von-Neumann-Flaschenhals verringern und Programme im Mittel stark beschleunigen. Caches lohnen sich nur, wenn die Zugriffszeit die Gesamtleistung wesentlich beeinflusst. Bei Vektorrechnern spielt sie eine untergeordnete Rolle, weshalb dort üblicherweise keine Caches eingesetzt werden.

Ein Nachteil ist das schwer vorhersagbare Zeitverhalten: Fehlen Daten im Cache, muss auf das langsamere Hintergrundmedium gewartet werden. Das geschieht bei Prozessoren oft bei bisher ungenutzten Daten oder beim Laden des nächsten Befehls nach weiten Sprüngen. Das Konzept eines schnellen Zwischenspeichers stellte M. V. Wilkes erstmals im April 1965 vor. Moderne Caches laden auch erwartete Daten vor, softwareunterstützt mit PREFETCHT0, PREFETCHT1, PREFETCHT2 und PREFETCHNTA ab 1999/Pentium III oder hardwareunterstützt durch das Erkennen von Zugriffsmustern ab 2000/Pentium 4.

Hierarchie, Größe und Lokalität

Ein einzelner Cache kann meist nicht zugleich sehr groß und sehr schnell sein. Deshalb verbindet eine Cachehierarchie mehrere Ebenen: L1, L2 bis L-n. Je kleiner die Level-Nummer, desto näher liegt der Cache am schnellen Benutzer und desto schneller wird er durchsucht. Fehlen Daten in L1, wird L2, dann gegebenenfalls L3 usw. durchsucht. Werden Daten etwa in L3 gefunden, gelangen sie zum Zugreifer und zugleich in L1; dafür muss dort eine Cache-Line weichen und kann in L2 absinken.

Bei einer inklusiven Hierarchie ist jede Cache-Line aus L1 auch in L2 und L3 vorhanden. Bei einer exklusiven Hierarchie liegt eine Cache-Line nur in einem Level. Exklusive Hierarchien verursachen mehr Verkehr zwischen den Caches, können aber so viele Cache-Lines halten wie die Summe der Größen von L1, L2 und L3. Bei inklusiven Caches ist dafür nur die L3-Größe maßgebend. Moderne CPUs haben vor allem zwei oder drei Ebenen; andere Geräte meist eine. Webbrowser sind eine wichtige Software-Ausnahme mit zwei Ebenen: Arbeitsspeicher und Festplattenlaufwerk.

Caches sind meist viel kleiner als der Hintergrundspeicher, weil schnellere Speichertechnik eingesetzt wird, etwa SRAM statt DRAM oder DRAM statt Magnetscheibe, und diese pro Bit teurer ist. Ihre Wirkung beruht auf Lokalität. Zeitliche oder temporale Lokalität bedeutet: Bereits genutzte Daten, etwa in Programmschleifen, werden wahrscheinlich bald erneut gebraucht. Räumliche oder spatiale Lokalität bedeutet: Nach einer Adresse werden oft nahe Adressen benötigt, etwa aufeinanderfolgende Befehle oder Elemente eines Arrays. Kleine Caches mit einigen Kibibytes können daher wirksam sein. Bei ständig neuen Streaming-Daten gibt es keine Beschleunigung durch Mehrfachzugriffe, höchstens geringfügig durch read-ahead.

Nutzdaten werden blockweise als Cache-Lines gespeichert. Sie waren in den 1990er Jahren 16 oder 32 Byte groß und sind heute 64 oder 128 Bytes groß. Je Cache-Line werden 5 bis 7 Byte Metadaten benötigt; außerdem lesen Speicher seit DDR1-RAM Blöcke von 64 oder 128 Byte statt einzelner Bytes. Für ECC-RAM sind nur Blöcke von 8 Byte bis 64 Bytes schreibbar.

Aufbau und Organisationsformen

Ein Cache besitzt meist eine feste Zahl von Einträgen. Jeder enthält die Cache-Line mit den Daten, einen Address-Tag mit höherwertigen Adressbits, Valid-Tags für gültige Daten und bei Write-Back-Caches Dirty-Tags für veränderte Daten. LRU-Tags helfen – außer bei Direct-Mapped-Caches – zu erkennen, welche Daten kürzlich oder häufig benutzt wurden. Wenn Startadressen durch die Länge der Cache-Line teilbar sind, genügt statt der vollständigen Adresse die Nummer des Datenblocks als Tag. Bei einer 64-Byte-Line sind beispielsweise die Startadressen 0, 64, 128, 192 und 256 möglich. Zweierpotenzen im Binärsystem machen die Tags platzsparender und die Prüfung schneller.

Cache-Lines können zu Sätzen zusammengefasst werden. Bei m Cacheblöcken und n Blöcken pro Satz, der Assoziativität, gibt es m/n Sätze. Ein direkt abgebildeter Cache (direct mapped, DM) hat n = 1: Für jede Adresse ist genau ein Block zuständig. Das benötigt nur einen Tag-Vergleich, kann aber Conflict Misses verursachen. Ein vollassoziativer Cache (fully associative, FA) hat n = m: Jede Adresse kann in jeden Block, doch alle Tags müssen parallel verglichen werden. Ein satzassoziativer Cache (set associative, SA) wählt n zwischen 2 und m/2 und ist ein Kompromiss aus Hardwareaufwand und Effizienz. DM und FA sind Sonderfälle von SA.

Beispiel: Ein 64-KiB-Cache mit 64-Byte-Zeilen enthält 64 KiB/64 Byte = 1024 Cache-Zeilen und deckt hier 4 GiB Adressraum bei 1 Byte Granularität ab. Beim vollassoziativen Cache gibt es eine Gruppe mit 1024 Zeilen; nötig sind 1024 Komparatoren, die jeweils 32 − 6 = 26 Bit vergleichen. Beim Direct-Mapped-Cache gibt es 1024 Gruppen mit je einer Zeile; die Gruppe wird durch Bit 15 bis 6 bestimmt. Ein Komparator vergleicht 16 Bit. Beim zweifach assoziativen Cache gibt es 512 Gruppen mit je zwei Zeilen; Bit 14 bis 6 bestimmen die Gruppe, zwei Komparatoren vergleichen jeweils 17 Bit. Höhere Assoziativität benötigt mehr Komparatoren und größere Tags.

Treffer, Verdrängung und Schreiben

Ein Cache Hit oder Cachetreffer liegt vor, wenn angeforderte Daten im Cache vorhanden sind; ein Cache Miss, wenn sie fehlen. Die Hit Rate ist die Zahl der Treffer geteilt durch alle Anfragen und liegt zwischen 0 und 1. Eine Hit Rate von 0,7 (= 70 %) bedeutet 70 % sofort beantwortete Anfragen. Die Miss Rate ist die Zahl der Anfragen ohne Daten im Cache geteilt durch alle Anfragen; es gilt: Miss Rate = 1 − Hit Rate.

Ein Capacity Miss entsteht, wenn der Cache zu klein ist und zuvor vorhandene Daten verdrängt wurden; nur ein größerer Cache hilft. Ein Conflict Miss entsteht in satzassoziativen und damit auch DM-Caches, wenn ein Satz voll ist, obwohl andere Sätze freie Blöcke haben; mehr Assoziativität hilft. Vollassoziative Caches haben prinzipbedingt keine Conflict Misses. Ein Compulsory Miss oder Cold Start Miss ist der erstmalige Zugriff auf noch nicht vorhandene Daten, obwohl freier Cacheplatz existiert; es findet keine Verdrängung statt. Prefetcher sollen ihn verringern. Diese drei Fälle heißen die „drei C“. In Multiprozessorsystemen mit Write-Invalidate-Kohärenzprotokoll kann ein viertes C auftreten: Ein Coherency Miss, wenn das Schreiben eines Prozessors einen Block im Cache eines anderen entfernt.

Bei Platzmangel bestimmen Verdrängungsstrategien den zu ersetzenden Block. FIFO verdrängt den ältesten Eintrag, LRU den am längsten nicht genutzten, LFU den am seltensten gelesenen und Random einen zufälligen. CLOCK setzt bei Zugriffen ein Bit; bei einem Miss wird der erste Block ohne gesetztes Bit ersetzt, während bei der Suche passierte gesetzte Bits gelöscht werden. Das optimale Verfahren von Laszlo Belady verdrängt den Bereich, auf den am längsten nicht zugegriffen werden wird. Es wäre optimal, ist aber praktisch nicht einsetzbar, weil der vollständige Programmablauf vorher bekannt sein müsste. Moderne Prozessoren verwenden oft leichter umsetzbares Pseudo-LRU.

Bei Write-Back wird ein geänderter Block zunächst nur im Cache geschrieben und erst beim Verdrängen anhand seines Dirty Bit zurückkopiert. Das ist schnell, kann aber gegenüber anderen Prozessoren oder DMA-Geräten veraltete Daten zeigen; Kohärenzprotokolle wie MESI helfen bei Uniform-Memory-Access-Systemen. Bei Write-Through wird sofort in die nächsthöhere Ebene geschrieben; ein Write Buffer verhindert häufiges Warten, kann aber voll laufen. Bei einem Schreib-Miss lädt Write-Allocate zunächst den Block in den Cache; Non-Write-Allocate schreibt am Cache vorbei und verhindert bei nur einmal geschriebenen Daten das Verdrängen wichtiger Blöcke. Übliche Kombinationen sind Write-Back mit Write-Allocate und Write-Through mit Non-Write-Allocate.

Greifen weitere Geräte auf das Hintergrundmedium zu, müssen Cache und Hintergrundmedium konsistent bleiben. Ein Cache Flush schreibt den vollständigen Cacheinhalt zurück, lässt ihn meist aber erhalten. Er ist etwa bei Multiprozessor-Kommunikation oder der Übergabe eines Hauptspeicherbereichs an einen DMA-Controller nötig. Zusätzlich muss ein Cache über externe Änderungen informiert werden, sonst enthält er ungültige Daten. Ein Cache ist kalt, wenn er nach dem Start noch leer ist und viele Misses hat; er wird heiß, wenn er gefüllt ist und nur wenige Misses aufweist.

Typische Einsatzbereiche

Prozessor-Caches liegen heute meist im Prozessor. L1 arbeitet fast immer auf dem Die mit vollem Prozessortakt, möglicherweise mehreren Gigahertz; ein externer Cache arbeitete oft nur mit einigen hundert Megahertz. AMD Zen 4, Intel Ice Lake und IBM Power10 besitzen überwiegend L1, L2 und L3. L1 umfasst gewöhnlich 4 bis 320 KiB pro Kern, L2 64 KiB bis 32.768 KiB meist pro Kern und L3 2 bis 1152 MiB für alle Kerne gemeinsam. Moderne Prozessoren haben meist getrennte L1-Caches für Programme und Daten, teilweise auch getrennte L2-Caches, also eine Harvard-Architektur. Das erlaubt unterschiedliche Designs und gleichzeitige Instruktions- und Datenzugriffe, verlangt aber bei selbstmodifizierendem Code besondere Behandlung.

Ein Laufwerks-Cache sitzt bei Festplatten auf der Steuerplatine oder im Host-Bus-Adapter und umfasst bei aktuellen Festplatten 8 bis 256 MiB. Optische Laufwerke nutzen Caches, um Zugriffszeiten im oft dreistelligen Millisekundenbereich und Schwankungen im Datenstrom abzufangen.

Software-Caches speichern Daten auf einem schnelleren Medium zwischen: Der Festplattencache des Betriebssystems nutzt Festplatte → Hauptspeicher, Memoisation Berechnung → Hauptspeicher, der Browser-Cache Netz → Festplatte/Arbeitsspeicher und ein Webserver Datenbank → HTML-Datei mittels HTTP Caching. Nicht mehr benötigte Programmbibliotheken oder Schriftarten können im Arbeitsspeicher bleiben und werden bei Speichermangel zuerst gelöscht.

Ein Suchmaschinen-Cache hält von einem Webcrawler geladene Webseiten bereit. Aus ihm werden Indizes erzeugt, in denen der Suchalgorithmus sucht; dadurch muss nicht jede Webseite für jede Anfrage in Echtzeit abgerufen werden. Inhalte können veraltet sein. Betreiber können Änderungen melden, ansonsten prüft der Crawler regelmäßig. Bei Google liegt die Prüfungsfrequenz für die meisten Webseiten zwischen einer und vier Wochen; gemeldete Seiten untersucht der Googlebot.

DNS-Caching speichert Ergebnisse einer Namensauflösung lokal vorübergehend. Gleichartige DNS-Anfragen können dann ohne erneute Anfrage an den Nameserver beantwortet werden, was die Performance erhöht. Namensserver, Cache und Anwendung liegen dabei in der Regel auf unterschiedlichen, über das Internet verbundenen Systemen.