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

Die sog. Ersetzungsstrategie legt fest, in welcher Zeile der neu in den Cache zu
ladende Speicherblock einzutragen ist. Im Allgemeinen werden dabei zunächst die
als ungültig gekennzeichneten Zeilen belegt. Falls jedoch alle Zeilen gültig sind,
muss eine belegte Zeile durch den zu ladenden Speicherblock verdrängt werden.
Nach Möglichkeit wird hier die Zeile verwendet, auf die in Zukunft die längste Zeit
nicht zugegriffen werden wird. Da ein Blick in die Zukunft technisch nicht realisier-
bar ist, werden Heuristiken zur Auswahl der zu ersetzenden Zeile verwendet, die im
Durchschnitt das angestrebte nichtkausale Verhalten gut nähern.
LRU (least recently used). Normalerweise ändert sich die Weise, in der auf Inhalte
im Cache zugegriffen wird, nicht sprunghaft, sondern langsam über die Zeit. Des-
halb lässt sich das Zugriffsverhalten in der Vergangenheit nutzen, um das in der
Zukunft zu extrapolieren. Beim LRU-Verfahren wird jeweils die Zeile im Cache,
auf die zuvor die längste Zeit kein Zugriff erfolgte, ersetzt. Hierzu ordnet man
jedem Zeilenpaar eines Satzes (beim n-fach assoziativen Cache) bzw. des gesamten
Caches (beim vollassoziativen Cache) ein Bit zu, dass die Altersrelation zwischen
den Zeilen anzeigt, d.h. auf welche der beiden Zeilen die längere Zeit nicht zugegrif-
fen wurde. Für einen 2-fach assoziativen Cache ist z.B. pro Satz nur ein einzelnes
Bit erforderlich, das bei jedem Zugriff ggf. modifiziert wird und das die jeweils am
längsten nicht angesprochene Zeile des Satzes indiziert. Je mehr Zeilen berücksich-
tigt werden müssen, desto höher ist der Realisierungsaufwand.
So werden für einen 4-fach assoziativen Cache bereits sechs Bit pro Satz benötigt,
die sich in einer Dreiecksmatrix , wie sie z.B. in Bild 2.62a dargestellt ist, zusam-
menfassen lassen [98]. Die zu klassifizierenden Zeilen des Caches sind in der verti-
kalen (zur Begriffsabgrenzung wird im Folgenden von Reihen gesprochen), die als
Bezug zu verwendenden Zeilen in der horizontalen Ausrichtung dargestellt. Zum
Beispiel gibt das in Reihe 0 Spalte 1 befindliche Bit die Altersrelation zwischen den
Zeilen 0 und 1 an. Falls es gesetzt ist, bedeutet dies, dass auf Zeile 0 längere Zeit
nicht zugegriffen wurde als auf Zeile 1 (Zeile 0 ist älter als Zeile 1). Falls es umge-
kehrt gelöscht ist, wurde auf Zeile 0 später als auf Zeile 1 zugegriffen (Zeile 0 ist
jünger als Zeile 1). Bemerkt sei, dass in der in Bild 2.62a dargestellten Matrix die
Altersrelation zwischen den Cache-Zeilen 0 und 1 auch in Reihe 1 Spalte 0 codiert
werden könnte. Das entsprechende Bit würde jedoch immer den inversen Inhalt zu
dem in Reihe 0 Spalte 1 codierten Bit aufweisen und lässt sich deshalb als redundant
einsparen.
In Bild 2.62a bis 2.62d ist dargestellt, wie sich die Dreiecksmatrix aus dem Initialzu-
stand mit ausschließlich gelöschten Bits durch Adressierung der Zeilen 1, 3, 0 und 2
stückweise verändert. Beim Zugriff auf Cache-Zeile 1 in Bild 2.62a kommt es
zunächst zur Alterung der Cache-Zeilen 0, 2 und 3, und zwar, indem die Bits in
Spalte 1 gesetzt und die in Reihe 1 gelöscht werden (im Bild die hellgrau unterleg-
ten, fett umrahmten Bits). Inhaltlich bewirkt diese Modifikation, dass das Alter von
Zeile 0 bezogen auf Zeile 1 erhöht und dass der Zeile 1 bezogen auf die Zeilen 2 und
3 vermindert wird. Demzufolge ist der jüngste Eintrag eines Satzes identifizierbar,
indem man jeweils nach genau der Zeile im Cache sucht, die in der zugeordneten
Spalte nur gesetzte und in der zugeordneten Reihe nur gelöschte Bits enthält.