Cache-Trefferrate für einen Satz-assoziativen Cache: Ich verstehe dieses Diagramm nicht

Question

Der Titel möglicherweise nicht sehr gut, aber ich konnte keinen besseren finden.

Wir hatten Hausaufgaben zu tun und ich gab es nicht, weil ich es nicht verstanden habe. Jetzt, da es vorbei ist, haben wir die Lösungen ... Und jetzt versuche ich, die Aufgabe mit den Lösungen zu verstehen, weil der Versuch, das komplizierte Skript unseres Professors zu verstehen, Zeitverschwendung für mich ist.

---

Die Aufgabe:

Wir haben einen direkt abgebildeten Cache mit folgenden Zugriffshäufigkeit auf Haupt Speicherblöcke:

2 5 0 13 2 5 10 8 0 4 5 2 

Was ist das schlagende Zitat (aka Trefferquote), wenn die Cache ist ein Set-assoziative Cache mit der Größe 4 und FIFO?

Von my last question about direct-mapped caches habe ich gelernt, wie man das Hit-Zitat zählt und wollte sagen, vielen Dank dafür übrigens. Mein einziges Problem dafür ist, dass ich nicht verstehe, wie die Zahlen in der Tabelle so platziert werden.

Ich dachte wie Programmierung vielleicht: 0-3 ist Array1 und andere 0-3 ist Array2. Wir nehmen die erste Nummer des Caches, 2, und setzen sie in array1, also in array1 [0]. Dann machen wir dasselbe für die nächste Zahl, nehmen 5 und setzen es in array2 [0]. Nimm nun die nächste Nummer 0 und setze das Array [1].

Aber wie es scheint das Muster falsch ist, dann ist es richtig, bis Zeile 4 der Tabelle, aber dann ist es falsch ...

Warum sind die Zahlen wie in der Tabelle platziert?

Lösung:

Answer 1

Sie fragen sich wahrscheinlich, warum die Zahlen nicht mit den Adressen in einer Reihe aufstellen, wie es in dem direkt abgebildeten Fall. Was in diesem Diagramm passiert, ist, dass die Elemente in den Sets von links nach rechts platziert werden, das ist alles, weil die Sets anfänglich leer sind. Die Werte 2, 0, 10 und 8 bilden den linken Satz ab. Die 2 erscheint zuerst, also in der Spalte ganz links. Dann wird 0 an der nächsten verfügbaren Position platziert. 2 tritt wieder auf, und das ist ein "Treffer", der durch die Klammern angezeigt wird. Dann tritt 10 auf und geht in den dritten Punkt. 8 geht zum vierten Punkt und der Cache-Block ist jetzt voll. 0 wiederholt sich, und es gibt einen Treffer, da es immer noch im Cache ist, an der zweiten Stelle. Jetzt kommt 4 vor. Der Cache ist voll: Etwas muss rausgeschmissen werden. Die 2 wird gelöscht (möglicherweise aufgrund einer LRU-Ersatzrichtlinie) und durch 4 ersetzt. Deshalb befindet sich die 4 in der Spalte ganz links; es hat die 2. ersetzt. Jetzt tritt 2 wieder auf und ist nicht mehr im Cache, da es gerade rausgeschmissen wurde. Jetzt ist das zuletzt verwendete Cache-Item 0, also wird es rausgeschmissen und 2 lebt jetzt an der zweiten Stelle.

Beachten Sie, dass reelle assoziative Vierwege-Caches nicht immer eine vollständige blockübergreifende LRU-Ersatzrichtlinie verwenden, da sie durch einige weitere Vereinfachungen beschleunigt werden.

Und übrigens sind die Adressen in die Sätze nach einfachen Modulo 4 verteilt.Es ist nicht der Fall, dass sogar Adressen nach links gehen gesetzt und ungerade nach rechts:

set 0    set 1 
0 1 2 3 | 0 1 2 3 <- addr modulo 4 
---------------+----------------- 
0 1 2 3 | 4 5 6 7 <- full addr 
8 9 10 11 | 12 13 14 15 

Wie Sie sehen können, ist dies im Einklang mit dem, was in der Tabelle ist; außer natürlich, dass die Adressen nicht mit ihrer Modulo 4-Position übereinstimmen: Sie erhalten einen beliebigen Punkt in jedem Satz basierend auf der Ersetzungsrichtlinie.