Allgemeines
CPU-Caches sind aus Cache-Zeilen aufgebaut. Diese sind die kleinsten adressierbaren Einheiten im Cache. Die Länge der Cache-Zeilen variiert, aber 32-64 Byte sind üblich.[1] Nun ist der Cache deutlich kleiner als der Hauptspeicher und man muss eine schnelle Möglichkeit haben, Hauptspeicher-Adressen auf den Cache abzubilden.
Eine Möglichkeit das zu machen, ist ein sog. „direct mapped cache“. Das ist im Prinzip eine Hash-Funktion, die zusätlich noch schnell von der Hardware umgesetzt werden können muss. Also unterteilt man gedanklich die Hauptspeicheradressen in 3 Teile:
- Tag
- Index
- Block-Offset
Der Index gibt direkt die Cache-Zeile an, in der die Daten einer Hauptspeicheradresse landen werden. Es wäre also z.B. möglich, die Pins des Adressbus, auf denen die Index-Bits liegen, auf einen Multiplexer zu legen, der die entsprechende Cache-Zeile durchschaltet.
Es gilt also: Index-Länge in Bit = \(\log_2(\text{Cache-Zeilen})\)
Nun kann es passieren, dass viele Hauptspeicher-Adressen in der selben Zeile landen. Um diese unterscheiden zu können, speichert man folgendes in einer Cache-Zeile:
- Tag
- Datenblock
- Flags
Der Datenblock beinhaltet die eigentlichen Daten aus dem Hauptspeicher. Benötigt nun ein Programm die Daten aus einer Hauptspeicheradresse, wird der Index dieser Adresse extrahiert und an dieser Cache-Zeile nachgeschaut. Wenn dann die Tags übereinstimmen, ist es die richtige Adresse und man kann die Daten aus dem Cache entnehmen.
Da man durch den Block-Offset ja eine ganze Reihe von Hauptspeicher-Adressen zusammenfasst, muss gelten:
Größe der Cache-Zeile \(= 2^{\text{Länge des Block-offsets}} \cdot\) Größe des Inhalts einer Hauptspeicheradresse
Der Block-Offset wird nicht weiter verwendet. Es wird schlicht ignoriert.
Der Tag muss aktiv im Cache gespeichert werden und die Länge des Tags im Cache muss mindestens so lang sein wie die Tag-Länge der Hauptspeicher- Adresse. Natürlich wird der Tag im Cache genau so lang sein wie der in der Hauptspeicher-Adresse. Man hat ja keinen Speicher zu verschenken.
Bei einem Voll-Assoziativem Cache würde es also keinen Index geben. Eine Hauptspeicher-Adresse würde dann nur in Tag und Block-Offset geteilt werden.
Bei einem \(n\)-fach Satzassoziativem Cache gibt es \(\frac{\text{Cachzeilen}}{n}\) Sätze mit jeweils \(n\) Cachezeilen. Das Datenwort kann nur in einem Satz stehen, dort aber an einer beliebigen Stelle. Nun geht die CPU wie folgt vor:
- Datenwort mit Hauptspeicheradresse x = $x_\text{tag}$ | $x_\text{index}$ | $x_\text{blockoffset}$ wird benötigt
- $x_\text{index}$ = der zu durchsuchende Satz im Cache
Dieser Satz wird zu den $n$ Vergleichern durchgeschaltet - Jeder Vergleicher vergleich den $x_\text{tag}$ und den in der Cache-Zeile gespeicherten tag
- Wird die Adresse gefunden → Cache Hit
Datenwort in keiner Cache-Zeile: Cache-Miss, Hauptspeicherzugriff
Physical address and virtual address
Die physische Adresse entspricht dem, womit man den Speicherbaustein anspricht. Nun kann es möglich sein, dass man mehrere RAM-Bausteine hat oder dass das Programm theoretische mehr Speicher braucht als an Hauptspeicher zur verfügung steht. Dennoch will man als Programmierer einheitlich adressieren. Also nutzt man im Userspace virtuelle Adressen (Im Kernel-Space können sowohl physische als auch virtuelle Adressen genutzt werden, siehe StackOverflow). Außerdem will man Speicherschutz herstellen. Die virtuellen Adressen sind scheinbar zusammenhängend und der Adressraum ist sehr groß. Der virtuelle Adressraum ist in Blöcke (Pages) unterteilt und die Pages werden von langsamen, aber großen auf schnelle, aber kleine Speichermedien je nach Bedarf aus- oder eingelagert.
Das passiert allerdings selten. Um zu sehen, wie häufig das der Fall ist, sollte man sich folgendes anschauen:
- /proc/swaps
- /proc/meminfo - ein paar Erklärungen zu meminfo
vmstat -s
Cache-Modelle
Fordert nun ein Prozess die Daten einer virtuellen Adresse an, kommt es nun auf die verschiedenen Cache-Modelle (PIPT, VIPT, VIVIT) an. Es gilt jedoch immer: Die CPU schaut im TLB nach, ob sie direkt erfahren kann, wo die Daten sind. Falls das nicht funktiniert, geht es wie folgt weiter:
Physically Indexed, Physically Tagged
Hier wird der index und der tag aus der physischen Adresse gezogen. Damit muss zuerst die MMU die virtuelle Adresse in eine physische Adresse umwandeln, bevor man im Cache nachschauen kann.
Virtually indexed, physically tagged
Man bekommt den Index aus der virtuellen Adresse, kann im Cache nachschauen ob dort überhaupt etwas steht, falls ja muss aber noch die MMU die physische Adresse nachschlagen damit man den tag überprüfen kann.
Annahme: Wir haben eine virtuelle Adresse 123456789. Der Index sind die Ziffern [4,6] also 456. Nun wird das auf die physische Adresse 123456789 gemappt. Der Tag sind die Ziffern [1,3] also 123.
Nun haben wir eine zweite virtuelle Adresse 000456000. Der index sind die Ziffern [4,6] also 456. Die zugehörige phyische Adresse sein 123000000. Der Tag sind die Ziffern [1,3] also 123.
Nun müsste doch fehlerhaft ein Cache-Hit herauskommen, oder?
Physically Indexed / Virtually Tagged
Macht keinen Sinn, weil man Probleme wegen Doppeldeutigkeiten bekommen kann und man auf jeden Fall immer zuerst die MMU nutzen kann.
Virtually Indexed / Virtually Tagged
Kein MMU-Zugriff benötigt, also schneller als die anderen Varianten. Birgt aber ein paar Probleme (Ambiguity, Alias)
Quellen
- Page-Table Lookups
- Virtuelle Adresse
- CPU cache
- Four-level page tables
- Linux Specifics: Address Space Layout
- Some example assignments (Memory access times, With and without TLBs)