Institut für Rechnerentwurf und Fehlertoleranz

 

Dr. Wolfgang Karl
Dipl.-Inform. Dirk Osswald
23. Mai 2002

3. Übungsblatt zur Vorlesung Rechnerstrukturen:
Virtuelle Speicherverwaltung, Cache


Die Besprechung dieses Übungsblattes findet am Mittwoch, den 29. Mai 2002, um 15.45 Uhr im HMU statt. Die Musterlösung ist nach der Übung im WWW zu finden unter http://wwwipr.ira.uka.de/~lehre/RS/index.html

1. Aufgabe (Verständnisfragen)

a)      Warum werden Cache-Speicher verwendet und wo werden sie im Rechner eingesetzt?

b)      Cache Speicher müssen auf die Daten ebenfalls über den Hauptspeicher zugreifen. Warum ist der Datenzugriff über den Cache Speicher trotzdem schneller?

c)      Was ist ein Tag-Speicher und wozu wird er verwendet?

2. Aufgabe (Cache Strukturen)

a)      Nennen Sie drei Cache Strukturen (Organisationsformen für Caches).

b)      Beschreiben Sie unter Verwendung der in der Vorlesung eingeführten Bezeichnungen die Zuordnung von Hauptspeicherblöcken zu Cache-Blockrahmen für die drei Cache Strukturen.

c)      Was ist der Cache-Abdeckungsgrad und was ist der Assoziativitätsgrad?

d)      Berechnen Sie den oder die Cache-Blockrahmen auf die Hauptspeicherblock 12 bei den drei Cache Strukturen abgebildet wird. Der Cache habe 8 Blockrahmen, ein Block enthalte immer nur ein Wort, der Hauptspeicher habe 64 Worte.
Geben Sie jeweils Cache-Abdeckungsgrad und Assoziativitätsgrad an.

e)      Welche Arten von Ersetzungsstrategien/Verdrängungsstrategien gibt es und für welche Arten von Caches werden diese benötigt?

f)        Wodurch unterscheidet sich die Rückschreibe- von der Durchschreibe-Strategie?

3. Aufgabe (Cache-Speicher)

Ein Rechner habe 64 kB Hauptspeicher (16-Bit Adressen) der in Blöcke von je 32 Byte unterteilt ist. Zur Auswahl stehen die folgende Cache-Arten, die alle 2 kB Datenspeicher besitzen:

I.)    direkt abgebildeter Cache

II.)   vollassoziativer Cache

III.) 4-fach-Satz-assoziativer Cache

a)      Geben Sie für die 3 Cache-Architekturen jeweils den Assoziativitätsgrad und die Anzahl der Sätze an.

b)      Erklären Sie die Begriffe Tag, Index und Block Offset.

c)      Geben Sie die Länge in Bit der drei Cache-Parameter Tag, Index und Block Offset jeweils für I), II) und III) an.

d)      Wie groß muss der Tag Speicher (ohne zusätzliche Status-Bits) für diesen Cache insgesamt mindestens sein?

e)      Betrachten Sie untenstehendes Programm unter Berücksichtigung der Cache-Architekturen I und II. (Bei Programmbeginn sind die Caches leer.)

Welche der beiden Cache-Architekturen hat für dieses Programm unter den gegebenen Voraussetzungen einen deutlichen Geschwindigkeitsvorteil? Geben Sie eine qualitative und quantitative Betrachtung. (Was wird wodurch und wann aus dem Cache verdrängt?)

 

Folgendes Programm befindet sich im sonst leeren Hauptspeicher (d.h. alle anderen Speicherstellen weisen den Wert 0 auf!):

 

Zeile HS-Adr. Befehl                     Erläuterung

1     0x0028  ADD   R3,    R0,   R0       ;R3 <- R0 + R0  

2     0x002c  ADDI  R2,    R0,   #0x0111  ;R2 <- R0 + 0x0111

3     0x0030  ADDI  R1,    R0,   #0x2034  ;R1 <- R0 + 0x2034

4     0x0034  SW    0(R1), R2            ;M[R1 + 0] <- R2

5     0x0038  SW    4(R1), R3            ;M[R1 + 4] <- R3

6     0x003C  ADDI  R2,    R2,   #0x00FF  ;R2 <- R2 + 0x00FF

7     0x0040  LW    R4,    0(R1)         ;R4 <- M[R1 + 0]

8     0x0044  ADDI  R1,    R0,   #0x0028  ;R1 <- R0 + 0x0028

9     0x0048  ADDI  R3,    R4,   #0x5F17  ;R3 <- R4 + 0x5F17

10    0x004C  LW    R5,    0(R3)         ;R5 <- M[R3 + 0]

11    0x0050  SUB   R6,    R2,   R5       ;R6 <- R2 - R5

12    0x0054  ADDI  R3,    R3,   #0x0018  ;R3    <- R3 + 0x0018

13    0x0058  SW    4(R3)  R6            ;M[R3 + 4] <- R6

14    0x005C  JR    R1                   ;PC    <- R1

 

f)        Im Folgenden soll nur noch der direkt-abgebildete Cache betrachtet werden:

Die Vorbelegung des Caches ist in Bild 1 dargestellt.

Bild 1: Cache Vorbelegung

 

Bei dieser Belegung soll auf die folgenden Hauptspeicheradressen der Reihe nach zugegriffen werden:

1.) Dez:  6856 Hex: 1AC8 Dual: 0001 1010 1100 1000

2.) Dez: 13028 Hex: 32E4 Dual: 0011 0010 1110 0100

3.) Dez: 13029 Hex: 32E5 Dual: 0011 0010 1110 0101

4.) Dez: 15156 Hex: 3B34 Dual: 0011 1011 0011 0100

