Assoziativ-Cache-Simulation - Der Umgang mit einem fehlerhaften Schema

Question

Während der Arbeit an einem vollständig assoziativen Cache-Simulation (in MIPS Assembly), ein paar Fragen kamen Grundlage Geist auf einige Informationen online lesen;

Nach einigen Anmerkungen von der University of Maryland

  

Finding a slot: Allenfalls sollte ein Steckplatz passen. Wenn   Gibt es mehr als einen Schlitzes, dass   Streichhölzer, dann haben Sie eine fehlerhafte   voll-assoziatives Cache-Schema. Du   sollte nie mehr als eine Kopie haben   der Cache-Zeile in jedem Schlitz eines   vollständig assoziative Cache. Es ist schwer zu   mehrere Kopien halten und nicht   Sinn ergeben. Die Schlitze könnten verwendet werden,   für andere Cache-Zeilen.

Heißt das, dass ich alle die ganze Tag-Liste, die Zeit, um für ein zweites Spiel zu überprüfen, überprüfen sollte? Denn wenn ich dies nicht tun, werde ich nie „Realize“ über den Fehler mit dem Cache, doch scheint jedes Mal überprüft ziemlich ineffizient.

Im Fall, dass ich Kontrolle tun, und irgendwie schaffe ich es ein zweites Spiel zu finden, fehlerhafte Cache-Schema bedeutet, was soll ich dann tun? Auch wenn die beste Antwort wäre meine Implementierung zu beheben, noch Ich bin interessiert, wie es während der Ausführung zu behandeln, wenn diese Situation entstehen sollte.

Answer 1

Wenn mehr als ein gültiger Steckplatz passt eine Adresse, dann das bedeutet, dass, wenn eine vorherige Suche nach derselben Adresse ausgeführt wurde, entweder ein gültiger Steckplatz, der die Adresse angepasst haben, sollten nicht verwendet wurde (vielleicht, weil es nicht in der geprüft wurde zunächst) oder mehr als ein ungültiger Slot wurde verwendet, um die Zeile zu speichern, die nicht in dem Cache-Speicher überhaupt war.

Ohne Zweifel, sollte dies einen Fehler in Betracht gezogen werden.

Aber wenn wir gerade entschieden haben, nicht den Fehler zu beheben (vielleicht würden wir lieber begehen nicht so viel Hardware zu einer besseren Umsetzung) die naheliegendste Option ist einer der Schlitze zu entkräften holen. Es wird dann für andere Cache-Zeilen zur Verfügung.

Was, wie die man zu entkräften holen, wenn eine der doppelten Linien sauber ist, entkräften, dass man den Vorzug vor einem schmutzigen Cache-Zeile. Wenn mehr als Cache-Zeile ist schmutzig und sie nicht einverstanden Sie haben einen noch größeren Fehler zu beheben, aber auf jeden Fall ist der Cache synchron und es tut wahrscheinlich keine Rolle, was Sie wählen.

Edit: hier ist, wie ich Hardware implementieren könnte, dies zu tun:

Zunächst einmal ist es nicht eine ganze Menge Sinn machen, Start mit der Annahme von Duplikaten, sondern wir arbeiten rund um die später zu gegebener Zeit. Es gibt ein paar Möglichkeiten, was passieren muss, wenn eine neue Zeile Caching.

• Die Linie ist bereits im Cache, wird keine Aktion erforderlich
• Die Linie ist nicht im Cache, aber es gibt ungültige Slots zur Verfügung: Setzen Sie die neue Zeile in eine der verfügbaren Slots
• Die Linie ist nicht im Cache, aber es gibt keine ungültigen Slots zur Verfügung. Eine weitere gültige Zeile muss geräumt werden und die neue Linie nimmt seinen Platz ein.
  
  • hat einen Räumungs Kandidat Kommissionierleistung Folgen. Saubere Cache-Zeilen können sein Evicted kostenlos, aber wenn schlecht gewählt, kann es eine andere Cache-Miss in naher Zukunft führen. Überlegen Sie, ob alle bis auf eine Cache-Zeile ist verschmutzt. Wenn nur die saubere Cache-Zeile geräumt, so viele sequentielle liest abwechselnd zwischen zwei Adressen einer Cache-Miss auf jeder Lese verursachen. Cache-Annullierungs gehört zu den zwei hart Problemen in Comp Sci (die anderen ‚Namensgebung Dinge‘) und aus dem Anwendungsbereich dieser genauen Frage.

Ich würde wahrscheinlich eine Suche durchführen, dass die Kontrollen für den richtigen Steckplatz für jede dieser auf handeln. Dann würde ein weiterer Block die erste aus dieser Liste auswählen und auf ihn einwirken.

Nun, immer auf die Frage zurück. Was sind die Bedingungen, unter denen Duplikate möglicherweise den Cache eingeben könnte. Wenn Speicherzugriffe streng geordnet sind, und die Umsetzung (wie oben) richtig ist, glaube ich nicht, Duplikate überhaupt möglich sind. Und so gibt es keine Notwendigkeit für sie zu überprüfen.

Jetzt kann einen unplausible Fall betrachten, wo ein einzelner Cache über zwei CPU-Kerne gemeinsam genutzt wird. Wir werden nur die einfachste Sache zu tun, das und doppelt alles außer dem Cache-Speicher selbst für jeden Kern funktionieren könnte. So ist die Slot-Hardware suchen ist nicht geteilt. Um dies zu unterstützen, wird ein zusätzliches Bit pro Schlitz als Mutex verwendet. Suche Hardware kann keinen Slot verwenden, die von dem anderen Kern gesperrt ist. Insbesondere

