Speicherhierarchie und Caches

Kapitel 4 - Speicherhierarchie und Caches

Was ist Lokalität?
Die drei Cache-Arten
Schreibstrategien für Caches-Zugriff

Was bedeutet die Eigenschaft Lokalität?

Aus programmtechnischer Sicht wiederholen sich oft Befehle und ganze Programmteile. Somit werden Daten oft wiederholt angefordert. Es gibt nun zwei Arten von Lokalität:

Was ist Zeitliche Lokalität?

Auf ein gerade zugegriffenes Datum wird sicher bald wieder zugegriffen.

Was ist Räumliche Lokalität?

Auf Daten, deren Adressen benachbart sind, wird mit hoher Wahrscheinlichkeit auch zugegriffen. Anzumerken ist, daß Datenzugriffe eine geringere Lokalität zeigen als Befehlszugriffe.

Nach welchen Merkmalen lassen sich Caches klassifizieren?

Cache-Größe (damit verbundener Hardware-Aufwand)
Größe einer Cachezeile (Verschmutzungseffekt)
Cache-Organisation (Vollassoziativ/Direct Mapped/Satz-Assoziativ)
Schreibstrategie (Write-Through /-Allocate oder -Back)
Split-Cache-Design (Transfer-Bandbreiten)
Multi-level Cache-Hierarchien (Workingssetgrößen)
Effective Working Set (Overflow-, Victim-, Trace Cache)
Innere Cache-Parallelität (Streaming)
Kohärenz-Verfahren (Snooping, MESI)

Wie ist ein Cache aufgebaut?

Zeile 1	Adress-Tag	Datenblock	Control(Bits)
Zeile 2	Adress-Tag	Datenblock	Control(Bits)
Zeile 3	Adress-Tag	Datenblock	Control(Bits)
...	Adress-Tag	Datenblock	Control(Bits)
Zeile n	Adress-Tag	Datenblock	Control(Bits)

Control-Bits sind z.B. Valid-Bits, Dirty-Bits und Prozess-ID. Das Adress-Tag ist nichts weiter als ein Teil der Adresse, welche bei einem Zugriff als Index gilt. Ein Datenblock ist in der Praxis meistens zwischen 16 und 64 KByte groß.

Welche Cache-Arten kennen Sie?

Ein Cache-Eintrag besteht aus einem Tag (Identifikator) und den Daten. Die Implementierung unterscheidet sich. Es gibt voll-, einfach assoziative und Satzassoziative Caches .

Wie arbeitet ein vollassoziativer Cache?

Das Tag Feld ist hier die assoziierende Adresse des Datums im Speicher. Die Hardware ist bei vollassoziativen Caches aufwendig, da diese bei einem Cache Zugriff alle Tags gleichzeitig mit der anliegenden Adresse vergleicht. Dies ist zwar extrem schnell, aber sehr teuer. Außerdem wird er sehr langsam wenn die Anzahl der Cachezeilen hinreichend groß wird.

Da bei vollassoziativen Cachen ein Datum an jede Stelle des Caches platziert werden kann, muss eine Logik her, welche eine Entscheidung trifft. Als Plazierungsstrategie wird oft LRU verwendet. Dies ist seht aufwendig!

Wie arbeitet ein Direct-Mapped-Cache (einfach assoziativer Cache)?

Beim Direct-Mapped-Cache entscheidet eine Map-Funktion, welche Zeile im Cache mit der anliegenden Adresse referenziert wird (somit ist kein LRU o.ä. notwendig). Dabei wird einem Hauptspeicherblock genau ein Cache-Block zugeordnet (n:1 Beziehung). Oft wird eine Funktion wie (A mod Cachesize / Zeilengröße) zur Berechnung der Cachezeile aus der anliegenden Adresse benutzt, da bei diesem Verfahren dann nur (A / Cachesize) als Tag in jeder Cachezeile gespeichert werden muss.
Vorteil dieser Variante ist die einfache, kostengünstige Integration (nur Komperator notwendig) und die hohe Geschwindigkeit. Leider neigt ein Direct-Mapped-Cache zu vielen Konflikten (ähnlich den Kollisionen bei Hash-Tables), welche zusätzliche Cache-Misses bildet, da mehrere Adressen auf die gleiche Cachezeile verweisen.

