Wie funktioniert ein direkt zugeordneter Cache?

Question

Ich nehme einen Kurs in Systemarchitektur und habe Schwierigkeiten zu verstehen, wie ein direkt abgebildeter Cache funktioniert.

Ich habe an verschiedenen Orten nachgeschaut, sie erklären es auf verschiedene Weise, was mich noch mehr verwirrt.

Was ich nicht verstehen kann, ist, was der Tag und der Index sind und wie sie ausgewählt werden?

Die Erklärung aus meiner Vorlesung lautet: "Adresse ist in zwei Teile unterteilt Index (z.B. 15 Bits) wird verwendet, um (32k) RAMs direkt anzusprechen Der Rest der Adresse, Tag wird gespeichert und mit dem eingehenden Tag verglichen."

Woher kommt dieser Tag? Es kann nicht die vollständige Adresse des Speicherorts im RAM sein, da es den direkt abgebildeten Cache nutzlos macht (im Vergleich zum voll assoziativen Cache).

Vielen Dank.

Answer 1

Okay. Lassen Sie uns zunächst verstehen, wie die CPU mit dem Cache interagiert.

Es gibt drei Speicherebenen (im Großen und Ganzen) - Cache (in der Regel bestehend aus SRAM-Chips), Hauptspeicher (in der Regel bestehend aus DRAM-Chips) und Speicher (in der Regel magnetisch, wie Festplatten). Wenn die CPU Daten aus einer bestimmten Position benötigt, sucht sie zuerst im Cache, ob sie dort vorhanden sind. Cache-Speicher liegt in Bezug auf die Speicherhierarchie am nächsten zur CPU, daher ist seine Zugriffszeit am geringsten (und die Kosten am höchsten), daher, wenn die gesuchten Daten im Cache gefunden werden, stellt dies einen 'Treffer' dar und die Daten werden von dort für die Verwendung durch die CPU abgerufen. Wenn sie nicht dort sind, müssen die Daten vom Hauptspeicher in den Cache verschoben werden, bevor sie von der CPU abgerufen werden können (die CPU interagiert in der Regel nur mit dem Cache), was eine Zeitstrafe nach sich zieht.

Um herauszufinden, ob die Daten im Cache vorhanden sind oder nicht, werden verschiedene Algorithmen angewendet. Einer davon ist die Methode des direkt zugeordneten Caches. Vereinfacht ausgedrückt, nehmen wir an, dass ein Speichersystem vorhanden ist, bei dem 10 Cache-Speicherpositionen (nummeriert von 0 bis 9) und 40 Hauptspeicherpositionen (nummeriert von 0 bis 39) verfügbar sind. Dieses Bild fasst es zusammen:

Es stehen 40 Hauptspeicherpositionen zur Verfügung, jedoch können nur bis zu 10 im Cache untergebracht werden. Daher muss die eingehende Anforderung von der CPU auf irgendeine Weise auf eine Cache-Position umgeleitet werden. Das hat zwei Probleme:

1. Wie umleiten? Speziell, wie dies auf eine vorhersagbare Weise geschehen kann, die sich im Laufe der Zeit nicht ändert?

2. Wenn die Cache-Position bereits mit Daten gefüllt ist, muss die eingehende Anforderung von der CPU identifizieren, ob die Adresse, von der sie die Daten benötigt, mit der Adresse übereinstimmt, deren Daten an diesem Ort gespeichert sind.

In unserem einfachen Beispiel können wir dies mit einer einfachen Logik umleiten. Angenommen, wir müssen 40 Hauptspeicherpositionen, die sequenziell von 0 bis 39 nummeriert sind, auf 10 Cache-Positionen umleiten, die von 0 bis 9 nummeriert sind, die Cache-Position für eine Speicherposition n kann n%10 sein. Also entspricht 21 1, 37 entspricht 7, usw. Das wird der Index.

Aber 37, 17, 7 entsprechen alle 7. Um zwischen ihnen zu unterscheiden, kommt das Tag. Also wie der Index n%10 ist, ist das Tag int(n/10). Jetzt haben 37, 17, 7 denselben Index 7, aber unterschiedliche Tags wie 3, 1, 0, usw. Das heißt, die Zuordnung kann komplett durch die beiden Daten - Tag und Index - spezifiziert werden.

