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

schen der Wurzel des Baums und der angesprochenen Zeile liegen, entsprechend
des durchlaufenen Pfads definiert. Falls z.B. auf Zeile 3 zugegriffen wird, sind die
LRU-Bits (a, b, e) entsprechend des fett gezeichneten Pfads auf (0, 1, 1) zu setzen.

Um die jeweils zu ersetzende Zeile zu identifizieren, müssen die inversen Inhalte
aller LRU-Bits betrachtet werden. Der sich einstellende Pfad führt im Bild vom
LRU-Bit a über c und g zur Zeile 6. Dass dies wirklich der möglicherweise älteste
Eintrag ist, lässt sich leicht verdeutlichen: Wegen des LRU-Bits g gleich 1 ist Zeile 6
definitiv älter als Zeile 7. In Verallgemeinerung dieser Argumentation muss wegen
des LRU-Bits c gleich 0 Zeile 6 älter als die Zeilen 4 und 5 und wegen des LRU-Bits
a gleich 0 auch älter als die Zeilen 0 bis 3 sein.

d

Line 0
Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7

0
1

b 0

0

1 e

weitere potentiell ersetzbare Zeilen

1

0
1

0

1

a

letzter Zugriff

0 f

0
1

0

c

1

0
1

0

g

zu ersetzende Zeile

0
1

1

Bild 2.63. Ersetzungsstrategie PLRU für einen Satz eines 8-fach assoziativen Caches. Die Zeile,
auf die zuletzt zugegriffen wurde, und die Zeile, die als nächstes ersetzt werden wird, sind durch
beschriftete Pfeile gekennzeichnet

Tatsächlich ist dies jedoch lediglich eine Annahme und der Grund dafür, weshalb
das PLRU-Verfahren nicht immer dieselben Ergebnisse wie das LRU-Verfahren
generiert. Der Leser möge sich davon überzeugen, dass mit den im Bild dargestell-
ten LRU-Bits, neben Zeile 6 auch die Zeilen 1, 2 und 5 potentielle Kandidaten für
den am längsten nicht adressierten Eintrag des Satzes sind. - Das PLRU-Verfahren
wird in vielen Prozessoren, z.B. dem PowerPC MPC750 von Motorola [128] und
dem Pentium 4 von Intel [80] verwendet.

FiFo (first-in, first out; auch als round robin bezeichnet). Dieses sehr einfache
Verfahren basiert darauf, dass auf Zeilen, die später in den Cache geladen wurden,
häufiger zugegriffen wird als auf solche, die früher in den Cache geladen wurden.
Dementsprechend kann man jeweils die Zeile im Cache ersetzen, die bereits die
längste Zeit darin befindet. Das Verfahren lässt sich sehr einfach mit Hilfe eines
Modulo-Zählers realisieren, der für einen Satz eines 8-fach assoziativen Caches z.B.
3 Bit breit sein muss. Dieser indiziert jeweils die am längsten im Cache verweilende
und als nächstes zu ersetzende Zeile. Nach dem Laden eines neuen Eintrags inkre-
mentiert man den Zähler um 1, wobei ein Überlauf das Zurücksetzen zum Startwert
0 bewirkt (Modulo-Operation). Enthält der Zähler den Zahlenwert 7, muss zuvor
Zeile 6 des Caches geladen worden sein. Mit dem nächsten Ladevorgang wird Zeile
7 ersetzt und dabei der Zähler auf 0 zurückgesetzt. In diesem Zustand enthält Zeile 7
den jüngsten, Zeile 6 den zweitjüngsten und Zeile 0 den als nächstes zu ersetzenden
ältesten Eintrag. - Das FiFo-Verfahren ist z.B. im XScale von Intel realisiert [83].