3. Lösungsblatt zur Vorlesung Rechnerstrukturen:
Virtuelle Speicherverwaltung, Cache

Die Besprechung dieses Übungsblattes findet am Mittwoch, dem 29. Mai 2002, um 15.45 Uhr im HMU statt. Das Aufgabenblatt und diese Musterlösung findet sich im WWW unter http://wwwipr.ira.uka.de/~lehre/RS/index.html

1. Aufgabe (Verständnisfragen)

a) Die Taktzeiten moderner Prozessoren sind viel kürzer als die Zugriffszeiten des Hauptspeichers. Damit der Prozessor nicht ständig auf Daten aus dem Hauptspeicher warten muss werden Caches verwendet. Diese schließen sowohl bezüglich der Zugriffsgeschwindigkeit als auch der Speicherkapazität die Lücke in der Speicherhierarchie zwischen Registern (Prozessor) und Hauptspeicher.

b) Im Fall, dass auf ein Datum welches sich nicht im Cache befindet zugegriffen werden muss, ist der Cache-Zugriff nicht schneller als ein 'normaler' Zugriff. Der Vorteil der schnelleren Zugriffsgeschwindigkeit ergibt sich erst bei mehreren Zugriffen auf das selbe Datum, oder auf aufeinander folgende Daten. Mehrere derartige Zugriffe sind aber aufgrund der Lokalität von Programmen sehr häufig.

c) Der Cache Speicher muss neben den eigentlichen Daten auch noch Zusatzinformationen wie Gültigkeit, Adressetikett usw. abspeichern. Diese Informationen werden im Tag-Speicher gelagert.

2. Aufgabe (Cache Strukturen)

a) Cache Strukturen (Organisationsformen für Caches):

Direkt-abgebildet / Direct Mapped,
k-fach-(Satz/Mengen)-Assoziativ / k-way (set) associative
Vollassoziativ / fully associative

b) Zuordnung von Hauptspeicherblöcken zu Cacheblockrahmen:

Bezeichnungen:

Hauptspeicher:

Block B_j , j = 0, 1, ..., (n-1)

Kapazität: n * b = 2^s+w Wörter

Cache:

Blockrahmen Z_i , i = 0, 1, ...(m-1) (Cache-Zeile)

Kapazität: m * b = 2^r+w Wörter

n >> m, n = 2^s , m = 2^r , b = 2^w , jeder Block enthält b Wörter

Cache Strukturen legen die Abbildung von {B_j } nach {Z_i } fest:

- Direkt-abgebildet / Direct Mapped:
direkte Abbildung von n/m = 2^s-r Speicherblöcken in eine Cache-Zeile:
B_j --> Z_i , mit i = j mod m
Ein Block kann nur in einen bestimmten Blockrahmen im Cache stehen. => Bewirkt u.U. Leistungseinbußen, z.B. durch Speicherflattern (Trashing)

- k-fach-(Satz/Mengen)-Assoziativ / k-way (set) associative:

Zusammenfassen von k Zeilen zu einem Satz (Menge, set)

Aufteilen der m Cache-Zeilen in v = m/k Sätze zu je k Zeilen;

jeder Satz wird über eine d Bit breite Nummer identifiziert: 2^d = v

ein Block B_j kann in eine der verfügbaren Zeilen Z_f in einem Satz S_i

abgebildet werden:

B_j --> Z_f , mit f Î S_i , mit i = j mod v
Mehrere Blockrahmen bilden einen Satz. Ein Block kann in jedem Blockrahmen eines bestimmten Satzes untergebracht sein. Ein Satz enthält k Block Frames. Die Zuordnung auf die Block Frames innerhalb des Set ist beliebig.
Bsp.: Der Level 1-Cache des Pentium ist zweifach assoziativ, der des Pentium Pro vierfach.

- Vollassoziativ / fully associative:
Der ganze Cache besteht nur aus einem Satz, d.h. ein Block kann in jedem beliebigen Block-Rahmen untergebracht sein.

B_j --> Z_i , mit i beliebig aus { 0, ... , m-1}

c) Cache-Abdeckungsgrad Assoziativitätsgrad

- Cache Abdeckungsgrad = n / m = Hauptspeichergröße / Cache Größe

- Assoziativitätsgrad = k = Anzahl der Blockrahmen pro Satz

d) Beispielzuordnung:
Cache der Größe m=8, Suche Cache Block für Speicherblock j =12.