Wie arbeitet ein n-Wege-Satz Cache (Satzassoziativer Cache)?

Diese Variante ist nichts anderes als eine Implementation mehrerer parallel verknüpfter Direct-Mapped-Caches. Sie stellt quasi einen Kompromiss zwischen Cache-Effizienz und Aufwand dar.
Die Arbeitsweise ist die gleiche, nur das die Map-Funktion nicht nur auf eine Zeile im Speicher zeigt, sondern auf n. Die Hardware des Caches vergleicht alle n Tags gleichzeitig, mit dem anliegenden Index. Ist eine der Tags gleich dem Index, ist dies ein Cache-Hit. Diese Technik reduziert die hohe Anfälligkeit von Direct-Mapped-Caches für Konflikte, benötigt aber mehr Chipfläche.

Cache-Arten

Welche Schreibstrategien für Caches gibt es?

Write-Back,Write-Throug und Write-Allocate.

Write-Back-Strategie?

Ein zu lesendes Datum wird entweder bei einem Hit aus dem Cache gelesen oder im Falle eines Misses, aus dem Hauptspeicher geholt und parallel in den Cache eingetragen. Im Falle der Aktualisierung, muss erst das Dirty-Bit der zu überschreibenden Cache-Line geprüft werden, um diese gegebenenfalls in den Hauptspeicher zurückzuschreiben. (Write-Back)
Vorteil dieser Strategie ist das bei Hits kein Hauptspeicherverkehr oder Busbelastung auftritt. Alle Operationen können schnell innerhalb der Working-Sets mit Cache-Speed erfolgen. Somit arbeitet die CPU ungebremst. Problematisch wird dies, wenn mehrere Bus-Master am Bus hängen. Um Inkonsistenzen zu vermeiden sind dann spezielle Synchronisationsprotololle wie MESI notwendig.

Concurrent Write-Back?

Bei einfachen Write-Back-Caches muss die CPU im Falle eines Cache-Misses warten, bis die neue Cache-Line aus dem Speicher geholt wurde. Um diese Wartezeit im Mittel zu eliminieren, wird die alte Zeile zunächst in einen Writebuffer zwischengespeichert und später, parallel zu nachfolgenden Cache-Referenzen in den Hauptspeicher übernommen. (Sonderform: Buffered Line Refill)

Wenn auch beim Lesen ein Line-(Read)-Buffer verwendet wird, spricht man von einem Streaming Cache.

Write-Through-Strategie?

Write-Through schreibt immer in den Hauptspeicher und falls sich eine Kopie auch im Cache befindet, so wird diese aktualisiert. Genau aus diesem Grund ist kein Rückschreiben eines Dirty-Datums notwendig, da es zu keinen Inkonsistenzen zwischen RAM und Cache kommen kann. Nachteil ist aber, dass nur bei Leseoperationen ein Geschwindigkeitsvorteil erzielt werden kann.

Buffered Write-Through Im Mittel erfolgen nach jeder Write-Operation zwei Read-Operationen. Deshalb kann ein Geschwindigkeitsgewinn erzielt werden, wenn ein schneller Zwischenbuffer (FiFo) vor dem Speicher plaziert wird, welcher einige Write-Operationen aufnehmen kann. Wird nun eine Leseoperation ausgeführt, so kann das Datum falls es noch in dem schnellen Buffer steht, direkt aus diesem gelesen werden.

Write Allocate

Hier wird immer in den Hauptspeicher und in den Cache geschrieben - auch wenn das Datum sich noch nicht im Cache befand.

Zusammenspiel bei Cache-Misses

Write-Allocate

Wird meistens mit Write-Back Strategie gemeinsam verwendet. Write-Allocate bedeutet dabei nichts weiter, als das der Hauptspeicher-Block in den Cache geladen wird.

