Direkt abgebildeter vs. satzassoziativer vs. vollassoziativer Cache

Ein Cache muss entscheiden, wo jeder Speicherblock abgelegt werden darf. In einem direkt abgebildeten Cache hat jeder Block genau eine mögliche Zeile, was einfach und schnell ist, aber zu Konflikten führt, wenn zwei Blöcke dieselbe Zeile belegen. In einem vollassoziativen Cache kann ein Block überall liegen, was Konflikte vermeidet, aber einen Vergleich mit jeder Zeile erfordert. Ein satzassoziativer Cache ist der Kompromiss: Ein Block kann in einem von wenigen Wegen innerhalb eines Satzes liegen. Die meisten CPU-Caches sind satzassoziativ.

Aspekt	Direkt abgebildet	Satzassoziativ	Vollassoziativ
Wo ein Block liegen kann	In genau einer Zeile, bestimmt durch die Index-Bits	In einem der Wege (zum Beispiel 4 oder 8) eines Satzes	In jeder Zeile des Caches
Tag-Vergleiche pro Zugriff	Einer	Einer pro Weg (zum Beispiel 8)	Alle Zeilen gleichzeitig, parallel
Trefferzeit	Am schnellsten	Etwas langsamer	Am langsamsten
Hardwarekosten und Leistungsaufnahme	Am niedrigsten	Mittel	Am höchsten: ein Komparator für jede Zeile
Konfliktfehlzugriffe	Am häufigsten	Nehmen mit der Zahl der Wege ab	Keine: Es bleiben nur Compulsory- und Kapazitätsfehlzugriffe
Ersetzungsstrategie	Nicht nötig: nur eine Möglichkeit	Innerhalb des Satzes gewählt (LRU oder Näherungen)	Unter allen Zeilen gewählt
Typische Einsatzgebiete	Kleine, einfache Caches und einige Mikrocontroller	L1-, L2- und L3-Caches in den meisten CPUs, meist mit 4 bis 16 Wegen	Kleine Strukturen wie TLBs und Victim-Caches

Die Zahlenangaben sind typische Größenordnungen und variieren je nach Prozessgeneration und Produkt.

Wann welches einsetzen

Direkt abgebildet: Wenn Einfachheit, geringe Leistungsaufnahme und Geschwindigkeit wichtiger sind als die Trefferrate.
Satzassoziativ: Die praktische Wahl für die meisten Caches, da wenige Wege die meisten Konfliktfehlzugriffe bei moderaten Kosten beseitigen.
Vollassoziativ: Für sehr kleine Strukturen, bei denen die Trefferrate entscheidend ist und der Vergleichsaufwand vertretbar ist.

FAQ

Was ist ein Konfliktfehlzugriff?

Ein Fehlzugriff, der auftritt, weil zwei Blöcke auf dieselbe Stelle abgebildet werden, obwohl andere Cache-Zeilen frei sind. Direkt abgebildete Caches leiden am meisten darunter, vollassoziative haben keine.

Wie viele Tags vergleicht ein 8-Wege-Cache pro Zugriff?

Acht, einen für jeden Weg des ausgewählten Satzes.

Warum sind die meisten CPU-Caches satzassoziativ?

Wenige Wege beseitigen die meisten Konfliktfehlzugriffe bei moderaten Kosten, während ein vollassoziativer Cache für jede Zeile einen Komparator benötigt.

Wo wird ein vollassoziativer Cache eingesetzt?

In kleinen Strukturen wie TLBs und Victim-Caches, wo die Trefferrate am wichtigsten ist und der Vergleichsaufwand vertretbar ist.

Wichtige Begriffe erklärt

Direkt abgebildeter Cache (Direct-Mapped): Cache-Organisation, in der jede Adresse an genau einer Stelle abgelegt werden kann. Sie ist einfach und hat eine kurze Trefferzeit, neigt aber zu Konfliktfehlzugriffen, wenn Adressen um denselben Platz konkurrieren.
Mengenassoziativer Cache (Set-Associative): Cache-Organisation, in der Daten an einer von mehreren Stellen (Ways) innerhalb der einen, durch die Adresse gewählten Menge abgelegt werden können. Ein n-Wege-Cache vergleicht bei jedem Zugriff n Tags parallel.
Vollassoziativer Cache (Fully Associative): Cache-Organisation, in der beliebige Daten an beliebiger Stelle abgelegt werden können. Es gibt keine Konfliktfehlzugriffe, aber es muss mit jedem Tag verglichen werden, weshalb sie sich für kleine Strukturen wie TLBs eignet, nicht für große Caches.
Cache-Zeile (Cache Line): Die Einheit, in der Daten zwischen einem Cache und der darunterliegenden Ebene bewegt werden, auch Cache-Block genannt. Viele CPUs verwenden 64 Byte; die niederwertigen Adressbits geben die Position (Offset) in der Zeile an.