Musterlösung zum 4. Übungsblatt

9. Aufgabe

1. 
   

2. 4 + (n - 1) = n + 3 Taktzyklen

3. 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. 4 n 10 ns = n 40 ns

10. Aufgabe

1. 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
   

2. 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 
   

3. 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+n+Pipelinelänge-1 Takte. Der Trade-Off-Punkt ist die Lösung der linearen Gleichung

   3n = 5 + 8 (n-1),

   also 6.

11. Aufgabe

1. Für jeden Befehl wird mindestens ein Takt benötigt. Verwendet man ein einfaches Modell, dann gilt: Hängt ein Befehl vom i-ten Vorgänger ab, so muß dieser Befehl um (k-i) Takte verzögert werden, bis der Vorgänger vollständig abgearbeitet ist. Damit ergibt sich T(m) als Erwartungswert der Verzögerungen für m Befehle und den (k-1) Takten zum Starten der Pipeline:

            /     k-1          \
            |     __           |
   T(M) = m | 1 + \   P  (k-i) | + k - 1
            |     /_   i       |
            \     i=1          /
   
             /     k (k-1)  \
        = m  | 1 + -------  | + k - 1 
             \       2 L    /
   

2.  m             1
   ---- = -------------------
   T(m)        k (k-1)   k-1
           1 + ------- + ---
                 2 L      m
                 
          m           1
    lim  ---- = -------------
   m->oo T(m)        k (k-1)
                 1 + -------
                       2 L
   

3.         m      Vorlesung                  k           Teil 2        m
   S  = k ----   -----------> k   >    -------------   -----------> k ----
    k     T(m)     m -> oo                  k (k-1)      m -> oo      T(m)
                                        1 + -------
                                              2 L