Musterlösung zum 2. Übungsblatt

1. Aufgabe (RISC-Rechner)

a) f(x) = if <= 1 then x else f(x-1)+f(x-2)

Registerfenster:

Vorbelegungen: 

    R0 = 0 
    R1 = 1
    R24  <-   Rückkehradresse
    R25  <-   x
    R26  <-   erg

fib    CMP    R9,R1
       JMP    LE,else
then   SUB    R9,R1,R25
       CALL   R24,fib       ;f(x-1)
@1     ADD    R0,R26,R16
       SUB    R25,R1,R25
       CALL   R24,fib       ;f(x-2)
@2     ADD    R16,R26,R10   ;f(x) = f(x-1) + f(x-2)
       RET    R8
else   ADD    R0,R9,R10     ;f(x) = x
       RET    R8
b) (3KB .png)

c) 

Registeranzahl ohne glob. Register    80
---------------------------------- = ----- =  5 Registerfenster
   Anz.'in'-Reg. + Anz.'loc'-Reg     8 + 8
Zieht man ein Fenster für das aufrufende Programm ab, so bleiben 4 Fenster übrig. Außerdem wird ein Registerfenster als 'invalid' gekennzeichnet, da es sich mit dem aufrufenden Programm überschneidet -> es läßt sich maximal fib(3) berechnen. Für größere Rekursionstiefen müssen Fenster zwischengespeichert werden, z.B. durch

d)

e) Einfügen von NOP-Befehlen: 
    fib  CMP   R9,R1
         NOP
         NOP
         JMP   LE,else
         NOP
         NOP
         NOP
    then SUB  R9,R1,R25
         NOP
         CALL R24,fib
         NOP
         NOP
         NOP
    @1   ADD  R0,R26,R16
         SUB  R25,R1,R25
         NOP
         CALL R24,fib
         NOP
         NOP
         NOP
    @2   ADD  R16,R26,R10
         NOP
         RET  R8
         NOP
         NOP
         NOP
    else ADD  R0,R9,R10
         NOP
         RET  R8
         NOP
         NOP
         NOP
zusätzlich Umordnen der Befehle: 
    fib  CMP   R9,R1
         ADD   R0,R9,R16    
         SUB   R9,R1,R25
         JMP   LE,else
         ADD   R0,R0,R26
         NOP
         NOP
    then CALL  R24,fib    
         NOP
         NOP
         NOP
    @1   CALL  R24,fib    
         ADD   R0,R26,R16
         SUB   R25,R1,R25
         NOP
    else RET   R8
         ADD   R16,R26,R10    
         NOP
         NOP
Dabei basiert die Umordnung der Befehle auf folgendem Prinzip:

2. Aufgabe (Pipelining)

  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-2) (k-1)  \
     = m  | 1 + -----------  | + k - 1 =: m(1+f) + k-1 
          \         2 L      /

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


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

3. Aufgabe (Pipelining)

1) 
erg := max{b*b - 4*a*c,0}
2) 
NOP := ADD R0, R0, R0
max: LD    b,  R1
     NOP            
     MUL   R1, R1, R1        
     LD    vier, R2            
     LD    a,  R3
     NOP
     MUL   R2, R3, R2        
     LD    c,  R3
     NOP
     MUL   R2, R3, R2
     NOP
     CMP   R1, R2, R3
     NOP
     BGE   R3, high
     NOP
     NOP
     NOP
low: ADD   R0, R0, R1        
     JMP   join    
     NOP
     NOP
     NOP
high:SUB   R1, R2, R1        
     NOP
join:ST    R1, erg
3)
max: LD    b,  R1
     LD    vier, R2            
     LD    a,  R3
     MUL   R1, R1, R1        
     MUL   R2, R3, R2        
     LD    c,  R3
     NOP
     MUL   R2, R3, R2
     NOP
     CMP   R1, R2, R3
     NOP
     BGE   R3, join
high:SUB   R1, R2, R1        
     NOP
     NOP
low: ADD   R0, R0, R1        
     NOP
join:ST    R1, erg
     NOP
4) 
max: LD    vier,  R2            
     LD    a,  R3
     LD    b, R1        
     MUL   R2, R3, R5    ; R2 -> R5        
     LD    c,  R6        ; R3 -> R6    
     MUL   R1, R1, R4    ; R1 -> R4
     MUL   R5, R6, R7    ; R2 -> R7
     NOP
     CMP   R4, R7, R8    ; R3 -> R8
     NOP
     BGE   R3, join
high:SUB   R4, R7, R9    ; R1 -> R9        
     NOP
     NOP
low: ADD   R0, R0, R9        
     NOP
join:ST    R9, erg
     NOP

4. Kontrollfragen

Die Lösung der Kontrollfragen sollte aus dem Skript und weiterführender Literatur erfolgen.
Michael Berthold