Institut für Rechnerentwurf und Fehlertoleranz

3. Übungsblatt zur Vorlesung Rechnerstrukturen

Die Besprechung dieses Übungsblattes findet am Donnerstag, den 4. Juni 1998 um 14:00 in Tulla-Hörsaal statt. Die Musterlösung wird im Anschluß an die Übung im WWW zu finden sein. Bei Fragen zu diesen Übungen: Sprechstunde am Montag, den 8. Juni 1998 von 14:00 bis 16:00 Uhr.

1. Aufgabe (Cachespeicher)

Gegeben seien drei kleine Cachespeicher DM, A2 und AV, die jeweils 8 Cacheblöcke enthalten, wobei jeder Cacheblock vier Datenworte 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 Datenworten 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)

1. Welcher technologische Unterschied besteht zwischen Cache und Hauptspeicher?
2. 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).
3. 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.
4. 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 Datenworte m[x1-x4]. Dabei sollen mit der Schreibweise m[x1-x4] die aus dem Speicherbereich [x1,x4] gelesenen Datenworte repräsentiert werden.

2. Aufgabe (Speicherhierarchie)

Ein Prozeß führt nacheinander Lesezugriffe auf die folgenden logischen Speicheradressen durch (alle Adreßangaben sind in hexadezimaler Darstellung):

1234A000, 1234A00A, 1234A010, 1234A023, 1234B050, 1234A00C, 1234B060, 1236FF60

Der Mikroprozessor verfügt über einen First-Level Cache mit 2 Blockrahmen und über einen Secondary-Level Cache mit 4 Blockrahmen. Jeder Block enthält 16 Datenworten. Der Cache ist vollassoziativ organisiert und wird physikalisch adressiert. Es wird die LRU-Verdrängungsstrategie (Least Recently Used) angewandt. Am Anfang seien beide Caches leer.

Gemäß der Segmenttabelle hat der Prozeß Zugriffsrechte auf ein Speichersegment der Größe 64k. Das Segment wird logisch mit den Adressen 12340000 - 1234FFFF adressiert und befindet sich auf den virtuellen Adressen 00010000 - 0001FFFF. Der Prozeß besitzt keine weiteren Speichersegmente. Die Segmenttabelle ändert sich während des betrachteten Zeitraums nicht.

Der Rechner verfügt über 1M Hauptspeicher und über 4G Sekundärspeicher. Die Seitengröße beträgt 4k. Am Anfang seien zufällig alle Seiten mit der virtuellen Anfangsadressen 00xyA000 im Hauptspeicher, wobei sich in diesem Augenblick gerade jede Seite mit der virtuellen Adresse 00xyA000 an der physikalischen Adresse 000xy000 befindet (x und y stehen für beliebige Hexadezimalstellen). Alle anderen Seiten seien anfangs im Sekundärspeicher ausgelagert. Die Seitentabelle sieht damit anfangs wie folgt aus:

Das Betriebssystem sei so realisiert, daß bei einem Seitenfehler immer die Seite mit der kleinsten virtuellen Adresse ausgelagert wird.

Beschreiben Sie die Operationen auf First-Level Cache, Secondary-Level Cache, Hauptspeicher und Sekundärspeicher. Tragen Sie in die nachfolgende Tabelle die virtuellen und physikalischen Adressen ein, die bei den Speicherzugriffen erzeugt werden. Tragen Sie ferner die Zustände der Caches und der Seitentabelle zwischen den Zugriffen ein. Es soll eingetragen werden, welche Blöcke (physikalische Adresse) gerade in den Caches gepuffert werden und welche Seiten (virtuelle Adresse) sich gerade im Hauptspeicher an welcher Stelle (physikalische Adresse) befinden. Von der Seitentabelle soll nur der Teil berücksichtigt werden, der innerhalb des betrachteten Segments liegt.

3. Aufgabe (Verbindungsnetzwerke)

Um mehrere Prozessoren eines Multiprozessorsystems miteinander zu vernetzen kann man Verbindungsnetzwerke aus Zweierschaltern verwenden (siehe Skript S.147). Das Benesnetzwerk ist ein solches Verbindungsnetzwerk mit 2^d Eingängen und 2^d Ausgängen. Es hat folgende Struktur:

d = 1:
d = 2:
d = 3:
Rekursiver Aufbau :

1. Wieviele Zeilen und Spalten hat ein Benesnetzwerk der Ordnung d?
2. Zeigen Sie, daß das Benesnetzwerk universell ist, d.h. jede Permutation erzeugen kann. Es empfiehlt sich ein konstruktiver Induktionsbeweis über d.
3. Konstruieren Sie für d = 3 eine Schalterstellung, die die Permutation (3,0,1,2,4,6,5,7) erzeugt.