Cache Aufgabe

[Bert S. (kautschuck)]

Hallo,
gegeben ist die Aufgabe zum Thema Cache. Es soll also zunächst bei a.) 
die Hitrate des gegebenen Code-Ausschnittes für einen Direct mapped 
Cache berechnet werden. Leider habe ich keine Lösungen und weiss nicht 
genau, ob meine Lösung richtig ist:

a.)
In Zeile 7 passiert folgendes:

A[0] -> miss
B[0] -> miss
A[0]= B[0] -> 2Hit?

In Zeile 8:

A[0] -> hit
A[0] -> hit
C[0] -> miss
A[0] = A[0] + C[0] = 3 hit?

Und das wiederholt sich in jeder Wiederholung, also Total:

7 Hit, 3 Miss

Und somit ist die Hitrate 0.7?

Die Arrays sind ja im Adressraum hintereinander angeordnet, daher spielt 
es doch keine Rolle ob Assoziativ oder direct mapped?

Gruss Bert

[(prx) A. K. (prx)]

> In Zeile 7 passiert folgendes:
> In Zeile 8:

Die von dir dargestellte Reihenfolge der Operationen kann ich nicht 
nachvollziehen. Hast du die Auswirkung der Cache-Organisation in 
Lines/Blöcke berücksichtigt?

[(prx) A. K. (prx)]

Bert Siegfried schrieb:
> Die Arrays sind ja im Adressraum hintereinander angeordnet, daher spielt
> es doch keine Rolle ob Assoziativ oder direct mapped?

Ob es für eine Fangfrage wohl 10 Punkte gäbe?

[Bert S. (kautschuck)]

Ja, das wäre viel zu viel. Nochmal neu:
Also für den Direct mapped Cache gilt doch:

512bit / 4 Byte = 8 Integer pro Block
Mit 16kbit/512bit = 64 Sätze
3 offset bits
6 index bits

Nochmal für Zeile 7:

Nun wird ja A[0] (dezimale Adresse 0) im ersten Block gespeichert  -> 
miss
B[0] hat die dezimale Adresse 4*1024 = 4096, also ebenfalls Block eins 
eins, da dort A[0] ist -> miss
nun wird B[0] aus dem Cache geholt -> Hit und wird in A[0] geschrieben 
-> miss

Stimmt das soweit? Gruss

[(prx) A. K. (prx)]

Als Reihenfolge der Mem-Operationen in 7 und 8 sehe ich:
  load  B[0]
  store A[0]
  load  A[0]
  load  C[0]
  store A[0]
  load  B[1]
  store A[1]
  load  A[1]
  load  C[1]
  store A[1]
  ...

> Stimmt das soweit?

Du scheinst Adress- und Datenoperationen eines Caches separat als 
hit/miss zu zählen. Und kommst damit bei einem einzigen load auf einen 
hit und einen miss. Dieser Betrachtungsweise bin ich noch nie begegnet.

Du solltest mal die Cache-Auswirkungen für mehrere Iterationen 
betrachten, mit detaillierter Angabe, was mit welchem Cache-Block 
geschieht. Und beim assoziativen Fall auch ebendiese Assoziativität samt 
LRU replacement berücksichtigen.

[Bert S. (kautschuck)]

Ok, danke, ja hatte da eine viel zu komplizierte Betrachtungsweise.

Also beim Direct Mapped Cache folgt nun für die erste Iteration:

load  B[0] -> miss
store A[0] -> miss
load  A[0] -> hit
load  C[0] -> miss (wird wieder in Block 1 geschrieben, also A[0] wird 
überschrieben)
store A[0] -> miss

Da ein Cacheblock den Adressbereich 0..7 abdeckt:

load  B[1] -> miss
store A[1] -> miss
load  A[1] -> hit
load  C[1] -> miss (wird in Block 1 geschrieben, also A[1] wird 
überschrieben)
store A[1] -> miss

Also 4 Miss und 1 Hit für eine Iteration -> Hitrate = 0.2


Beim Assoziativen Cache folgt:

load  B[0] -> miss
store A[0] -> miss
load  A[0] -> hit
load  C[0] -> miss
store A[0] -> hit

load  B[1] -> miss
store A[1] -> hit (Da C[0] durch B[1] wegen LRU überschrieben wird)
load  A[1] -> hit
load  C[1] -> miss
store A[1] -> hit

load  B[2] -> miss
store A[2] -> hit (Da C[1] durch B[2] wegen LRU überschrieben wird)
load  A[2] -> hit
load  C[2] -> miss
store A[2] -> hit

.
.
.

load  B[7] -> miss
store A[7] -> hit
load  A[7] -> hit
load  C[7] -> miss
store A[7] -> hit

Dann wird der zweite Block betrachtet:

load  B[8] -> miss
store A[8] -> miss
load  A[8] -> hit
load  C[8] -> miss
store A[8] -> hit

Also haben wir für den ersten Block 1 x 2 + 7 x 3 = 23 Hits, 1 x 3 + 7 x 
2 = 17 Miss -> Hitrate = 0.575

Kann das stimmen?
Gruss Bert

[(prx) A. K. (prx)]

Das sieht auf den ersten Blick deutlich besser aus.

[Bert S. (kautschuck)]

Super, vielen Dank für deine Hilfe