Institut für Rechnerentwurf und Fehlertoleranz

Prof. Dr. Th. Ungerer

Christian Blumenröhr

15. Mai 1997

Loesung2

Musterlösung zum 2. Übungsblatt

1. Aufgabe (RISC-Rechner)

a) f(x) = if x <= 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,then
else   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
then   ADD    R0,R9,R10     ;f(x) = x
       RET    R8

b) (3KB .png)

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

Load/Store-Befehle
Traphandling

e) Einfügen von NOP-Befehlen:

    fib  CMP   R9,R1
         NOP
         NOP
         JMP   LE,then
         NOP
         NOP
         NOP
    else 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
    then 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,then
         ADD   R0,R0,R26
         NOP
         NOP
    else CALL  R24,fib    
         NOP
         NOP
         NOP
    @1   CALL  R24,fib    
         ADD   R0,R26,R16
         SUB   R25,R1,R25
         NOP
    then ADD   R16,R26,R10 
         NOP
         RET   R8
         NOP
         NOP
         NOP

Dabei basiert die Umordnung der Befehle auf folgendem Prinzip:
Ergebnisrückgabe bisher:

else:
then:

besser:

then:

oder noch effizienter:

    fib  CMP   R9,R1
         ADD   R0,R9,R16    
         SUB   R9,R1,R25
         JMP   LE,then
         ADD   R0,R0,R26
         NOP
         NOP
    else CALL  R24,fib    
         NOP
         NOP
         NOP
    @1   CALL  R24,fib    
         ADD   R0,R26,R16
         SUB   R25,R1,R25
         NOP
    then RET   R8
         ADD   R16,R26,R26 
         NOP
         NOP

Bei "then" wird zunächst der Sprung ausgeführt. Die nächsten
3 Befehle werden dann noch mit in die Pipeline genommen, sodaß die Addition
auch nach dem RET-Befehl auftreten kann. Da aber beim RET-Befehl das CWP geändert
wird, darf das Ergebnis nicht in R10 (aktuelles Registerfenster) geschrieben werden,
sondern muss in das entsprechende Register des aufrufenden Programms - R26 - 
geschrieben werden.


2. Aufgabe (Pipelining)


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


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



        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    vier, R2
     LD    a, R3           
     LD    b, R1
     MUL   R2, R3, R2        
     LD    c,  R3
     MUL   R1, R1, R1        
     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





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

   
Christian Blumenröhr, Sprechstunde: Montags 14 - 15 Uhr