Institut für Rechnerentwurf und Fehlertoleranz

Dr. W. Karl

Frank Beeh

13. Juni 2002

4. Übungsblatt zur Vorlesung Rechnerstrukturen:
Verbindungsstrukturen, Leistungsfähigkeit von Multiprozessorsystemen, MESI-Protokoll

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

1. Aufgabe (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
1	write 8
1	read 10
2	read 8
1	write 8
1	write 8
1	read 18
2	write 10
2	write 18

2. Aufgabe (Leistungsbewertung)

Gehen Sie im Folgenden davon aus, dass der sequentielle Prozessor eine Operation pro Takt ausführt, d. h. T(1)=P(1).

(a) Vergleichen Sie den Beschleunigung und den Parallelindex unter der Bedingung, dass der Mehraufwand R(n)=1 ist.

(b) Wodurch ist ein Mehraufwand R(n)>1 begründet?

(d) Geben Sie die Werte für die Beschleunigung, die Effizienz, den Mehraufwand, den Parallelindex und die Auslastung eines Einprozessorsystems an.

(e) Welches Verhalten erwarten Sie im Normalfall von der Beschleunigung und der Effizienz bei einer steigenden Prozessoranzahl?

3. Aufgabe (Ahmdals Gesetz)

Gegeben sei ein Programm. Es benötigt auf einem Einprozessorsystem die Ausführungszeit T(1) = 1000. Dieses Programm wird auf ein Multiprozessorsystem portiert. Es kann entweder mit 10 oder mit 20 Prozessoren abgearbeitet werden und benötigt hierfür T(10) = 650 bzw. T(20) = 625.

(a) Berechnen Sie mit Hilfe von Amdahls Gesetz den prozentualen Anteil a des nur sequentiell ausführbaren Programmteils in beiden Fällen.

(b) Weshalb erhalten Sie unterschiedliche Werte für a?

(c) Beachten Sie nun, dass in T(n) auch Synchronisations- und Kommunikationszeiten T_s enthalten sind. Erweitern Sie das Amdahlsche Gesetz so, dass dies berücksichtigt wird. Gehen Sie hierbei davon aus, dass T_s nicht von der Anzahl der Prozessoren abhängt und von einem, im Ursprungsprogramm nicht vorhandenen, und nur sequentiell ausführbaren Programmteil herrührt. Bestimmen Sie nun mit Hilfe von T(10) und T(20) die Werte für T_s und a.

(d) Berechnen Sie den Speedup S(10) und S(20). Berechnen Sie den maximal erreichbaren Speedup.

(e) Berechnen Sie die Effizienz E(10) und E(20). Wie viele Prozessoren können maximal eingesetzt werden bevor die Effizienz unter 0,5 sinkt?

(f) Wie beurteilen Sie die Parallelisierbarkeit des Programms?

4. Aufgabe (statische Verbindungsstrukturen)

Untersuchen Sie die Verbindungsstrukturen Ring, 2D-Gitter, 2D-Thorus, Baum und Hyperkubus hinsichtlich folgender Punkte:

· Sinnvolle Ausbaustufen welche ein regelmäßiges Verbindungsmuster ergeben.

· Verbindungsgrad

· Durchmesser

· minimale Bisektionsbreite

· Diskonnektivität

· Kosteneffektivität

5. Aufgabe (dynamische Verbindungsstrukturen)

Es soll ein Permutationsnetzwerk mit Kreuzschaltern entworfen werden.

(a) Wie viele Kreuzschalter k werden mindestens benötigt, um ein universelles Netzwerk mit n Eingängen und n Ausgängen zu erstellen?

(b) Zählen Sie zwei Verbindungsnetzwerke, welche auf Permutationsnetzwerken aufgebaut sind, auf und nennen Sie die Permutationen die ihnen zugrunde liegen.

(d) Sind diese Netzwerke blockierungsfrei? Begründen Sie Ihre Meinung?

(e) Schätzen Sie den asymptotischen Aufwand an Kreuzschaltern k für universelle Permutationsnetzwerke mit n Ein- und Ausgängen ab. Vereinfachen Sie das Ergebnis soweit wie möglich. Sie benötigen hierzu die Stirlingsche Formel: