« »

GRABS Übungsaufgaben Arbeitsspeicher und Caches Direkt abgebildete Caches

Direkt abgebildete Caches

Betrachten Sie einen direkt abgebildeten Cache (en. direct-mapped) mit 64-Bit-Adressen, wobei die folgenden Bits der Adresse zum Zugriff auf den Cache verwendet werden:

TagIndexOffset
63–109–54–0

Die Adressierung erfolgt byteweise.

Diese Aufgabe stammt aus Kapitel 5.3 von "Computer Organization and Design. The Hardware/Software Interface. RISC-V Edition" (Patterson & Hennessy, 2018).

a)

Level 3: Anwenden

Was ist die Blockgröße des Caches (in Worten)?

Lösung
  • 64 Bit je Wort → 8 Byte je Wort
  • gesamter Offset: 5 Bit – davon …
    • 3 Bit für den Word Offset (innerhalb eines 8-Byte-Wortes)
    • 2 Bits für den Block Offset, womit $2^2 = 4$ Worte nummeriert werden können
  • jeder Cacheblock besteht also aus vier Worten

b)

Level 1: Wissen

Wie viele Blöcke hat der Cache?

Lösung
  • Index ist 5 Bit breit
  • darum $2^5$ = 32 Zeilen im Cache
  • bei direkter Abbildung enthält jede Zeile einen Block
  • darum 32 Blöcke im Cache

c)

Level 1: Wissen

Wie ist das Verhältnis von den für diese Implementierung des Caches insgesamt benötigten Bits zu den gespeicherten Datenbits?

Lösung
  • Nutzdaten: 32 Blöcke · 4 Worte je Block · 8 Byte je Wort = 1.024 Byte = 8.192 Bits
  • Metadaten: (54 Tag-Bits je Block + 1 Gültigkeitsbit je Block) · 32 Blöcke = 1.760 Bits
  • insgesamt: 9.952 Bits
  • Verhältnis Gesamtgröße zu Nutzdaten: 9.952 Bit ÷ 8.192 Bit = 1,21

d)

Level 3: Anwenden

Ab dem Moment des Einschaltens wurden folgende byte-adressierte Adresszugriffe aufgezeichnet:

0x00, 0x04, 0x10, 0x84, 0xe8, 0xa0, 
0x400, 0x1e, 0x8c, 0xc1c, 0xb4, 0x884

Vollziehen Sie die Funktionsweise des Caches nach. Identifizieren Sie für jeden Zugriff den Tag, den Index und den Offset. Geben Sie weiterhin an, ob es sich um einen Hit oder einen Miss handelt und gegebenenfalls, welche Bytes ersetzt wurden.

Binär-AdresseTagIndexOffsetHit?ersetzte Bytes
0x000000.0000.0000
0x040000.0000.0100
0x100000.0001.0000
0x840000.1000.0100
0xe80000.1110.1000
0xa00000.1010.0000
0x4000100.0000.0000
0x1e0000.0001.1110
0x8c0000.1000.1100
0xc1c1100.0001.1100
0xb40000.1011.0100
0x8841000.1000.0100
Lösung

Hinweis zur Darstellung: In der Binär-Adresse werden führende Nullen weggelassen und somit nur die letzten 12 Bit gezeigt.

Binär-AdresseTagIndexOffsetHit?ersetzte Bytes
0x000000.0000.00000x00x000x00Miss
0x040000.0000.01000x00x000x04Hit
0x100000.0001.00000x00x000x10Hit
0x840000.1000.01000x00x040x04Miss
0xe80000.1110.10000x00x070x08Miss
0xa00000.1010.00000x00x050x00Miss
0x4000100.0000.00000x10x000x00Miss0x00–0x1f
0x1e0000.0001.11100x00x000x1eMiss0x400–0x41f
0x8c0000.1000.11000x00x040x0cHit
0xc1c1100.0001.11000x30x000x1cMiss0x00–0x1f
0xb40000.1011.01000x00x050x14Hit
0x8841000.1000.01000x20x040x04Miss0x80–0x9f

Zur Frage, welche Bytes bei einem Cache Miss ersetzt werden:

  • 5 Bit Offset, also Werte 0.0000 bis 1.1111 möglich
  • darum Bereich (Startadresse + 0x00) bis (Startadresse + 0x1f)

e)

Level 3: Anwenden

Erstellen Sie eine Liste, die den Endzustand des Caches beschreibt. Jeder gültige Eintrag soll in der Form <index, tag, data> angegeben werden (z. B. <0x0, 0x3, Mem[0xc00]-Mem[0xc1f]>).

<index, tag, data>
<0x.., 0x.., Mem[0x...]-Mem[0x...]>
Lösung 
<index, tag, data>
<0x00, 0x03, Mem[0xc00]-Mem[0xc1f]>
<0x04, 0x02, Mem[0x880]-Mem[0x89f]>
<0x05, 0x00, Mem[0x0a0]-Mem[0x0bf]>
<0x07, 0x00, Mem[0x0e0]-Mem[0x0ff]>

f)

Level 1: Wissen

Ermitteln Sie die Hit Ratio, also den Anteil der Zugriffe, die aus dem Cache erfüllt werden konnten.

Lösung
  • Hit Ratio = (Anzahl der Treffer) ÷ (Anzahl der Zugriffe) = 4 ÷ 12 = 33,33 %

Lernziele

In dieser Aufgabe …

  • festigen die Studierenden ihre Kenntnisse der Struktur direkt abgebildeter Caches.
  • leiten die Studierenden aus einem Adressierungsschema den Aufbau des Caches ab.
  • berechnen die Studierenden einfache Kennzahlen.