Institut für Rechnerentwurf und Fehlertoleranz

Prof. Dr. Th. Ungerer

Michael Syrjakow

19. Juni 1997

Blatt4

4. Übungsblatt zur Vorlesung Rechnerstrukturen

Die Besprechung des Übungsblattes findet am Donnerstag den 19. Juni 1997 statt. Die Musterlösung wird im Anschluß an die Übung im WWW unter http://goethe.ira.uka.de//edu/rechnerstrukturen/SS97/homepage.html zu finden sein. Bei Fragen zu diesen Übungen stehen Ihnen Montags von 14.00-16.00 Sprechstunden zur Verfügung.

1. Aufgabe (Vektorrechner)

Betrachte ein vierstufiges Addierwerk für normalisierte Gleipunktzahlen mit 10ns Verzögerung pro Stufe. Die Pipelinetaktfrequenz entspreche der Verzögerung einer Stufe. Neben Addierwerken stehen Verzögerungsglieder zur Verfügung.

Konstruieren Sie aus den eingeführten Bestandteilen eine Pipeline, mit der aus dem Vektor a1... an der Vektor b1... bn mit bi= ai+ai-1 erzeugt wird, wobei a0=0 gesetzt wird.
Zählen Sie die Taktzyklen zur Bearbeitung eines Vektors der Länge n, d.h. wieviele Taktzyklen werden benötigt, bis das Element bn die Pipeline verläßt?

Wie läßt sich die Pipeline modifizieren, um damit folgende Zahlenfolge für i>=0 zu berechnen:

    ai = ai-4+ai-8        für  i > 3 
    a0 = a1 = a2 = a3 =1 
    ai = 0                für  i < 0;

Wie lange dauert es, bis die n-te Fibonacci-Zahl berechnet ist?

2. Aufgabe (Vektorrechner Kenngrößen)

Ein Vektorrechner habe eine achtstufige Pipeline, deren Startzeit 5 Taktzyklen beträgt. Für eine skalare Operation benötigt der Prozessor 3 Taktzyklen. Die Maschine wird mit einer Taktfrequenz von 90 MHz betrieben.

Berechnen Sie den Grenzwert des Durchsatzes für den beschriebenen Vektorrechner im Idealfall.
Wie lang sollten die Vektoren nach dem Maß "half-performance length" ohne Berücksichtigung der Startzeit sein?
Berechnen Sie den Trade-Off-Punkt.

Kontrollfragen

Das folgende sind Fragen zu Stichworten des bisher behandelten Stoffs. Sie sollen dazu dienen, das eigene Wissen zu überprüfen und dazu anregen, die entsprechenden Kapitel im Skript noch einmal aufzuschlagen.

Worin liegen die Besonderheiten der Vektorrechner ?
Was versteht man unter der Effizienz eines Pipeline-Prozessors ?
Unter welchen Bedingungen ist ein Pipeline-Prozessor von der Bearbeitungszeit her günstiger als ein serieller Prozessor ?

3. Aufgabe (Leistungsfähigkeit von Multiprozessorsystemen)

Gegeben sei ein Multiprozessorsystem mit 16 Prozessoren. Die Leistungssteigerung bezüglich eines Einprozessorsystems sei S(16) = 4. Die Ausführungszeit auf dem Einprozessorsystem sei T(1) = 32 und die Anzahl der auszuführenden (Einheits-) Operationen auf dem Multiprozessorsystem sei P(16) = 40.

Geben Sie die Effizienz E(16) an.
Berechnen Sie die Ausführungszeit des Multiprozessorsystems T(16).
Geben Sie den Parallelindex I(16) an.
Welcher Bruchteil der Programme ist nach Amdahls Gesetz nur sequentiell ausführbar?
Durch welchen Wert wird die Leistungssteigerung begrenzt, wenn man die Anzahl der Prozessoren beliebig erhöht?

4. Aufgabe (Adressierung in Multiprozessorsystemen)

Ein Multiprozessorsystem sei mit einer Pyramidenstruktur aus e Ebenen verbunden.

Wieviele Knoten hat eine Pyramide mit e Ebenen?
Wieviele Nachbarn kann ein Knoten maximal haben?
Geben sie ein Adressierungsschema für die Knoten an.
Geben sie die Adressen aller Nachbarknoten eines Knotens an, sowie die Bedingungen für die Existenz des Nachbarn.

5. Aufgabe (Modellierung von Multiprozessorsystemen)

Abb. 1 zeigt die Architektur eines speichergekoppelten Multiprozessor-Systems mit einem Mehrfachbus, das aus drei Komponententypen zusammengesetzt ist: Prozessoren P, globale Busse B und Speichermodule S. Im Normalfall (aktiver Zustand) arbeiten die Prozessoren in ihrem lokalen Speicherbereich (hier der Einfachheit halber nicht eingezeichnet) ein Programm ab. Um miteinander zu kommunizieren, greifen sie über die globalen Busse B auf die Speichermodule S zu.

Abb. 1: Speichergekoppeltes Multiprozessor-System mit Mehrfachbus

Mit dem GSPN (Generalized Stochastic Petri Net) aus Abb. 2 wird ein speichergekoppeltes Multiprozessor-System mit Mehrfachbus modelliert, das aus 4 Prozessoren, 2 globalen Bussen und 3 Speichermodulen zusammengesetzt ist (kurz 4x2x3 MP-Architektur). Gegenstand der Modellierung ist der Zugriff der Prozessoren P auf die Speichermodule S über die globalen Busse B.

Abb. 2: GSPN-Modell einer 4x2x3 Multiprozessor-Architektur

Beantworten Sie die folgenden Fragen:

Wodurch unterscheiden sich Standard-Petrinetze von den hier verwendeten GSPNs (Generalized Stochastic Petri Nets)?
- Welchen Komponententyp repräsentieren Marken in Platz P1?
- Welchen Komponententyp repräsentieren Marken in Platz P2?
- Welchen Komponententyp repräsentieren Marken in P10, P11 und P12?
Das in Abb. 2 dargestellte GSPN befindet sich im Anfangszustand (P1, P2, P3, P4, P5, P6, P7, P8 ,P9, P10, P11, P12)=(4,2,0,0,0,0,0,0,0,1,1,1). Geben Sie Schritt für Schritt die Zustände an, die sich ergeben, wenn ausgehend vom Anfangszustand ein Prozessor über einen globalen Bus auf ein Speichermodul ihrer Wahl zugreift. Zum Schluss soll wieder der Anfangszustand erreicht werden.
Sie wollen eine Architektur mit 7 Prozessoren, 3 globalen Bussen und 4 Speichermodulen (7x3x4 MP-Architektur) modellieren. Erweitern sie dazu das in Abb. 2 dargestellte GSPN, indem sie es entsprechend markieren und eventuell in seiner Struktur erweitern.

Michael Syrjakow