Speichersysteme - Rechneraufbau und Rechnerarchitektur - page 138

Die einfachsten derartigen Verdrangungsstrategien bestehen darin, Blocke im
Set nacheinander auszuwahlen ( sequential ) oder zufallig ( random ).
Da aber der Zweck eines Cache darin besteht, haufig benutzte Daten schnell
verfugbar zu halten, erscheint es sinnvoll, den schon am langsten nicht mehr
verwendeten Eintrag zu verdrangen. Solche Strategien nennen sich Least-
Recently Used oder auch Least-Frequently Used . Diese Strategie erfordert
zusatzliche Zahler, die entweder die Zugriffshaufigkeit auf jeden einzelnen
Cache-Block speichern oder die Reihenfolge, in der die Zugriffe auf die Blocke
innerhalb des Set stattgefunden haben. Die Zugriffshaufigkeit zu vermerken
ist unpraktikabel, weil das einen zusatzlichen Sortierschritt erfordert. Es gibt
n != n· 1mogliche Reihenfolgen, die bei diesem Verfahren zu

berucksichtigen sind. Also mussten je Set log 2 ( n !) Bits vorgesehen werden,
um die aktuell vorliegende Zugriffsreihenfolge zu kodieren. Das entspricht
funf Bits bei 4-Wege assoziativen Caches und bereits 16 Bits bei 8-Wege
Assoziativitat.
Dieses Verfahren ist sehr aufwandig in Hardware zu implementieren, da bei
jedem Zugriff die gespeicherte Zugriffsreihenfolge kompliziert zu andern ist.
Daher wird in der Praxis oft ein Verfahren eingesetzt, das zwar einfacher
zu implementieren ist, aber nicht immer den tatsachlich am langsten unbe-
nutzten Eintrag liefert. Das Verfahren heißt Pseudo-LRU .Esspeichertzu
jedem Set einen Vektor mit 2 a −

( n− 1) · ( n− 2) ·...·

1Bits,den Pseudo-LRU-Bits .Betrachten
Sie beim Lesen der folgenden Erklarung bitte Abbildung 7.12. Man stellt sich
vor, dass die Blocke eines Sets a -Mal sukzessive in zwei Teilmengen aufgeteilt
werden. Ein gesuchter Block muss sich jeweils in einer der beiden Teilmengen
befinden. Jedes der Pseudo-LRU-Bits dient in einem der Teilungsschritte als
Merker, in welcher Teilmenge sich der zuletzt gesuchte Block befand (Wert 0
fur erste Teilmenge, Wert 1 fur zweite Teilmenge).
Abbildung 7.12 demonstriert dieses Verfahren fur einen 8-Wege assoziativen
Cache ( a =3).JeSetgibtesachtBlocke. Zusatzlich wird je Set ein Vektor
mit sieben Pseudo-LRU-Bits gespeichert. Eine 0 zeigt an, dass an der Position
der letzte Zugriff in die linke Teilmenge erfolgte.
Fur die Belegung (1 , 0 , 0 , 1 , 0 , 1 , 1) des Vektors mit den LRU-Bits suchen wir
nun einen zu verdrangenden Block. Wir stellen fest, dass das erste Bit (von
links beginnend) 1 ist. Also erfolgte der letzte Zugriff in die rechte Teilmenge
(Blocke 4 bis 7). Ein zu verdrangender Block muss also in der linkenTeilmenge
gesucht werden. Wir betrachten daher als nachstes das LRU-Bit 2 (zweites
von links). Dieses ist 0, also erfolgte der letzte Zugriff in diesem Bereich auf
einen der Blocke 0 oder 1. Verdrangt werden muss somit einer der Blocke 2
oder 3. LRU-Bit 5 ist 0 und zeigt an, dass wir Block 3 verdrangen mussen.
Wird dann also Block 3 verdrangt, so sind die LRU-Bits zu aktualisieren. Sie
mussen signalisieren, dass der nunmehr letzte Zugriff auf Block 3 erfolgte. Es