• Wenn die Adresse im Cache ist, versuchen, den Schlitz zu verriegeln und diesen Schlitz zurück. Wenn der Schlitz bereits gesperrt ist, Stall , bis sie frei ist.
• Wenn die Adresse nicht im Cache ist, finden eine entriegelten Steckplatz, ungültig oder gültig ist, aber evictable.

In diesem Fall können wir tatsächlich bis in einer Position enden, wo zwei Schlitze die gleiche Adresse teilen. Wenn beide Kerne versuchen, eine Adresse zu schreiben, die nicht im Cache ist, werden sie immer verschiedene Slots am Ende, und eine doppelte Linie auftreten. Zunächst lässt darüber nachdenken, was passieren könnte:

• Beide Linien waren liest aus dem Hauptspeicher. Sie werden der gleiche Wert sein, und sie werden beide sauber sein. Es ist richtig, zu evict auch nicht.
• waren Beiden Linien schreiben. Beide werden schmutzig sein, aber wahrscheinlichnicht gleich sein. Dies ist eine Race-Bedingung, die durch die Ausgabe von Speicher Zäunen oder einige andere Speicherordnungs Anweisungen von der Anwendung aufgelöst werden sollte. Wir können nicht erraten, welche verwendet werden soll, wenn kein Cache war die Race-Bedingung in dem RAM bestehen bleiben würde. Es ist richtig, zu evict auch nicht.
• war eine Zeile ein Lese und man war ein Schreib. Die Schreib ist schmutzig, aber die Lese ist sauber. Wieder einmal würde dieses Rennen Zustand verharrte in dem RAM hat, wenn es keine dazwischen liegende Cache war, aber der Leser hätte einen anderen Wert zu sehen. die saubere Linie evicting ist direkt RAM und hat auch den Nebeneffekt, immer dann Schreibreihenfolge lesen begünstigende.

wir also jetzt wissen, was zu tun ist, aber woher kommen diese Logik gehört. Zunächst lässt darüber nachdenken, was passieren könnte, wenn wir nichts tun. Ein nachfolgender Cache-Zugriff für die gleiche Adresse auf beiden Kernen könnte so oder Linie zurück. Auch wenn weder Kern schreibt ausgibt, liest halten könnte anders kommen, im Wechsel zwischen den beiden Werten. Dies bricht jede denkbare Idee über Speicherordnungs.

eine Lösung nur sein könnte, dass schmutzigen Linien nur einen Kern gehören zu sagen, die Linie nicht verschmutzt ist, aber schmutzig und von einem anderen Kern gehört.

• Im Falle von zwei gleichzeitig liest, beide Linien identisch sind, entriegelt und austauschbar. Es spielt keine Rolle, welche Linie ein Kern für nachfolgende Operationen bekommt.
• im Fall der gleichzeitigen schreibt, sind beide Leitungen synchron, aber für beide Seiten unsichtbar. Obwohl die Race-Bedingung, dass dies schafft, ist bedauerlich, es immer noch führt zu einer vernünftigen Speicherordnung, als ob alle Operationen, die vor einem der Operationen auf der gereinigten Linie auf der Linie verworfen passiert passieren.
• Wenn ein Lese- und ein Schreib gleichzeitig geschieht, ist die schmutzige Linie zum Lese Kern unsichtbar. Allerdings ist die saubere Linie zu beiden Kernen sichtbar, und würde dazu führen, Speicherordnung für den Schriftsteller zu brechen. Zukunft schreibt könnte sogar dazu führen, dass beide zu sperren (weil beide schmutzig wäre).

Der letzte Fall ziemlich viel streitet, dass schmutzige Linien sauber diejenigen bevorzugt werden. Diese Kräfte zumindest einige zusätzliche Hardware sucht schmutzige Linien erste und klare Linien nur, wenn keine schmutzigen Zeilen gefunden wurden. So, jetzt haben wir eine neue gleichzeitige Cache-Implementierung:

• Wenn die Adresse im Cache und schmutzig ist und von dem anfordernden Kern gehört, verwenden Sie diesen Steckplatz
• wenn die Adresse im Cache, aber sauber
  • für liest, benutzen Sie einfach diesen Schlitz
  • für schreibt, den Schlitz als schmutzig markiert und verwenden Sie diese Slot
• , wenn die Adresse nicht im Cache ist, und es gibt ungültige Slots verwendet eine ungültige Steckplatz
• , wenn es keine ungültigen Slots, evict eine Linie und die Nutzung, dass Slot.

Wir nähern, gibt es noch ein Loch in der Umsetzung. Was passiert, wenn beide Kerne Zugriff auf die gleiche Adresse, aber nicht gleichzeitig . Die einfachste Sache ist wahrscheinlich nur zu sagen, dass schmutzige Linien auf andere Kerne wirklich unsichtbar sind. Im Cache aber schmutzig ist das gleiche wie in dem Cache nicht überhaupt zu sein.

Nun müssen wir darüber nachdenken, tatsächlich ist das Werkzeug für Anwendungen zu synchronisieren bietet. Ich würde wahrscheinlich ein Tool tun, die nur explizit eine spült, wenn es schmutzig ist. Dies würde ruft nur die gleiche Hardware, die während der Räumung verwendet wird, sondern markiert die Linie so sauber statt ungültig.

Um einen langen Beitrag kurz zu machen, ist die Idee mit den Duplikaten beschäftigen nicht von ihnen zu entfernen, sondern, indem sichergestellt wird, können sie nicht zu weiteren Speicherordnungsproblemen führen, und das Verlassen die Deduplizierung Arbeit auf die Anwendung oder eventuelle Räumung.