5. Übungsblatt zur Vorlesung Rechnerstrukturen

Die Besprechung des Übungsblattes findet am Dienstag, den 11. Juli 1995 um 14.00 Uhr im HMU statt. Die Musterlösung ist ausschließlich im WWW zu finden.

13. Aufgabe (Verbindungsnetzwerke)

Um mehrere Prozessoren eines Multiprozessorsystems miteinander zu vernetzen kann man Verbindungsnetzwerke aus Zweierschaltern verwenden (siehe Skript S.162). 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 für d = 3 eine Schalterstellung, die die Permutation (3,0,1,2,4,6,5,7) erzeugt.

14. 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.
  1. Geben Sie die Effizienz E(16) an.
  2. Berechnen Sie die Ausführungszeit des Multiprozessorsystems T(16).
  3. Geben Sie den Parallelindex I(16) an.
  4. Welcher Bruchteil der Programme ist nach Amdahls Gesetz nur sequentiell ausführbar?
  5. Durch welchen Wert wird die Leistungssteigerung begrenzt, wenn man die Anzahl der Prozessoren beliebig erhöht?

15. Aufgabe (Adressierung in Multiprozessorsystemen)

Ein Multiprozessorsystem sei mit einer Pyramidenstruktur aus e Ebenen verbunden.
  1. Wieviele Knoten hat eine Pyramide mit e Ebenen?
  2. Wieviele Nachbarn kann ein Knoten maximal haben?
  3. Geben sie ein Adressierungsschema für die Knoten an.
  4. Geben sie die Adressen aller Nachbarknoten eines Knotens an, sowie die Bedingungen für die Existenz des Nachbarn.

Felix Holderied