Also, wenn eine Anforderung für die Adressposition 29 eingeht, wird dies zu einem Tag von 2 und einem Index von 9. Der Index entspricht der Cache-Positionsnummer, daher wird die Cache-Position Nr. 9 überprüft, um zu sehen, ob dort Daten vorhanden sind, und wenn ja, ob das zugehörige Tag 2 ist. Wenn ja, handelt es sich um einen CPU-Treffer und die Daten werden sofort von diesem Ort abgerufen. Wenn es leer ist oder das Tag nicht 2 ist, bedeutet dies, dass es die Daten zu einer anderen Speicheradresse enthält und nicht zu 29 (obwohl es denselben Index enthält, was bedeutet, dass es Daten von Adressen wie 9, 19, 39, usw. enthält). Es handelt sich also um einen CPU-Fehler und die Daten von Standort Nr. 29 im Hauptspeicher müssen in den Cache an Standort 9 geladen werden (und das Tag wird zu 2 geändert und alle zuvor vorhandenen Daten gelöscht), wonach sie von der CPU abgerufen werden.

Answer 2

Nehmen wir ein Beispiel. Ein 64 Kilobyte Cache mit 16 Byte Cache-Zeilen hat 4096 verschiedene Cache-Zeilen.

Sie müssen die Adresse in drei verschiedene Teile aufteilen.

1. Die niedrigsten Bits dienen dazu, Ihnen den Byte innerhalb einer Cache-Zeile mitzuteilen, wenn Sie sie zurückbekommen. Dieser Teil wird nicht direkt für den Cache-Lookup verwendet. (Bits 0-3 in diesem Beispiel)
2. Die nächsten Bits dienen dazu, den Cache zu INDEXIEREN. Wenn Sie den Cache als eine große Spalte von Cachelinien betrachten, geben Ihnen die Indexbits an, in welcher Zeile Sie nach Ihren Daten suchen müssen. (Bits 4-15 in diesem Beispiel)
3. Alle anderen Bits sind TAG-Bits. Diese Bits werden im Tag-Speicher für die Daten gespeichert, die im Cache gespeichert sind, und wir vergleichen die entsprechenden Bits der Cache-Anfrage mit dem, was wir gespeichert haben, um herauszufinden, ob die Daten, die wir cachen, die angeforderten Daten sind.

Die Anzahl der Bits, die Sie für den Index verwenden, beträgt log_base_2(Anzahl der Cache-Zeilen) [es ist wirklich die Anzahl der Sets, aber in einem direkt zugeordneten Cache gibt es die gleiche Anzahl von Zeilen und Sets]

Answer 3

Ein direkt zugeordneter Cache ist wie eine Tabelle, die Zeilen hat, die auch als Cache-Zeilen bezeichnet werden, und mindestens 2 Spalten, eine für die Daten und die andere für die Tags.

So funktioniert es: Ein Lesezugriff auf den Cache nimmt den mittleren Teil der Adresse, der Index genannt wird, und verwendet ihn als Zeilennummer. Die Daten und der Tag werden gleichzeitig nachgeschlagen. Als nächstes muss der Tag mit dem oberen Teil der Adresse verglichen werden, um zu entscheiden, ob die Zeile aus demselben Adressbereich im Speicher stammt und gültig ist. Gleichzeitig kann der untere Teil der Adresse verwendet werden, um die angeforderten Daten aus der Cache-Zeile auszuwählen (Ich gehe davon aus, dass eine Cache-Zeile Daten für mehrere Wörter speichern kann).

Ich habe etwas darauf hingewiesen, dass der Datenzugriff und der Tag-Zugriff + Vergleich gleichzeitig erfolgen, denn das ist entscheidend, um die Latenz zu reduzieren (Zweck eines Caches). Der Datenpfad-RAM-Zugriff muss nicht in zwei Schritten erfolgen.

Der Vorteil ist, dass ein Lesezugriff im Grunde genommen nur eine einfache Tabellensuche und einen Vergleich ist.

