Aus programmtechnischer Sicht wiederholen sich oft Befehle und ganze Programmteile. Somit werden Daten oft wiederholt angefordert. Es gibt nun zwei Arten von Lokalität:
Auf ein gerade zugegriffenes Datum wird sicher bald wieder zugegriffen.
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?
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 .
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!
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.
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.
Welche Schreibstrategien für Caches gibt es?
Write-Back,Write-Throug und Write-Allocate.
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.
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 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
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.
Hier wird immer in den Hauptspeicher und in den Cache geschrieben - auch wenn das Datum sich noch nicht im Cache befand.
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.
Beim No-write-Allocate (Write-Around)
wird das Datum direkt im Hauptspeicher modifiziert, weshalb Write Around meist
mit Write-Through verbunden wird.
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-CachesDurch 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.
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.
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 TablesFolgende vier Fragen stellen sich bei Caches, TLB's und auch bei Page Tables:
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)
status | not read | reprioritisations | ||
---|---|---|---|---|
last reprioritisation on | suggested re-reading day | |||
started reading on | finished reading on |