Institut für Rechnerentwurf und
Fehlertoleranz

Jürgen Ruf

4. Übungsblatt zur Vorlesung Rechnerstrukturen

Die Besprechung des Übungsblattes findet am Donnerstag den 25. Juni 1998 statt. Die Musterlösungen ist im WWW zu finden. Eine Sprechstunde zu diesem Übungsblatt findet am Montag 29.6.1998 von 14.00-16.00 Uhr im Raum 266, Geb. 20.20 statt.

1. Leistungsfähigkeit von Multiprozessorsystemen

Gegeben sei ein Multiprozessorsystem mit 30 Prozessoren. Die Leistungssteigerung bezüglich eines Einprozessorsystems sei S(30) = 6. Die Ausführungszeit auf einem Einprozessorsystems sei T(1) = 300 und die Anzahl der auszuführenden (Einheits-) Operationen auf dem Multiprozessorsystem sei P(30) = 120.

Geben sie die Effizienz E(30) an.

Berechnen sie die Ausführungszeit des Multiprozessorsystems T(30).

Geben sie den Parallelindex I(30) an.

2. Amdahls Gesetz

Geben sie Amdahls Gesetz an. Was sagt dieses Gesetz aus? Leiten sie mit Hilfe dieses Gesetzes eine obere Schranke für den Speed-up S(n) eines Multiprozessorsystems her.

Amdahls Gesetz kann auch für allgemeine Optimierungen eingesetzt werden:

_new

_opt

_old

Gegeben sei ein optimierter Prozessor dessen Festpunkteinheit doppelt so schnell arbeitet wie der Standardprozessor. Weiterhin sei ein Programm gegeben, das zu 20% aus Festpunktoperationen besteht. Berechnen Sie den Speedup der mit dem optimierten Prozessor erreicht werden kann.

3. MESI-Protokoll

Gegeben sei ein speichergekoppeltes Multiprozessorsystem mit zwei Prozessoren, die über einen Bus mit einem globalen Speicher verbunden sind. Zur Wahrung der Cache Kohärenz wird das MESI Protokoll verwendet. Die Caches der beiden Prozessoren haben je eine Größe von drei Cache-Lines die genau ein Speicherwort aufnehmen können. Die Caches werden von der niedrigsten Cache-Line aufwärts gefüllt, falls noch freie Lines zur Verfügung stehen. Im Falle eines voll besetzten Caches werden sie nach der Strategie LRU (least recently used) überschrieben. Ergänzen Sie die folgende Tabelle, wobei die Buchstaben die Zustände: M = exclusive modified, E = exclusive unmodified, S = shared unmodified, I = invalid repräsentieren. Die Zahlen hinter den Aktionen und Zuständen bezeichnen Speicheradressen.

Prozessor	Aktion	Cache1 Line1	Cache1 Line2	Cache1 Line3	Cache2 Line1	Cache2 Line2	Cache2 Line3
-	-	E/8	E/12	I/-	E/6	I/-	I/-
2	read 10	E/8	E/12	I/-	E/6	E/10	I/-
1	write 8
1	read 10
2	read 8
1	write 8
1	write 8
1	read 18
2	write 10
2	write 18

4. Verbindungsnetzwerke

Gegeben sei ein Multiprozessor bestehend aus N = 6 Prozessorknoten und einem statischen Verbindungsnetz, das jeden Prozessor mit allen anderen Prozessoren verbindet (vollverbundenes Netzwerk). Jede Verbindung habe die gleiche (Einheits-) Bandbreite und sei bidirektional.

Geben sie den maximalen Durchsatz in Einheitsbandbreiten an. Bestimmen Sie die minimale Bisektionsbreite, den Verbindungsgrad, den Durchmesser und errechnen Sie daraus die Diskonnektivität.
Leiten Sie eine allgemeine Formel für den maximalen Durchsatz und die Diskonnektivität für vollverbundene Netzwerke mit gerader Knotenzahl her (auch wieder in der Maßeinheit Einheitsbandbreite).

5. Vektorrechner

Zur Konstruktion einer Pipeline stehen drei verschiedene Rechenwerke zur Verfügung:

Ein Multiplizierer der als Pipeline mit 6 Stufen realisiert ist
Ein Addierwerk, das drei Pipelinestufe benötigt
Eine beliebige Anzahl von Verzögerungselementen, die den Eingangswert nach einem Taktzyklus an den Ausgang weiterleiten

Konstruieren sie eine Pipeline aus den gegebenen Elementen, die nacheinander die Produktsummen der Eingangsvektoren x und y berechnet:
Wieviele Stufen hat die Pipeline, wie lange müssen die Wertepaare (x_i,y_i) am Eingang anliegen, damit am Ausgang die korrekten Werte für z_i erscheinen. Berechnen Sie den Grenzwert des Durchsatzes und die Half-Performance-Length für die in 1. konstruierte Pipeline wenn diese mit einer Taktrate von 60 MHz betrieben wird.
Da der Addierer und das Verzögerungsglied einen einfachen internen Aufbau haben, ist es möglich ihre Taktfrequenz zu verdreifachen (Superpipelining). Konstruieren sie eine Pipeline ohne Steuerlogik, die in jedem Taktzyklus ein Ergebnis z_i liefert.
Berechnen Sie den Trade-Off Punkt der in 3. konstruierten Pipeline, wenn diese durch einen Controller gesteuert wird, der zum Einrichten der arithmetischen Komponenten 13 Taktzyklen benötigt. Ein vergleichbarer Multiplizierer, der nicht auf Pipelinebasis arbeitet, benötigt 3 Taktzyklen (bei 60 MHz) und der entsprechende Addierer braucht einen Takt (bei 60 MHz).