Aber es ist direkt zugeordnet, was bedeutet, dass für jede Leseadresse genau ein Ort im Cache vorhanden ist, an dem diese Daten zwischengespeichert werden könnten. Der Nachteil ist jedoch, dass viele andere Adressen auf denselben Ort abgebildet werden und um diese Cache-Zeile konkurrieren können.

Answer 4

Ich habe ein gutes Buch in der Bibliothek gefunden, das mir die klare Erklärung geboten hat, die ich brauchte, und ich werde sie jetzt hier teilen, falls ein anderer Student beim Suchen über Caches auf diesen Thread stößt.

Das Buch ist "Computerarchitektur - Ein quantitativer Ansatz" 3. Auflage von Hennesy und Patterson, Seite 390.

Zunächst einmal gilt zu beachten, dass der Hauptspeicher in Blöcke für den Cache aufgeteilt ist. Wenn wir einen 64-Byte-Cache und 1 GB RAM haben, würde der RAM in 128 KB Blöcke aufgeteilt werden (1 GB RAM / 64B Cache = 128 KB Blockgröße).

Aus dem Buch:

Wo kann ein Block im Cache platziert werden?

• Wenn jeder Block nur an einer Stelle im Cache erscheinen kann, wird der Cache als direkt zugeordnet bezeichnet. Der Zielblock wird mit dieser Formel berechnet: MOD

Angenommen, wir haben 32 Blöcke RAM und 8 Cacheblöcke.

Wenn wir beispielsweise Block 12 von RAM in den Cache speichern möchten, würde RAM-Block 12 in Cache-Block 4 gespeichert werden. Warum? Weil 12 / 8 = 1 Rest 4. Der Rest ist der Zielblock.

• Wenn ein Block überall im Cache platziert werden kann, wird der Cache als vollständig assoziativ bezeichnet.

• Wenn ein Block an einer eingeschränkten Anzahl von Stellen im Cache platziert werden kann, ist der Cache set assoziativ.

Im Grunde genommen ist ein Set eine Gruppe von Blöcken im Cache. Ein Block wird zunächst auf ein Set abgebildet und dann kann der Block überall im Set platziert werden.

Die Formel lautet: MOD

Angenommen, wir haben 32 Blöcke RAM und einen Cache, der in 4 Sets unterteilt ist (jedes Set mit zwei Blöcken, also insgesamt 8 Blöcken). Auf diese Weise würde Set 0 Blöcke 0 und 1 enthalten, Set 1 Blöcke 2 und 3, usw...

Wenn wir RAM-Block 12 in den Cache speichern möchten, wird der RAM-Block in Cache-Block 0 oder 1 gespeichert. Warum? Weil 12 / 4 = 3 Rest 0. Daher wird Set 0 ausgewählt und der Block kann überall in Set 0 platziert werden (also Block 0 und 1).

Jetzt werde ich zu meinem ursprünglichen Problem mit den Adressen zurückkehren.

Wie wird ein Block gefunden, wenn er sich im Cache befindet?

Jeder Blockrahmen im Cache hat eine Adresse. Nur zur Klarstellung, ein Block hat sowohl eine Adresse als auch Daten.

Die Blockadresse ist in mehrere Teile unterteilt: Tag, Index und Offset.

Der Tag wird verwendet, um den Block im Cache zu finden, der Index zeigt nur das Set an, in dem sich der Block befindet (was ziemlich überflüssig ist) und der Offset wird verwendet, um die Daten auszuwählen.

Mit "Daten auswählen" meine ich, dass in einem Cacheblock offensichtlich mehr als eine Speicherstelle vorhanden ist, der Offset wird verwendet, um zwischen ihnen zu wählen.

Wenn Sie sich also eine Tabelle vorstellen möchten, wären dies die Spalten:

TAG | INDEX | OFFSET | DATA 1 | DATA 2 | ... | DATA N

Der Tag würde verwendet, um den Block zu finden, der Index würde zeigen, in welchem Set sich der Block befindet, der Offset würde eines der Felder rechts davon auswählen.

Ich hoffe, dass mein Verständnis davon korrekt ist, wenn nicht, lassen Sie es mich bitte wissen.