- Direkt-abgebildet / Direct Mapped, Block 12 kann nur in Block-Rahmen i = j mod m = 12 mod 8 = 4 abgelegt werden

Block Nr.	0	1	2	3	4	5	6	7
Cache
Satz Nr. (Index)	0	1	2	3	4	5	6	7

Cache Abdeckungsgrad = 64 / 8 = 8

Assoziativitätsgrad = 1

- k-fach-(Satz/Mengen)-Assoziativ / k-way (set) associative: Block j=12 kann nur in Satz i = j mod v = j mod (m/k) abgelegt werden.
Für k = 2 in Satz i = 12 mod (8/2) = 0 d.h. in Block-Rahmen f Î S_i = S₀ = {0, 1}

Block Nr.	0	1	2	3	4	5	6	7
Cache
Satz Nr. (Index)	0		1		2		3

Cache Abdeckungsgrad = 64 / 8 = 8

Assoziativitätsgrad = 2

Für k = 4 in Satz i = 12 mod (8/4) = 0 d.h. in Block-Rahmen f Î S_i = S₀ = {0,1, 2, 3}

Block Nr.	0	1	2	3	4	5	6	7
Cache
Satz Nr. (Index)	0				1

Cache Abdeckungsgrad = 64 / 8 = 8

Assoziativitätsgrad = 2

- Vollassoziativ / fully associative: Block j=12 kann in jeden Block-Rahmen abgelegt werden i Î { 0, ... , 7 }

Block Nr.	0	1	2	3	4	5	6	7
Cache
Satz Nr. (Index)	0

Cache Abdeckungsgrad = 64 / 8 = 8

Assoziativitätsgrad = m = 8

e) Ersetzungsstrategien/Verdrängungsstrategie für Caches

- LRU (Least recently used / am wenigsten neulich benutzt):
Die Speicherportion (Block / Cache-Line / Block Frame) im Satz (Cache-Set), die am längsten nicht benuzt wurde wird verdrängt.
=> aufwändigere Implementierung, da die Benutzung vermerkt werden muß

- Random (Zufall):
Aus den möglichen Kandidaten im Satz (Cache-Set) wird zufällig einer ausgewählt
=> einfacher zu implementieren

- LFU (Least frequently used / am seltensten benutzt:
Die Speicherportion (Block / Cache-Line / Block Frame) im Satz (Cache-Set), die im Vergleich zu den anderen am wenigsten benutzt wurde wird verdrängt.
=> aufwändigere Implementierung, da die Benutzung vermerkt werden muß

Wenn es die Cache-Struktur zulässt, dass ein aus dem Hauptspeicher zu lesender Block in verschiedene Cache-Blockrahmen geladen werden kann, dann muss ein Blockrahmen verdrängt werden, wenn alle erlaubten Blockrahmen belegt sind. Bei Direkt-abgebildeten Caches ist also keine Verdrängungsstrategie notwendig, wohl aber bei Mengenassoziativen und vollassoziativen Caches.

f) Rückschreibe- Durchschreibe-Strategie

- Rückschreibe Strategie / Write-Back :
Schreibbefehle ändern zunächst nur den Cache. Damit die geänderten Daten schließlich doch irgendwann im Hauptspeicher landen muss beim Verdrängen eines Cache-Blockrahmens ggf. der verdrängte Inhalt im Hauptspeicher gesichert werden. Dies kann entweder immer getan werden (simple copy-back) oder nur wenn der Cache-Blockrahmen geändert wurde (flagged copy-back mit Dirty Bits).

- Durchschreibe-Strategie / Write-Through:
Jede Änderung in einem Cache-Block wird sofort in den Hauptspeicher geschrieben. Ist das entsprechende Datum im Cache so wird dieser zwar auch aktualisiert, der Befehlszyklus wartet aber auf die Beendigung des Hauptspeicherzugriffs - der Cache verliert also seinen Geschwindigkeitsvorteil beim Schreiben. Da dieses Verfahren also langsamer ist, verwenden die meisten Systeme Write-Back. Jedoch ist Write-Through von der Chiplogik her einfacher.
Varianten: Buffered-Write-Through, No-Write-Allocation, Write-Allocation.

3. Aufgabe (Cache-Speicher)

a) Cache-Abdeckungsgrad = 32 = (Hauptspeichergröße / Cache Größe = 64 kB / 2 kB),

Anzahl Cache-Blöcke m = 64 = (Cache Größe / Block Größe) = 2 kB / 32 B)

