Cache-Organisation und -Strategien

Die Cache-Organisation befasst sich damit, wie ein Cache Speicherblöcke dem Speicher zuordnet – deren Platzierung und Assoziativität – sowie mit den Strategien, die den Austausch und die Schreibvorgänge regeln. Zusammen bestimmen diese, wie oft der Cache trifft und wie er mit dem Hauptspeicher interagiert.

Definition

Cache-Organisation und -Strategien sind die strukturellen und verwaltungstechnischen Entscheidungen eines Caches – wo Blöcke platziert werden dürfen, welcher Block bei einem Miss verdrängt wird und wie Schreibvorgänge an untergeordnete Ebenen weitergegeben werden –, die seine Trefferrate und sein Verhalten bestimmen.

Scope

Dieses Thema behandelt den internen Aufbau eines einzelnen Caches: direkt-abgebildete, set-assoziative und voll-assoziative Platzierung; Ersetzungsstrategien wie LRU und deren Annäherungen; Schreibstrategien (Write-Through versus Write-Back) und Write-Allocation; Blockgröße; und die Klassifizierung von Misses in Compulsory, Capacity und Conflict. Es schließt Multi-Cache-Kohärenz (Cache-Kohärenzprotokolle) und Adressübersetzung (virtueller Speicher und Paging) aus.

Core questions

• Wie unterscheiden sich direkt-abgebildete, set-assoziative und voll-assoziative Platzierung in Bezug auf Kosten und Konfliktverhalten?
• Welche Ersetzungsstrategie sollte einen Block bei einem Miss verdrängen, und wie wird sie kostengünstig angenähert?
• Wie unterscheiden sich Write-Through- und Write-Back-Strategien in Bezug auf Datenverkehr und Komplexität?
• Wie werden Misses klassifiziert, und welche Designänderungen reduzieren jede Art?

Key concepts

• direkt-abgebildeter Cache
• set-assoziativer Cache
• voll-assoziativer Cache
• Least-Recently-Used (LRU) Ersetzung
• Write-Through vs. Write-Back
• Write-Allocate
• Blockgröße (Line Size)
• Compulsory-, Capacity- und Conflict-Misses

Key theories

Drei-Cs-Miss-Modell

Cache-Misses können als Compulsory (erster Zugriff), Capacity (Cache zu klein für den Arbeitssatz) und Conflict (zu geringe Assoziativität) kategorisiert werden, ein Rahmenwerk, das jeden Designparameter – Größe, Blockgröße, Assoziativität – mit den Misses verknüpft, die er reduziert.

Mechanisms

Eine Speicheradresse wird in Tag-, Index- und Offset-Felder aufgeteilt. Der Index wählt ein Set aus, der Tag identifiziert den Block darin, und die Assoziativität legt fest, wie viele Blöcke sich ein Set teilen. Bei einem Miss holt der Cache den Block und verdrängt einen anderen, der durch eine Ersetzungsstrategie (oft eine Annäherung an Least-Recently-Used) ausgewählt wird. Schreibvorgänge aktualisieren entweder den Hauptspeicher sofort (Write-Through) oder markieren den Block als 'dirty' und verschieben die Aktualisierung (Write-Back).

Clinical relevance

Die Cache-Organisation bestimmt die effektive Leistung, da die Kosten für Misses im Vergleich zu Treffern hoch sind. Programmierer verbessern das Cache-Verhalten durch Datenlayout, Blocking und Zugriffsmuster, die die Lokalität erhöhen, während Architekten Assoziativität, Blockgröße und Schreibstrategie anpassen, um die Trefferrate gegen Fläche, Leistung und Bandbreite abzuwägen.

History

Wilkes schlug 1965 den Slave-Speicher (Cache) vor, und Caches wurden bald kommerziell eingesetzt. Alan Jay Smiths Studie von 1982 synthetisierte umfangreiche Messungen zu Platzierungs-, Ersetzungs- und Schreibstrategien und etablierte das noch heute verwendete Designvokabular. Das Drei-Cs-Modell lieferte später eine strukturierte Methode, um über die Ursachen und Abhilfen von Misses nachzudenken.

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

Was ist der Unterschied zwischen Write-Through- und Write-Back-Caches?

Ein Write-Through-Cache aktualisiert bei jedem Schreibvorgang sowohl den Cache als auch den Hauptspeicher, wodurch der Speicher aktuell bleibt, aber mehr Datenverkehr erzeugt wird. Ein Write-Back-Cache aktualisiert nur den Cache, markiert den Block als 'dirty' und schreibt ihn erst bei der Verdrängung in den Speicher, was den Datenverkehr auf Kosten zusätzlicher Buchhaltung reduziert.

Warum werden set-assoziative anstelle von direkt-abgebildeten Caches verwendet?

Ein direkt-abgebildeter Cache erlaubt jedem Block genau eine Position, sodass Blöcke, die auf denselben Slot abgebildet werden, in Konflikt geraten. Die Set-Assoziativität gibt jedem Block mehrere mögliche Positionen innerhalb eines Sets, wodurch Konflikt-Misses reduziert werden, allerdings auf Kosten von mehr Vergleichshardware und leicht langsameren Treffern.