Loesung5

Musterlösung zum 5. Übungsblatt

13. Aufgabe (Verbindungsnetzwerke)

Wieviele Zeilen und Spalten hat ein Benesnetzwerk der Ordnung d?

           d-1
#Zeilen = 2   ,     #Spalten = 2 d - 1

Zeigen Sie, daß das Benesnetzwerk universell ist, d.h. jede Permutation erzeugen kann. Ich führe einen Induktionsbeweis.
```
d = 1
```
stimmt (trivial)
```
d - 1 -> d 
```
Annahme: Ein Netzwerk der Ordnung d -1 kann alle Permutationen über 2^(d-1) erzeugen.
Möchte ich eine vorgegebene Permutation zu einem Netzwerk der Größe d erzeugen gehe ich folgendermaßen vor:
OBdA stelle ich den Kreuzschalter (Tauscher) links oben auf "parallel". Damit geht der Pfad des Eingangs 0 durch das obere Subnetzwerk. (Jeder Tauscher der äusseren Spalten hat eine Verbindung zum oberen und eine zum unteren Subnetzwerk) Ich lege damit die Stellung des Tauscher in der rechten Spalte fest, der zum entsprechenden Ausgang P(0) gehört. Als nächstes gehe ich vom zweiten Ausgang dieses rechten Tauschers aus, und suche den entsprechenden Eingang auf der linken Seite. Dieser Pfad führt durch das untere Subnetzwerk. Damit lege ich einen zweiten Tauscher in der linken Spalte fest. Nun nehme ich den anderen Eingang dieses Tauschers u.s.w.
Mit diesem Zick-Zack-Verfahren werden solange Tauscher in den äusseren Spalten festgelegt, bis man wieder beim linken oberen Tauscher ankommt.
Sind dann noch nicht alle Tauscher in der linken und rechten Spalte festgelegt, so wähle ich den noch freien Eingang mit dem kleinsten Index aus, stelle den zugehörigen Tauscher wieder auf parallel und setze das Verfahren fort.
Sind alle Tauscher in der linken und rechten Reihe festgelegt, so wird das Verfahren rekursiv auf die Subnetzwerke angewandt.
Auf dem Weg von links nach rechts wird jeweils das obere Netzwerk durchlaufen, auf dem Rückweg das untere.
Warum kann es nicht zu Verklemmungen kommen?
Auf der linken Seite ist immer nur ein Eingang an einem schon festgelegten Tauscher frei (im ersten Schritt ist dies der Eingang 1). Wird dieser irgendwann auf einem Rückweg festgelegt so steht der zugehörige linke Tauscher auf jeden Fall richtig, denn der Pfad dieses Eingangs führt durch das untere Subnetzwerk.
Auf der rechten Seite wird immer, nachdem ein Tauscher festgelegt wurde der andere Pfad festgelegt, der durch diesen Tauscher führt. Es gehören daher immer alle "offenen" Ausgänge auch zu noch nicht festgelegten Tauschern.
Anmerkung 1: Das Verfahren wird am Beispiel aus Teilaufgabe 3 deutlich.
Anmerkung 2: Ruhe bewahren! Ein Beweis dieser Art wird nicht in der Klausur gefordert.
Konstruieren für d = 3 eine Schalterstellung, die die Permutation (3,0,1,2,4,6,5,7) erzeugt.
Zuerst veranschaulicht man sich die Permutation graphisch:

Die äußeren Spalten werden im beschriebenen Verfahren konstruiert. Numerierung der Wege in der Reihenfolge, wie sie im Algorithmus erzeugt werden. Rote Wege sind von links nach rechts, also vom Eingang zum Ausgang erzeugt, grüne ungekehrt.

Wendet man das Verfahren auf die Unternetzwerke rekursiv an, so kommt man zu folgendem Ergebnis:

14. Aufgabe (Leistungsfähigkeit von Multiprozessorsystemen)

Die Effizienz gibt die relative Verbesserung der Verarbeitungsgeschwindigkeit an. Wenn man mit der 16-fachen Anzahl Prozessoren nur die 4-fache Geschwindigkeit erzielt, ist die Effizienz = 1/4.
```
       S(n)   4    1
E(n) = ---- = -- = -
        n     16   4
```

Nach Formel gilt:

       T(1)                T(1)    32
S(n) = ----   ==>  T(16) = ----- = -- = 8
       T(n)                S(16)   4

Der Parallelindex gibt die Anzahl der parallelen Operationen (16) an. Die Maschine muß 40 Operationen ausführen und benötigt dafür 8 Einheiten.
```
       P(n)    P(16)   40
I(n) = ----  = ----- = -- = 5
       T(n)    T(16)   8
```

Amdahls Gesetz besagt, daß ein bestimmter Prozentsatz a des Programms nur sequentiell bearbeitet weerden kann.

                T(1) (1-a)          n T(n) - T(1)   1
T(n) = T(1) a + ----------  ==> a = ------------- = -
                    n                (n-1) T(1)     5

Erhöht man die Anzahl der Prozessoren beliebig, so kann die Ausführungszeit T nicht kleiner werden als die Zeit, die für den sequentiell abzuarbeitenden Teil a benötigt wird.
```
T(oo) = T(1) a = 32/5 
```
Der maximale SpeedUp ist demzufolge 5.

15. Aufgabe (Adressierung in Multiprozessorsystemen)

Wieviele Knoten hat eine Pyramide mit e Ebenen?

Ich definiere die Spitze der Pyramide als Ebene 0, dann gilt: Jede Ebene i ist quadratisch und hat eine Kantenlänge von 2^i.

             e-1          e-1            e
             __     i 2   __   i    1 - 4      Summenformel
=> #Knoten = \    (2 )  = \   4   = ------     der geometrischen
             /_           /_        1 - 4      Reihe!
             i=0          i=0

Wieviele Nachbarn kann ein Knoten maximal haben?
Ein Knoten im Inneren der Pyramide hat 1 "Vater", 4 "Brüder" und 4 "Söhne", also 9 Nachbarn.
Geben sie ein Adressierungsschema für die Knoten an.
Ich definiere die Adressen als Tripel:
```
(Ebene i, Koordinate x, Koordinate y)
```
(i, x, y starten bei 0)

Geben sie die Adressen aller Nachbarknoten eines Knotens an, sowie die Bedingungen für die Existenz des Nachbarn.

Adressen:

Vater:  (i - 1, x DIV 2, y DIV 2)
Brüder: (i    , x + 1  , y      )
        (i    , x - 1  , y      )
        (i    , x      , y + 1  )
        (i    , x      , y - 1  )
Söhne:  (i + 1, 2 x    , 2 y    )
        (i + 1, 2 x + 1, 2 y    )
        (i + 1, 2 x    , 2 y + 1)
        (i + 1, 2 x + 1, 2 y + 1)

Existenzbedingung:

                         i               i
0 <= i < e und 0 <= x < 2  und 0 <= y < 2

Felix Holderied