GRABS Übungsaufgaben Arbeitsspeicher und Caches Mengenassoziative Caches

Mengenassoziative Caches

In dieser Aufgabe geht es um mengenassoziative Caches (en. set-associative). Die Adressierung erfolgt wortweise. Unser System nutzt 64-Bit-Adressen.

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

Konstruieren Sie gedanklich einen mengenassoziativen Cache mit drei Wegen. Die Cache-Blöcke sollen zwei Worte groß sein. Der gesamte Cache soll eine Kapazität von 48 Worten haben. Wie viele Cache-Zeilen gibt es und wie breit sind sie? Wie viele Bits werden für Tag, Index und Offset benötigt?

Lösung

Aufbau des Caches:
- zwei Worte je Block
- ein Block je Weg
- drei Wege je Zeile
- somit sechs Worte je Zeile
- in Summe 48/6 = 8 Zeilen
Aufbau der Adressen:
- wortweise Adressierung → 0 Bit Word Offset
- zwei Worte je Block → 1 Bit Block Offset
- acht Zeilen → 3 Bit Index
- verbleibende Bits für den Tag

b)

Level 3: Anwenden

Vollziehen Sie die Funktionsweise des Caches aus der ersten Teilaufgabe nach. Nehmen Sie als Ersetzungsstrategie „Least Recently Used“ (LRU) an. Identifizieren Sie für jede Referenz

die binäre Wortadresse,
den Tag,
den Index und
den Offset.

Geben Sie weiterhin an,

ob es sich um einen Hit oder einen Miss handelt und
welchen Inhalt der Cache nach der Behandlung des Zugriffs hat.

Hinweis: $T[x]$ ist der Tag an Index x.

	Binär	Tag	Index	Offset	Hit?	Weg 0	Weg 1	Weg 2
`0x03`	`0000.0011`
`0xb4`	`1011.0100`
`0x2b`	`0010.1011`
`0x02`	`0000.0010`
`0xbe`	`1011.1110`
`0x58`	`0101.1000`
`0xbf`	`1011.1111`
`0x0e`	`0000.1110`
`0x1f`	`0001.1111`
`0xb5`	`1011.0101`
`0xbf`	`1011.1111`
`0xba`	`1011.1010`
`0x2e`	`0010.1110`
`0xce`	`1100.1110`

Nutzen Sie für diese Aufgabe die folgende Sequenz von Worten:

0x03, 0xb4, 0x2b, 0x02, 0xbe, 0x58, 0xbf, 
0x0e, 0x1f, 0xb5, 0xbf, 0xba, 0x2e, 0xce

Lösung

	Binär	T	I	O	H?	W0	W1	W2
`0x03`	`0000.0011`	0	001	1	M	T[1]=0
`0xb4`	`1011.0100`	b	010	0	M	T[1]=0 T[2]=b
`0x2b`	`0010.1011`	2	101	1	M	T[1]=0 T[2]=b T[5]=2
`0x02`	`0000.0010`	0	001	0	H	T[1]=0 T[2]=b T[5]=2
`0xbe`	`1011.1110`	b	111	0	M	T[1]=0 T[2]=b T[5]=2 T[7]=b
`0x58`	`0101.1000`	5	100	0	M	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b
`0xbf`	`1011.1111`	b	111	1	H	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b
`0x0e`	`0000.1110`	0	111	0	M	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b	T[7]=0
`0x1f`	`0001.1111`	1	111	1	M	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b	T[7]=0	T[7]=1
`0xb5`	`1011.0101`	b	010	1	H	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b	T[7]=0	T[7]=1
`0xbf`	`1011.1111`	b	111	1	H	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b	T[7]=0	T[7]=1
`0xba`	`1011.1010`	b	101	0	M	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b	T[5]=b T[7]=0	T[7]=1
`0x2e`	`0010.1110`	2	111	0	M	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b	T[5]=b T[7]=2	T[7]=1
`0xce`	`1100.1110`	c	111	0	M	T[1]=0 T[2]=b T[4]=5 T[5]=2 T[7]=b	T[5]=b T[7]=2	T[7]=c

T = Tag, I = Index, O = Offset, H = Hit, M = Miss, W = Weg
Angaben bei Tags und Wegen in Hexadezimaldarstellung

Lernziele

In dieser Aufgabe …

wiederholen die Studierenden den Aufbau mengenassoziativer Caches.
leiten die Studierenden aus gegebenen Anforderungen einen Cache-Entwurf ab.
simulieren die Studierenden die Funktionsweise des Caches.