Cache - Organisation

[Christoph H. (berton)]

Argggs... ich versuche hier schon seit 2 Tagen den Unterschied zwischen 
direkt abgebildeten (direct mapped), mengen-assoziativ 
(n-way-associative) und vollassoziativ (full associative) zu verstehen.
Kann mir dabei mal jemand helfen?

Was ich bisher verstanden habe:
Direct mapped bildet eine Art Modulofunktion über den Adressraum des 
Speichers.
Angenommen ich habe einen Speicheradressraum von 2^4=16 bit und mein 
Cache hat 2^3=8 bit, dann wird Speicheradresse 0 und 8 auf den Eintrag 0 
im Cache abgebildet.

Wie sieht das bei den anderen beiden Organisationsformen aus?

[Andreas K. (a-k)]

N-way set associative: Stell dir N direct mapped caches vor. 
Nebeneinander.

Fully associative: keine Einschränkungen bei der Adressabbildung. Jede 
cache line passt auf jedem entsprechend grossen Speicherblock.

[Morin (Gast)]

Direct-Mapped bildet jede Adresse auf genau einen Cache-Eintrag ab.

Set-Associative bildet jede Adresse auf mehrere Einträge ab, die es sein 
können. Entsprechend müssen die dann auch alle (möglichst gleichzeitig) 
darauf geprüft werden, ob sie das Datum denn nun wirklich enthalten -> 
mehrere Vergleicher nötig, mehr Hardwareaufwand.

Fully-Associative bildet jede Adresse auf alle Einträge ab, d.h. jeder 
Eintrag kann möglicherweise das Datum enthalten -> soviele Vergleicher 
wie Einträge nötig, großer Hardwareaufwand aber minimales Thrashing.

[Christoph H. (berton)]

Okey, soweit schon mal Danke!

Bleibt immernoch ein bischen was zu klären:

>"Set-Associative bildet jede Adresse auf mehrere Einträge ab, die es sein
>können."
So weit so gut. Ich stellt mir ein 2-fach assoziativen cache also als 
2x1-Dimensionale Direct mapped caches vor.
Was habe ich davon, wenn beide Dimensionen den selben Eintrag des 
Hauptspeichers beinhalten, oder liegt hier der Denkfehler?

[Andreas K. (a-k)]

Christoph H. wrote:

> Was habe ich davon, wenn beide Dimensionen den selben Eintrag des
> Hauptspeichers beinhalten, oder liegt hier der Denkfehler?

Bischen mitdenken ist nicht verboten. Das darf natürlich nicht 
vorkommen. Ich habe das oben etwas vereinfacht, denn natürlich kommt 
noch ein bischen Logik hinzu, die entscheidet welcher Eintrag ersetzt 
wird. Und die garnicht erst auf die Idee kommen wird, etwas zu ersetzen 
das nicht ersetzt werden muss.

[Christoph H. (berton)]

Andreas Kaiser wrote:
> Bischen mitdenken ist nicht verboten.

Okey, aber wenn man sich schon einige Zeit mit dem Thema beschäftigt 
hat, dann sieht man den Wald ... bla bla ...

> Und die garnicht erst auf die Idee kommen wird, etwas zu ersetzen
> das nicht ersetzt werden muss.

Es ergibt sich aber noch ne neue Frage:
Wie kann es sein, dass der Eintrag in der ersten Dimension nicht mit dem 
in der zweiten Dimension übereinstimmt wenn beide den Inhalt der selben 
Adresse referenzieren?
Gibt es dann nicht sowas wie Koherenz/Konsistenzverletzungen?

[Andreas K. (a-k)]

Versuch mal chronologisch vorzugehen. Fang vorneweg an, mit einem direct 
mapped cache dessen Inhalt Zeile für Zeile nix anderes sagt als 
"invalid". Dann kommt der erste Prozessorzugriff. Was passiert dann. 
Dann der zweite auf eine andere Stelle. Dann der dritte Zugriff, der 
blöderweise bei verschiedener Adresse mit dem Cacheinhalt vom ersten 
Zugriff kollidiert.

Und dann probier das gleiche mal bei einen 2-Wege Cache. Und wenn du es 
so schaffst, ein Schritt-für-Schritt Szenario zu entwickeln, in dem in 
beiden Teilen vom Cache das gleiche drinsteht, dann gratuliere!

Ja, es gibt bei Caches Kohärenzprobleme. Bei Mehrprozessorsystemen und 
bei DMA. Aber im jetzigen Stadium würde ich an deiner Stelle erstmal 
grosszügig über diese Vertiefung des Themas hinwegsehen.

[Christoph H. (berton)]

Danke a-k!
Ich habe so eben den "Set-Associative" Cache verstanden. Nur dort und 
bei Fullass. machen Ersetzungsstrategien Sinn.
Danke!