Loesung4

Musterlösung zum 4. Übungsblatt

1. Aufgabe

4 + (n - 1) = n + 3 Taktzyklen
Die Pipeline besteht aus einem Addierwerk und vier Verzögerungsgliedern, welche jeweils mit dem Wert 0 initialisiert werden. Zum Starten der Berechnung werden nur die vier Startwerte (1 1 1 1) eingeleitet. Anschließend werden die errechneten Ergebnisse auf den Eingang zurückgekoppelt. Es kann nur alle vier Takte eine neue Fibonacci-Zahl erzeugt werden. Also bringt die Pipeline hier keine Vorteile.
4 n 10 ns = n 40 ns

2. Aufgabe

Im Idealfall wird von der Vektorpipeline in jedem Takt ein Ergebnis erzeugt => D8 = f = 90 MFLOPS.
Dieser Idealfall wird umso besser angenähert, je länger die Vektoren sind, da dann die Startzeit und die Füllzeit der Pipeline vernachlässigt werden kann:
```
               n
D (n) = --------------- 90 MFLOPS ---------> 90 MFLOPS
 8      (5 + 8 + (n-1))            n -> oo
```

Ohne Berücksichtigung der Startzeit läßt sich n1/2 mit dem folgenden Ansatz berechnen:

      n
       1/2                 1
-------------- 90 MFLOPS = - 90 MFLOPS  =>  n    = 8 - 1 = 7
 8 + (n   - 1)             2                 1/2
       1/2

Die Anzahl der Takte zur Berechnung von n skalaren Operationen beträgt 3n. Berechnet man die n Operationen in der gegebenen Pipeline, dann benötigt man Startzeit+Pipelinelänge+Verarbeitungsaufträge-1 Takte. Der Trade-Off-Punkt ist die Lösung der linearen Gleichung
```
3n = 5 + 8+(n-1),
```
also 6.

3. 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) pro Zeiteinheit an. Die Maschine muß 40 Operationen ausführen und benötigt dafür 8 Zeiteinheiten.
```
       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 werden 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.

4. 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 umfasst 2^i Knoten.

             e            e              e+1
             __     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

5. Aufgabe (Modellierung von Multiprozessorsystemen)

- Zur Modellierung von Zeit stellen GSPNs neben zeitlosen Transitionen (schwarze Balken) auch zeitbehaftete Transitionen (weisse Balken) zur Verfügung. Während die zeitlosen Transitionen schalten sobald sie aktiviert sind, erfahren die Marken an den zeitbehafteten Transitionen eine exponentiell verteilte Verzögerung (daher die Bezeichnung stochastische Petrinetze). Damit lassen sich mit GSPNs sowohl parallele Abläufe als auch deren Zeitverhalten nachbilden.
- Konfliktsituationen, die dann auftreten, wenn mehrere Transitionen gleichzeitig aktiviert sind, werden dadurch aufgelöst, dass mit einer bestimmten Wahrscheinlichkeit genau eine der schaltbereiten Transitionen zur Durchführung des Schaltvorgangs ausgewählt wird. Im GSPN aus Abb. 2 tritt eine Konfliktsituation dann auf, wenn sich eine Marke in Platz P3 befindet. Dann schaltet mit einer Wahrscheinlichkeit von jeweils 1/3 eine der drei aktivierten Transitionen T2, T3 oder T4.
- Marken in Platz P1 repräsentieren Prozessoren, die in ihrem lokalen Speicherbereich arbeiten (Prozessoren im aktiven Zustand).
- Marken in Platz P2 repräsentieren frei zur Verfügung stehende globale Busse.
- Marken in P10, P11 und P12 repräsentieren frei zur Verfügung stehende globale Speichermodule.
- Zustand 1: (P1, P2, P3, P4, P5, P6, P7, P8 ,P9, P10, P11, P12)= (4,2,0,0,0,0,0,0,0,1,1,1)
- Zustand 2: (P1, P2, P3, P4, P5, P6, P7, P8 ,P9, P10, P11, P12)= (3,2,1,0,0,0,0,0,0,1,1,1)
- Zustand 3: (P1, P2, P3, P4, P5, P6, P7, P8 ,P9, P10, P11, P12)= (3,2,0,1,0,0,0,0,0,1,1,1)
- Zustand 4: (P1, P2, P3, P4, P5, P6, P7, P8 ,P9, P10, P11, P12)= (3,1,0,0,0,0,1,0,0,0,1,1)
- Zustand 1: (P1, P2, P3, P4, P5, P6, P7, P8 ,P9, P10, P11, P12)= (4,2,0,0,0,0,0,0,0,1,1,1)
GSPN-Modell einer 7x3x4 Multiprozessor-Architektur

Michael Syrjakow