Institut für Rechnerentwurf und
Fehlertoleranz

Jürgen Ruf

4. Übungsblatt und Lösungen zur Vorlesung Rechnerstrukturen

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.

Die Effizienz gibt die relative Verbesserung der Verarbeitungsgeschwindigkeit an. Wenn man mit der 30-fachen Zahl von Prozessoren nur die 6-fache Geschwindigkeit erzielt, ist die Effizienz:

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

Geben sie den Parallelindex I(30) an.

Der Parallelindex gibt die Anzahl der parallelen Operationen pro Zeiteinheit an. Die Maschine muß 120 Operationen in 50 Zeiteinheiten ausführen:

Im Mittel sind nur 2,4 der 30 Prozessoren bei der Bearbeitung dieses Beispiels aktiv.

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	M/8	E/12	I/-	E/6	E/10	I/-
1	read 10	M/8	E/12	S/10	E/6	S/10	I/-
2	read 8	S/8	E/12	S/10	E/6	S/10	S/8
1	write 8	M/8	E/12	S/10	E/6	S/10	I/-
1	write 8	M/8	E/12	S/10	E/6	S/10	I/-
1	read 18	M/8	E/18	S/10	E/6	S/10	I/-
2	write 10	M/8	E/18	I/-	E/6	M/10	I/-
2	write 18	M/8	I/-	I/-	E/6	M/10	M/18

4. Verbindungsnetzwerke

Gegeben sei ein Multiprozessor bestehend au 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.

Durchsatz:

Bisektionsbreite:

Verbindungsgrad:

Durchmesser:

Diskonnektivität: Bei der Bisektionierung will jeder Knoten der einen Hälfte an jeden Knoten der anderen Hälfte eine Nachricht verschicken und umgekehrt (worst case für die Kommunikation)

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.
Die Länge der Pipeline ist k = 9. Die Werte müssen drei Takte lang anliegen, damit bei der Rückkopplung die richtigen Werte addiert werden. Alle drei Takte erscheint somit ein neuer Produktsummenwert. Für die Berechnung des Durchsatzes und der Half-Performance-Length kann man die Taktrate durch drei Teilen und erhält somit eine Multiplizierer mit zwei Pipelinestufen und einen Addierer mit nur einer Stufe. Die Pipeline hat drei Stufen und in jedem Taktzyklus liegt dann ein neuer Wert für x_i, y_i und z_i an:
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).

Die Pipeline hat 7 Stufen (6 vom Multiplizierer und 3/3 vom beschleunigten Addierer) k_p = 7, s_p = 13. Bei der Schaltung ohne Pipeline können der Multiplizierer und der Addierer so parallel geschaltet werden, daß alle drei Takte ein Ergebnis anliegt (k_k = 3), außer beim ersten Wertepaar, da muß man einen zusätzlichen Takt vom Addierer warten, der noch nicht rechnen konnte (s_k = 1).

Ab Vektoren der Länge neun rentiert sich der Einsatz der Pipeline.