Skalare Prozessoren - Moderne Prozessorarchitekturen: Prinzipien und ihre Realisierungen - page 155

Umgekehrt lässt sich der Eintrag, auf den die längste Zeit nicht mehr zugegriffen
wurde, dadurch ermitteln, dass nach einer Zeile im Cache gesucht wird, die in der
zugeordneten Spalte nur Nullen und in der zugeordneten Reihe nur Einsen enthält.
Dies gilt in Bild 2.62a für Cache-Zeile 3, wobei Einsen hier nicht berücksichtigt
werden müssen, weil die Reihe 3 der Dreiecksmatrix keine Bits enthält. - Weitere
Modifikationen sind in Bild 2.62b bis 2.62d dargestellt. Der jeweils älteste Eintrag
ist am oberen Bildrand durch einen beschrifteten Pfeil gekennzeichnet.

älteste Zeile älteste Zeile älteste Zeile älteste Zeile

Zugriff Zugriff Zugriff Zugriff

0
1
2
3

1 0 0

0

0
1
2
3

1 0 1

1

0
1
2
3

0 0 0

1

0
1
2
3

0 1 0

1 0 0 0 1

0 1 1 0

0123 0123 0123 0123

a b c d

n 0 Cache-Zeile n jünger als Cache-Zeile m n 1 Cache-Zeile n älter als Cache-Zeile m

m m

Bild 2.62. LRU-Dreiecksmatrix für einen einzelnen Satz eines 4-fach assoziativen Caches, darge-
stellt jeweils nach Zugriffen auf die Zeilen 2, 4, 1 und 3 (von links nach rechts)

Bemerkung. Das LRU-Verfahren besitzt einen quadratischen Realisierungsaufwand und ist des-
halb schlecht geeignet, wenn die Anzahl der gleichzeitig zu berücksichtigenden Zeilen sehr groß
ist. So werden für einen vollassoziativen Cache mit 256 Zeilen z.B. 32640 Bits benötigt. Aus die-
sem Grund wird das LRU-Verfahren vor allem in n-fach assoziativen Caches mit n zwischen Zwei
und Acht verwendet, wobei mit n gleich Acht bereits 28 Bit pro Satz benötigt werden.
Eine Verminderung des Speicherbedarfs lässt sich für n ≥ 4 erreichen, indem man die Bits der Drei-
ecksmatrix umcodiert. Zum Beispiel sind für einen 4-fach assoziativen Cache entsprechend Bild
2.62 pro Satz sechs Bit erforderlich, so dass theoretisch 64 Altersrelationen codierbar sind. Tatsäch-
lich können zwischen vier unterschiedlichen Zeilen jedoch nur 4!, also 24 mögliche Altersrelatio-
nen auftreten, die in fünf Bit vollständig codierbar wären. Pro Satz kann also ein Bit eingespart wer-
den. Bei einem 8-fach assoziativen Cache reduziert sich der Speicherbedarf pro Satz sogar von 28
auf 16 Bits. Allerdings ist die Ansteuerung der Bits in der codierten Dreiecksmatrix deutlich kom-
plexer als bei einer direkten Umsetzung des Verfahrens (weitere Codierungsmöglichkeiten werden
in [98, 46] beschrieben).

PLRU (pseudo least recently used). Das LRU lässt sich durch das PLRU-Verfah-
ren mit deutlich geringerem Realisierungsaufwand in seinem Verhalten näherungs-
weise nachbilden. Hierzu fasst man jeweils zwei Zeilen zu Gruppen zusammen, von
denen man sukzessive zwei zu neuen Gruppen zusammenfasst usw., bis schließlich
nur noch eine Gruppe verbleibt. Jede dieser Gruppen bekommt ein LRU-Bit zuge-
ordnet, dass anzeigt, auf welche der untergeordneten Gruppen bzw. Zeilen zuletzt
zugegriffen wurde.

Ein in dieser Weise realisierter Baum ist für einen Satz eines 8-fach assoziativen
Caches in Bild 2.63 dargestellt. Bei einem Zugriff werden alle LRU-Bits, die zwi-