Cache-Art	Assoziativitätsgrad	Anzahl Sätze (m / k)
I.) direktabgebildet	k = 1	v = 64 (= m)
II.) vollassoziativ	k = 64 (= m)	v = 1
III.) 4-fach Satz-assoziativ	k = 4	v = 16

b) Tag: Unterscheidungsmerkmal für die mögl. HS-Blöcke
Index: Adresse des Satz im Cache
Block Offset: Byte-Adresse im Block

c)

Abblildung	Tag	Index	block offset
I.) direct mapped	5 bit	6 bit	5 bit
II.) vollassoziativ	11 bit	0 bit	5 bit
III.) 4-fach set-assoziativ	7 bit	4 bit	5 bit

d) Pro Cache-Block müssen nach c) für I) 5 Bit, für II) 11 Bit und für III) 7 Bit des Tag abgespeichert werden. Die Bits des Index und des Block-Offset müssen nicht abgespeichert werden. Insgesamt werden also für I) mindestens m* 5 Bit = 320 Bit, für II) m*11 = 704 und für III) m*7 = 448 Bit benötigt.

e) Qualitativ: Der vollassoziative Cache ist besser geeignet. Der Cache hat 64 freie Blöcke, die wahlfrei belegt werden können. Beim Programmablauf wird auf zwei Codeblöcke und zwei Datenblöcke zugegriffen. Damit wird jeder Block nur einmal in den vollassoziativen Cache geladen, es kommt zu keiner Verdrängung. Bei dem direktabgebildeten Cache kommt es ständig zu Verdrängungen, weil die Code- und Datenblöcke auf die gleichen Cacheblöcke gemappt werden! (trashing)

Quantitativ:

Vollassoziativer Cache:

Es werden alle Blöcke der Reihe nach in die freien Cache-Blöcke geschrieben.

Direct-mapped Cache:

Zeile 1: Block 1 wird durch Code belegt.
Code liegt an Adr. 0x28, also Hauptspeicher-Block 1 (= 0x28 >> 5)
Dieser wird direkt auf Cache-Blockrahmen 1
(= 1 mod 0x40) abgebildet

Zeile 4: Block 1 wird durch Daten belegt. (Verdrängung)
Adr. 0x2034, also Hauptspeicher-Block 0x101
(= 0x2034 >> 5) wird beschrieben
Dieser wird direkt auf Cache-Blockrahmen 1
(= 0x101 mod 0x40) abgebildet

Zeile 5: Block 1 wird durch Code belegt, danach gleich wieder durch Daten. (Verdrängung)

Zeile 6: Block 1 wird durch Code belegt. (Verdrängung)

Zeile 7: Block 2 wird durch Code belegt, Block 1 durch Daten. (Verdrängung)

Zeile 10: Block 1 wird durch Daten belegt. (Verdrängung)

Zeile 13: Block 2 wird durch Daten belegt.(Verdrängung)

Zeile 14: Block 2 wird durch Code belegt. (Verdrängung)

Zeile 1: Block 1 wird durch Code belegt. (Verdrängung)

usw.

f)

HS-Adr. (0x)	Set	Offset	leer	belegt	verdrängte HS-Adressen (0x)	Bemerkung
1AC8	22	8	x
32E4	23	4		x	2AE0 - 2AFF	Verdrängung
32E5	23	5		x	keine Verdrängung	Block vorhanden, Cache Hit
3B34	25	20		x	6320 - 633F	Verdrängung
63B8	29	24		x	keine Verdrängung	Block vorhanden, Cache Hit
EB4C	26	12	x

Abbildung Hauptspeicher-Adr. h -> Satz-Nummer i :

i = (h >> 5) mod 0x40

Verdrängte Adressen berechnen sich aus dem in dem Tag-Speicher gegebenen Tag und dem Index der sich aus der Set-Adresse ergibt. Ein Block umfaßt 32 = 2⁵ Byte, also werden insgesamt 32 HS-Adressen auf einmal aus dem Cache verdrängt, wenn ein Block verdrängt wird.

Wenn ein Block bereits im Cache vorhanden ist, kann direkt auf den Cache zugegriffen werden, der Block braucht nicht erst aus dem HS geholt zu werden, es findet also auch keine Verdrängung statt!

Der Tag-Speicher enthält die 5 Bits des Tags, ein belegter Cache-Blockrahmen mit Tagspeicherinhalt = t in Satz s enthält also den Hauptspeicherblock Nummer i = t << 6 + s
bzw. die Hauptspeicher-Adr. h = i << 5