5.) Dez: 25528 Hex: 63B8 Dual: 0110 0011 1011 1000

6.) Dez: 60236 Hex: EB4C Dual: 1110 1011 0100 1100

Geben Sie an, welche freien Cacheplätze belegt werden, bzw. welche Hauptspeicheradressen aus dem Cache verdrängt werden.

 

4. Aufgabe (Virtuelle Speicherverwaltung)

Der folgende aus der digitalen Signalverarbeitung stammende Algorithmus soll auf einem Prozessor mit virtueller Speicherverwaltung ausgeführt werden:

   (01) FOR i = 0 TO 2^13-1

   (02)     y = 0;

   (03)     FOR j = 0 TO 2

   (04)         y = y + x[i+j] * w(j);

   (05)     END

   (06)     y[i] = y;

   (07) END

Der Prozessor verfügt über drei Segmentregister: CS für Programmcode, DS für Datenstrukturen und SS für den Stapel. Die Auswahl eines Segmentregisters erfolgt implizit durch den auszuführenden Befehl. Die Bildung der virtuellen Adresse erfolgt durch Addition der Basisadresse mit der logischen Adresse. Die Seitengröße beträgt 4096 Worte, wobei der Hauptspeicher maximal 4 Seiten aufnehmen kann. Seiten der CS- und der SS-Segmente werden vom Betriebssystem nicht ausgelagert. Als Ersetzungsstrategie kommt LRU zum Einsatz. Die Segmentregister sind wie folgt belegt:

Segment

Basisadresse (hex.)

Länge (hex.)

CS

3A17C000

1000

DS

D29E4000

4000

SS

51F60000

1000


Das Feld x im obigen Programm beginnt an der logischen Adresse 2000, y bei 0. Die Seitentabelle enthält zu Beginn folgende Einträge:

Virtuelle Adresse

Physikalische Adresse

Hauptspeicher

3A17C

0

ja

51F60

1

ja

D29E6

2

ja

D29E7

3

ja

 

a)      Erstellen Sie ein Protokoll der ein- und ausgelagerten Seiten während der Ausführung des Programms solange keine Zugriffsverletzung auftritt. Geben Sie jeweils die Iteration und die Zeilennummer an, bei der ein Seitenfehler auftritt. Wie viele Seitenwechsel werden insgesamt durchgeführt?

b)      Gibt es eine Strategie zur Seitenersetzung, die besser ist als LRU? Wenn ja, wie viele Ein-/Auslagerungen müssen dann durchgeführt werden?


5. Speicherhierarchie

Ein mit 500MHz getakteter 32-bit Rechner besitze 256 MB Hauptspeicher. Dieser hat eine Zugriffszeit von 60 ns für den wahlfreien Zugriff. Die CPU verfügt über 256 Vielzweckregister, auf die im Prozessortakt zugegriffen werden kann.

 

a)      Weshalb teilt man den Speicher in unterschiedliche Ebenen ein?

b)      Fassen Sie das Registerfile als Level-0 Cache auf. Wie groß ist dieser Cache?

c)      Im Folgenden sollen mehrstufige Speicherhierarchien untersucht werden. Die Wahrscheinlichkeit, ein gesuchtes Datum im 'Register-Cache' zu finden betrage rH0 = 0.5 ('r' für 'rate', 1.Index 'H' für 'Hit', 2.Index '0' für 'Level 0'. Ausgehend hiervon soll für die darunterliegenden Speicherebenen allgemein gelten, dass die Wahrscheinlichkeit eines Hits (rHx) um 50% zunimmt, wenn man die Cachegröße der Ebene verdoppelt. Die Cachegröße (in kB) einer Ebene soll in Abhängigkeit vom Parameter n nach folgender Formel angeben werden.

SC = 1kB * 2n (n=1,2,...).

Die Daten liegen auf jeden Fall im Hauptspeicher.

Zunächst soll nur ein Level-1 Cache eingesetzt werden, dessen Größe Sie dimensionieren  sollen.

Skizzieren Sie das Speichersystem und geben Sie die Wahrscheinlichkeit an, mit der ein Datum sich in den einzelnen Komponenten befindet. Wie groß ist die L1-Hitrate bei minimaler Cachegröße (n=1)? Wie groß ist sie jeweils für die nächsten beiden Größen (n=2, n=3). Entwickeln Sie die Formel allgemein für die n-te Größe.

Hinweis: Folgende Formeln könnten hilfreich sein.

d)      Der eingesetzte Cachespeicher habe eine Zugriffszeit von 8 ns. Wieviele Waitstates muss der Prozessor durchschnittlich einlegen, wenn alle Daten spätestens im L1 Cache gefunden werden (also für rH1 = 1.0). Wieviele verursacht sonst der Cache und wieviele der Hauptspeicher in Abhängigkeit von rH1 (also für 0< rH1 < 1.0)?

e)      Wie groß muss der Cache mindestens sein, damit durchschnittlich nicht mehr als 2 Waitstates eingelegt werden müssen? Benutzen Sie die Ergebnisse aus d) und e)!

f)        Um die Performance zu erhöhen, wollen Sie nun für den L1-Cache Speicher mit 5 ns Zugriffszeit einsetzen. Dieser ist leider so teuer, dass Sie sich nur 16kB leisten können.
Wie groß muss die Hitrate sein, damit sich eine Verbesserung ergibt (weniger als 1.9 durchschnittliche Waitstates)? Erreicht der Cache unter den Voraussetzungen aus d) (n=4) diese Hitrate ?

g)      Sie haben die Möglichkeit, günstig 10 ns Speichermodule zu erwerben. Wieviele Waitstates muss der Prozessor durchschnittlich einlegen, wenn Sie einen 1 MB großen L2 Cache mit diesem Speicher einbauen?