2. Übungsblatt zur Vorlesung Rechnerstrukturen
Die Besprechung des Übungsblattes findet am Dienstag,
den 23. Mai 1995 um 14.00 Uhr im HMU statt.
Die Musterlösung wird im Anschluß an die
Übung im WWW zu finden sein.
4. Aufgabe (Cachespeicher)
Gegeben seien drei kleine
Cachespeicher DM, A2 und AV, die jeweils 8 Cacheblöcke enthalten, wobei jeder
Cacheblock vier Bytes umfaßt. Cache DM ist als direct mapped Cache organisiert,
Cache A2 als 2-fach assoziativer Cache und Cache AV ist voll assoziativ. Bei A2
und AV soll die LRU-Ersetzungsstrategie angewendet werden. Nehmen Sie an, die
Caches seien zu Beginn leer und es soll eine Serie von einzelnen Bytes mit den
folgenden 32-Bit-Adressen gelesen werden:
294928070, 294928009, 294928039, 294928083, 294928066, 294928068, 294928035,
294928080, 294928093, 294928067, 294928079, 294928037, 294928084, 294928009
(294928000d = 0001 0001 1001 0100 0011 1110 1000 0000b)
- Welcher technologische Unterschied besteht zwischen Cache und Hauptspeicher?
- Geben Sie zunächst für
alle drei Cachespeicher an, wieviel Bits zur Verwaltung eines Cacheblocks
benötigt werden. Dabei sollen für den Zustand des Cacheblocks 2 Bits verwendet
werden (ein Valid-Bit und ein Dirty-Bit).
- Geben Sie nun für jeden Cache an,
ob es sich beim Lesezugriff auf die jeweilige Adresse um einen Cache-Hit oder um
einen Cache-Miss handelt.
- Stellen Sie den Zustand der drei Caches nach dem
letzten Speicherzugriff dar, d.h. für jeden Cache-Block den Cache-Tag und die
vier Datenbytes m[x1-x4]. Dabei sollen mit der Schreibweise m[x1-x4] die aus dem
Speicherbereich [x1,x4] gelesenen Datenbytes repräsentiert werden.
5. Kontrollfragen (ohne Musterlösung)
- Wieviele und welche Anschlüsse hat ein 1 MBit-Speicherchip?
- Wie heißen die verschiedenen Ebenen der Speicherhierarchie?
Wer organisiert jeweils die Zugriffe? Wie lange dauert ein Zugriff?
- Wieviel kostet derzeit ein MByte in den verschiedenen Ebenen?
- Wodurch ist es möglich, auf einem Rechner mit 12 MB Hauptspeicher
Programme laufen zu lassen, die 20 MB Speicher benötigen?
- Wozu dient die Schnüffellogik?
- In welchen Größenordnungen liegen die Zeitabstände des Wiederauffrischens
von Dynamischem RAM?
- Wie lautet die Mehrzahl von "Datenwort", "Speicherwort", "Datenbank" und "Speicherbank"?
6. Aufgabe (Cachekohärenz, MESI-Protokoll)
Das MESI Cachekohärenzprotokoll arbeitet mit einem write-invalidate Verfahren,
d.h. bei einer Schreibaktion werden alle Lesekopien der anderen Caches invalidiert.
- Jeder Cache-Line ist nach dem MESI-Protokoll ein Zustand zugeordnet. Geben Sie für die
vier Zustände (exclusive Modified, Exclusive unmodified, Shared unmodified und Invalid)
eine Codierung an, welche mit drei Bits auskommt: einem Valid-Bit, falls die Cache-Line gültig ist,
einem Dirty-Bit, falls die Cache-Line verändert wurde, und einem Shared-Bit, falls die Cache-Line
auch in einem anderen Cache vorhanden ist.
- Im obigen Multiprozessorsystem führen die drei Prozessoren P1, P2 und P3 eine Folge
von Lese- und Schreibzugriffen auf die Adresse 4711 aus. Veranschaulichen Sie
sich die Zustandsübergänge der entsprechenden Cache-Lines nach dem MESI-Protokoll,
indem Sie die folgende Tabelle ausfüllen. Nehmen Sie dabei an, daß die Caches anfangs leer sind.
Cache 1 Cache 2 Cache 3
Operation E Z A E Z A E Z A
- I - - I - - I -
P1: read 4711
P2: read 4711
P3: write 4711
P3: write 4711
P2: write 4711
P1: read 4711
In der Spalte Operation ist angegeben, welcher Prozessor einen Lese- bzw.
Schreibzugriff durchführt. In der Spalte E soll das Ereignis angegeben werden,
welches der Zustandsänderung zugeordnet ist (z.B. RH, WH, SHR, SMR). In der
Spalte Z soll der neuen Zustand stehen, und in die Spalte A soll die Aktion
eingetragen werden, die dabei auszuführen ist (d.h. "Pfeil nach oben" für Cache line fill
oder "Pfeil nach unten" für Dirty line copyback).
Felix Holderied