4. Aufgabe (Virtuelle Speicherverwaltung)

a) Bei der LRU-Ersetzungsstrategie werden insgesamt 14 Seiten ein- bzw. ausgelagert:

Zeile	i	j	Seite	Aktion
6	0		D29E7	auslagern
			D29E4	anlegen -> 3
4	FFE	2	D29E4	auslagern
			D29E7	einlagern -> 3
6	FFE		D29E6	auslagern
			D29E4	einlagern -> 2
4	FFF	0	D29E7	auslagern
			D29E6	einlagern -> 3
4	FFF	1	D29E4	auslagern
			D29E7	einlagern -> 2
6	FFF		D29E6	auslagern
			D29E4	einlagern -> 3
6	1000		D29E4	auslagern
			D29E5	anlegen -> 3
6	1FFE	2	D29E8	Zugriffsverletzung

b) Bei der folgenden Ersetzungsstrategie reduziert sich die Anzahl der Ein-/Auslagerungen auf 10:

Zeile	i	j	Seite	Aktion
6	0		D29E7	auslagern
			D29E4	anlegen -> 3
4	FFE	2	D29E6	auslagern
			D29E7	einlagern -> 2
4	FFF	0	D29E7	auslagern
			D29E6	einlagern -> 2
4	FFF	1	D29E6	auslagern
			D29E7	einlagern -> 2
6	1000		D29E4	auslagern
			D29E5	anlegen -> 3
6	1FFE	2	D29E8	Zugriffsverletzung

5. Speicherhierarchie

a) Um die Zugriffsgeschwindigkeit zu steigern. Ausnutzen der sog. Lokalität von Programmen: Wenn ein Datum von Adresse x gebraucht wird, so wird es wahrscheinlich bald wieder, oder zumindest ein Datum aus der 'Nähe' von x benötigt.
Cache-Prinzip: Häufig genutzte Daten in schnellen Speichern halten. Seltener genutzte dürfen langsamer zugänglich sein.
Typische Speicherhierachie: CPU-Register (Cache-Level 0), L1-Cache "on chip", L2-Cache "on board", Hauptspeicher, Festplattenspeicher, Wechselplattenspeicher

b) 256 Stück 32 Bit breite Register ergeben 256 * 32 / 8 = 1 kB Register-Cache (L0-Cache)

c) CPU <-> Register ("L0-Cache") <-> L1-Cache <-> HS
r_H,reg = r_H0=0,5 ; r_H,HS=1 ist klar nach Aufgabenstellung
gesucht ist nun r_H,L1(n)=r_H1(n) wobei n ein Maß für die Cachegröße S_c = 1kB * 2ⁿ ist.

Um die Aussage "Die Wahrscheinlichkeit eines Hits nimmt um 50% zu, wenn man die Cachegröße der Ebene verdoppelt" in eine Formel umzusetzen betrachten wir zunächst die Miss-Rate r_M,L1=r_{M1 :}
Es gilt r_M1=1-r_H1 , da immer gilt: r_Mx + r_Hx  = 1

Nun kann die Aussage umformuliert werden zu "Die Wahrscheinlichkeit eines Miss nimmt um 50% ab, wenn man die Cachegröße der Ebene verdoppelt", also: r_M1(n+1)=0.5*r_M1(n)
daraus folgt mit r_M1=1-r_H1 daß r_H1(n+1)=1/2 + 1/2*r_H1(n)
für allgemeines n gilt also:
r_H1(n) = 1/2 + 1/4 + 1/8 + ... + 1/2ⁿ + r_H1(0)/2ⁿ
mit r_H1(0) = 0,5 und der gegeben Formel gilt dann
r_H1(n) =

für n=1,2,3 gilt also r_H1(1) = 0,75

n	rH1(n)
1	3/4 = 0,75
2	7/8 = 0,875
3	15/16 = 0,9375

Bemerkung: Die Formulierung der Aussage auf dem Aufgabenblatt ist, wie auch schon in der Übung am 2002-05-29 berechtigterweise moniert wurde, nicht ganz eindeutig. Gemeint war, dass r_H(n+1) um 50% der verbleibenden Wahrscheinlichkeit zunimmt. Bei dieser Formulierung ist das Ergebnis aber schon allzu offensichtlich...

d) Prozessortakt = 500 MHz => Zykluszeit T = 2 ns

