FIFO Ersetzungsstrategie

dstorck
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 26. Mär 2009 07:58

FIFO Ersetzungsstrategie

Beitrag von dstorck »

Servus,

ich bin mir nicht sicher ob ich das ganze Prinzip des Caches verstanden habe aber ich versuche es mal.
In der HÜ haben wir einen 2-Fach Cache mit FIFO-Ersetzungsstrategie.
Das heisst, dass wir in einer Zeile 2 Spalten haben mit jeweils 1024 words Daten. Jetzt greife ich über die Adresse auf ein Byte im Cache zu und bekomme ein Miss, die Daten(1 Byte?) werden jetzt in die Zeile des Caches geschrieben. Wird bei erneutem Adressaufruf auf die selbe Zeile (ebenfalls gleiches Byte des entsprechenden Words) automatisch in die 2 te Spalte dieser Zeile geschrieben? Und falls beide Zeilen belegt sind wird die erste Zeile überschrieben, da diese schon länger existiert?

mfG

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: FIFO Ersetzungsstrategie

Beitrag von AlexPi11 »

Jetzt greife ich über die Adresse auf ein Byte im Cache zu und bekomme ein Miss, die Daten(1 Byte?) werden jetzt in die Zeile des Caches geschrieben.
Also man sucht nach der Adresse im Cache und erhält ein Miss, wenn sich diese nicht im Cache befindet oder sie nicht gültig ist (Valid-bit). Nun werden die Daten in den Cache geschrieben. Die Anzahl der Bytes ist dabei immer gleich. Wie du schon gesagt hast ist die Blockgröße 1024 Wörter. Also selbst wenn mich nur ein Bit an einer Adresse interessiert, werden 1024 Wörter an Daten (also ohne Adresse, Valid/Dirty-Bit) in den Cache geschrieben.
Wird bei erneutem Adressaufruf auf die selbe Zeile (ebenfalls gleiches Byte des entsprechenden Words) automatisch in die 2 te Spalte dieser Zeile geschrieben?
Wenn man vorraussetzt, dass der Tag unterschiedlich ist, dann müsste das so sein. Ob das jetzt von einem Byte abhängt welche Zeile hergenommen wird, weiß ich nicht mehr.
Und falls beide Zeilen belegt sind wird die erste Zeile überschrieben, da diese schon länger existiert?
Genau.

Spätestens, wenn du die Hausaufgabe zurückbekommen hast, siehst du ja ob's gestimmt hat. :wink:

dstorck
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 26. Mär 2009 07:58

Re: FIFO Ersetzungsstrategie

Beitrag von dstorck »

Super, danke du hast ein wenig Licht in die Dunkelheit gebracht :D .

k_b
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 213
Registriert: 15. Mär 2009 12:06

Re: FIFO Ersetzungsstrategie

Beitrag von k_b »

Hallo,

wie ist es denn, wenn die Tags gleich sind? Bedeutet das dann, dass ich einen Hit habe? Meiner momentanen Ansicht nach, könnte es doch aber auch passieren, dass ich nach einem bestimmten Datensatz im Cache suche, der zwar den selben Tag hat, aber nicht in dem geladenen Block von 1024 Wörtern ist. Ist das möglich?
Bei mir herrscht grad noch Verwirrung wie die Enscheidung funktioniert, ob ich in den 2. Block des 2-fach mengenassiziativen Caches schreibe und eben noch bei oben beschriebenem Problem.


Danke schonmal ;)

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: FIFO Ersetzungsstrategie

Beitrag von AlexPi11 »

Einen Hit gibt es nur wenn Index und Tag gleich sind. (Und die Adresse muss natürlich gültig sein)
Ein kleines Beispiel:
Ich habe insgesamt 8 = 2^3 Adressen
Mein Cache hat 2 Zeilen und ist 2-fach mengenassoziativ.

Ob ich Zeile 0 oder Zeile 1 nehme hängt also nur vom letzten Bit der Adresse ab (2^1 = 2). Der Tag besteht dann zwangsweiße aus den ersten 2 Bit.
Anfangs seien alle Einträge ungültig. Greife ich nun auf die Adressen 000, 010 und 100 zu, wäre das 3 mal ein Miss, da jedes Mal der Tag oder das Valid-Bit nicht passt.
Da am Ende immer eine 0 steht spielt sich das alles in der Zeile 0 ab: (X, X) -> (000, X) -> (000, 010) -> (100, 010)
Wenn ich nun auf Adresse 100 zugreifen wollte, wäre das ein Hit.

Bei 101 hätte ich zwar nun den gleichen Tag wie bei 100, aber da der Index 1 ist, kümmert mich Zeile 0 nicht. 101 wäre also wieder ein Miss, da in der Zeile 1 noch alle Einträge ungültig sind.

Es ist also nicht möglich einen Hit zu bekommen, obwohl es sich nicht um die gleiche Adresse handelt. Index + Tag sind eindeutig. Was im Block steht ist dabei irrelevant. Ändert sich der Inhalt an einer Adresse, wird der Eintrag im Cache (,falls vorhanden,) als nicht mehr gültig gekennzeichnet.

Antworten

Zurück zu „Archiv“