No-write-Allocate (Write-Around)

Hier wird das Datum direkt im Hauptspeicher modifiziert, weshalb Write Around meist mit Write-Through verbunden wird.

Zusammenfassung Caches

Write-Back wird üblicherweise mit Write-Allocate kombiniert. Beim Write Allocate (fetch-on-write) wird ein Block gelesen und in Cache gespeichert.
Beim No-write-allocate (write-around) wird der Block in der unteren Ebene der Speicherhierarchie modifiziert und nicht nicht im Cache geladen. No-write-allocate wird deshalb meist bei Write-through verwendet.

Was ist der Unterschied zwischen einen logischen und einen physischen Cache?

Physische Caches liegen vor der MMU und speichern somit nur physikalische Adressen. Ein logischer Cache liegt zwischen CPU und MMU und speichert logische Adressen. Vorteil von logischen Caches ist daher, dass die Adressumrechnung bei einem Hit entfällt. Ein großer Nachteil sind aber die Synonym-Probleme bei Multiprozessorsystemen. Des weiteren wird bei Taskwechsel ein Cache-Flush notwendig.

Multi-Level-Caches und Split-Caches

Durch Hintereinanderlegen von verschiedenen Caches kann ein gleitender Übergang zu immer größeren und langsameren Speichern erreicht werden. First Level Caches sind meist n-Wege-Satzassoziativ und folgende Direct-Mapped.
Split-Caches trennen Code und Daten und sind somit viel flexibler und besser an das Zugriffsverhalten in Bezug auf Strategie oder Assoziativität zu optimieren. Dabei unterscheidet man eine Havard-Architektur von der multiplexed Havard-Architektur (von Neumann Prinzip). Die reine Harvard trennt nicht nur Cache sondern auch den Hauptspeicher in Daten und Codebereich. Bei von Neumann liegen Daten und Code zusammen im Hauptspeicher und werden nur im Cache getrennt. Durch Trennung von Code und Daten verdoppelt sich die Bandbreite, da zeitgleich zugegriffen werden kann.

Was geschieht wenn kein Platz mehr im Cache vorhanden ist?

Es muss eine Cache-Line ausgewählt werden, die mit den neuen benötigten Daten überschrieben werden kann. Die Auswahl erfolgt meistens mit LRU - Last Recently Used. D.h. die am längsten nicht genutzte Cache-Line fliegt raus.

Was ist ein Burst-Cache?

Burst Caches schreiben nicht nur eine Zeile in den Speicher zurück, sondern gleich mehrere, um die Bandbreite auszunutzen und somit Zeit zu sparen.

Zusammenhänge zwischen Caches, TLB's und Page Tables

Folgende vier Fragen stellen sich bei Caches, TLB's und auch bei Page Tables:

Wo kann ein Block eingelagert werden? (Direct Mapped also nur an einem Ort, Set Assoziativ an mehreren Orten oder Voll Assoziativ, also überall)
Wie kann ein Block gefunden werden? (indexiert, limitierte Suche, komplette Suche oder lookup table wie Page Tables)
Wie wird ein Block bei einem Miss aktualisiert? (normalerweise über LRU oder random Methoden)
Wie wird mit Schreiboperationen umgegangen? (Write Through oder Write Back)

Ein TLB ist ein Translation Lookaside Buffer und ist ein kleiner Cache für die Page Table, um Seitenzugriffe zu beschleunigen.

Was ist ein Trace-Cache

Ein Trace Cache ist ein spezieller Befehlscache, der "Traces" des aktuellen Programmlauf protokolliert. Dabei speichert jede Zeile einen Trace, welcher typisch mehrere taken branches enthalten kann. Befehlsfolgen, die aufgrund von taken branches (weit) auseinander liegen, werden in kontinuierlicher Folge abgespeichert. Gepaart mit multiple branch prediction können mehrere zusammenhängende Basisblöcke parallel gefetched werden. (ergibt hohe issue rate)