Auf den L0 Cache (Register) kann mit T_H0 = T zugegriffen werden, so daß hierfür T_H0 - T = 0 Waitstates anfallen.

Auf den L1 Cache kann mit T_H1 = 8 ns = 4 T zugegriffen werden, so daß hier beim Zugriff T_H1- T = 3 Waitstates einzufügen sind.

Auf den Hauptspeicher kann mit T_HHS = 60 ns = 30 T zugegriffen werden, so daß hier beim Zugriff T_HHS - T = 29 Waitstates einzufügen sind.

Nach der allgemeinen Formel t_Access = Hitrate * t_Hit + (1-Hitrate) * t_Mis

kann die Zeit (in Taktzyklen T) für einen Speicherzugriff wie folgt berechnet werden:

T_Access = r_H0 * T_H0 + (1- r_H0) * T_Access1 , mit

T_Access1 = r_H1 * T_H1 + (1- r_H1) * T_HHS , insgesamt also

T_Access = r_H0 * T_H0 + (1- r_H0) * (r_H1 * T_H1 + (1- r_H1) * T_HHS )

für r_H0 = 0,5 und r_H1 = 1,0 gilt dann

T_Access = 2,5 T, es müssen also im Schnitt 1,5 Waitstates eingelegt werden.

für 0< r_H1 < 1.0 verursacht der L1 Cache im Schnitt

W₁ = (r_H1 * T_H1 ) - T Waitstates, und der Hauptspeicher

W_HS = (1- r_H1) * T_HHS - T

e) Mit folgender Tabelle ergibt sich eine Mindestgröße von 16 kB:

				TH1 =4		TH1 =2,5
n	SC [kB]	SC [MB]	rH1	TAccess	Waitstates	TAccess	Waitstates
1	2	0,00195313	0,75	5,75	4,75	5,1875	4,1875
2	4	0,00390625	0,875	4,125	3,125	3,46875	2,46875
3	8	0,0078125	0,9375	3,3125	2,3125	2,609375	1,609375
4	16	0,015625	0,96875	2,90625	1,90625	2,1796875	1,1796875
5	32	0,03125	0,984375	2,703125	1,703125	1,96484375	0,96484375
6	64	0,0625	0,9921875	2,6015625	1,6015625	1,85742188	0,85742188
7	128	0,125	0,99609375	2,55078125	1,55078125	1,80371094	0,80371094
8	256	0,25	0,99804688	2,52539063	1,525390625	1,77685547	0,77685547
9	512	0,5	0,99902344	2,51269531	1,512695313	1,76342773	0,76342773
10	1024	1	0,99951172	2,50634766	1,506347656	1,75671387	0,75671387
11	2048	2	0,99975586	2,50317383	1,503173828	1,75335693	0,75335693
12	4096	4	0,99987793	2,50158691	1,501586914	1,75167847	0,75167847
13	8192	8	0,99993896	2,50079346	1,500793457	1,75083923	0,75083923
14	16384	16	0,99996948	2,50039673	1,500396729	1,75041962	0,75041962
15	32768	32	0,99998474	2,50019836	1,500198364	1,75020981	0,75020981

f) T_H1ist nun 5 ns = 2,5 T, gesucht ist r_H1, damit T_Access -T < 1,9

Mit dem Ergebnis aus e):

r_H0 * T_H0 + (1- r_H0) * (r_H1 * T_H1 + (1- r_H1) * T_HHS ) - T < 1,9

ó 0,5 + 0,5 * (r_H1* 2,5 + (1- r_H1) * 30 ) - 1 < 1,9

ó (r_H1* 2,5 + (1- r_H1) * 30 ) < 4,8

ó -r_H1* 27,5 < -25,2

ó r_H1 > 0,916

Nach der Tabelle aus Teilaufgabe f erreicht der Cache diese Hitrate.

g) Es ist T_H2 = 10 ns = 5 T . Außerdem gilt nun:

T_Access = r_H0*T_H0+(1-r_H0)*(r_H1*T_H1+(1-r_H1)*(r_H2* T_H2+(1-r_H2)*T_HHS ))

Mit

r_H0=0,5 T_H0=1 T;

r_H1= 0,96875 T_H1= 2,5 T

r_H2= 0,99951172 T_H2= 5 T

r_HHS= 1 T_HHS = 30 T )

Ergibt sich

T_Access = 1,78925323

also muß der Prozessor nun lediglich noch rund 0,789 Waitstates einlegen