Lösungen zum Übungsblatt 2

Institut für Rechnerentwurf und Fehlertoleranz

Lösungen zum Übungsblatt 2

1. Aufgabe (RISC-Rechner)

Die Register sind folgendermaßen belegt:

`R0`	0
`R1`	1
`R8`	Rücksprungadresse vom Aufrufer
`R9`	`n` vom Aufrufer
`R10`	`k` vom Aufrufer
`R11`	Ergebnis für Aufrufer (`b`)
`R24`	Rücksprungadresse für Unteroutine
`R25`	`n` für Unteroutine (`n_u`)
`R26`	`k` für Unteroutine (`k_u`)
`R27`	Ergebnis von Unterroutine (`b_u`)

Das entsprechende Programm sieht dann so aus:

bin:    CMP   R10, R0        ; ST = k - 0
        JMP   Z,   ret1	     ; if ( ST == 0 ) goto ret1
        CMP   R9,  R10       ; ST = n - k
        JMP   LT,  ret0      ; if ( ST < 0 ) goto ret0
        SUB   R9,  R1,  R25  ; n_u = n - 1
        ADD   R10, R0,  R26  ; k_u = k
        CALL  R24, bin	     ; b_u = bin( n_u, k_u )
	ADD   R27, R0,  R11  ; b = b_u 
	SUB   R26, R1,  R26  ; k_u--
	CALL  R24, bin	     ; b_u = bin( n_u, k_u )
	ADD   R27, R11, R11  ; b += b_u
	RET   R8             ; return
ret0:	ADD   R0,  R0,  R11  ; b = 0
        RET   R8	     ; return
ret1:	ADD   R1,  R0,  R11  ; b = 1
        RET   R8             ; return

Dieses Programm geht natürlich davon aus, daß der Prozessor hardwaremäßig in der Lage ist, Daten- und Kontrollkonflikte aufzulösen.

Im folgenden ist der Ablauf des Aufrufes bin( 2, 1 ) auf Registerebene dargestellt. In den Spalten IO sind dabei die Input bzw. Output-Register R9/R25 (Parameter n), R10/R26 (Parameter k) und R11/R27 (Ergebnis b) sowie in L die lokalen Register (die im obigen Program nicht benutzt werden) dargestellt. Unbekante Werte sind durch ein ? dargestellt. Durch das Program neu geschriebene Werte sind fett gedruckt. Die Register R8/R24, welche die Rücksprungadressen enthalten, werden nicht extra angegeben.

IO L IO L IO L IO L IO
? ? 2 1 ?

2 1 ? ? 1 1 ?

1 1 ? ? 0 1 ?

0 1 0 ? ?

1 1 0 ? 0 0 0

0 0 1 ? ?

1 1 1 ? 0 0 1

2 1 1 ? 1 0 1

1 0 1 ? ?

2 1 2 ? 1 0 1

? ? 2 1 2

Das Ergebnis lautet also 2.
Jedes neue Registerfenster benötigt einen zusätzlichen Satz lokale Register und einen zusätzlichen Satz Output-Register. Die Input-Register sind die Output-Register des aufrufenden Programs. Auf der angegeben Maschine sind 80 Register vorhanden und jedes neue Fenster braucht 8 + 8 = 16 neue Register. Es gibt also 5 Registerfenster. Das aufrufende Program belegt 1 Fenster. Außerdem ist ein Registerfenster als "invalid" gekennzeichnet, da es sich mit dem Fenster des aufrufenden Programmes überschneidet. Es sind also maximal 2 Rekursionen (den Erstaufruf nicht mitgezählt) möglich. bin( 2, 1 ) wie im obigen Beispiel könnte also gerade noch berechnet werden. bin( 3, 1 ) kann nicht in den vorhandenen Registern berechnet werden. Dafür müßten dann Registerfenster zwischengespeichert werden. Entweder von Betriebssystem, das über einen Trap aufgerufen wird, wenn die Register voll sind, oder direkt durch das Programm mit Hilfe von Load/Store-Befehlen.
In folgender Darstellung wird der zeitliche Verlauf des Aufenthalts der einzelnen Befehle in den verschiedenen Pipelinestufen (1,2,3,4 und 5 ) dargestellt. Dabei wurden alle Konflikte durch zwischenzeitliches Anhalten der Pipeline aufgehoben. Folgende Konflikte treten dabei auf.
1. Ein Befehl benötigt die Ergebnisse des vorhergehenden Befehls. Dieser schreibt seine Ergebnisse im 5. Takt. Der aktuelle Befehl liest seine Daten im 3. Takt. Der 3. Takt des aktuellen Befehls darf also erst nach dem 5. Takt des vorhergenden Befehls stattfinden (siehe Zeilen (01)-(02), (03)-(04)).
2. Ein Befehl nach einem Sprungbefehl muß so lange warten, bis der Befehlszähler neu geschrieben ist, damit er nicht noch eingelesen und bearbeitet wird. Der Befehlszähler wird bei einem Sprung in der 4. Stufe neue geschrieben. Die 1. Stufe des aktuellen Befehls muß also nach der 4. Stufe des vorhergehenden Sprungbefehles kommen (siehe Zeilen (02)-(03), (04)-(05), (07)-(08), (10)-(11), (12)-(13), (14)-(15), (16)-(17)).
3. Ein Befehl vor einem Unterprogrambefehl (also CALL und RET), der noch in Register des aktuellen Registerfenster schreibt, muß seine 5. Stufe noch vor der 4. Stufe des Unterprogrammbefehls (CWP wird geändert) durchführen (siehe Zeilen (06)-(07), (09)-(10), (11)-(12), (13)-(14), (15)-(16)).
```
(01) CMP   R10, R0        12345
(02) JMP   Z,   ret1         12345
(03) CMP   R9,  R10              12345
(04) JMP   LT,  ret0                12345
(05) SUB   R9,  R1,  R25                12345
(06) ADD   R10, R0,  R26                 12345
(07) CALL  R24, bin                        12345
(08) ADD   R27, R0,  R11                       12345
(09) SUB   R26, R1,  R26                        12345
(10) CALL  R24, bin                               12345
(11) ADD   R27, R11, R11                              12345
(12) RET   R8                                           12345
(13) ADD   R0,  R0,  R11                                    12345
(14) RET   R8                                                 12345
(15) ADD   R1,  R0,  R11                                          12345
(16) RET   R8                                                       12345
(17) ??                                                                 12345
```

Um die Konflikte zu lösen, müssen jetzt NOP-Befehle derart eingefügt werden, daß die oben angegebenen Stopps der Pipeline nicht mehr nötig sind.

bin:    CMP   R10, R0 
        NOP
	NOP
        JMP   Z,   ret1	
        NOP
	NOP
	NOP
        CMP   R9,  R10
        NOP
	NOP
        JMP   LT,  ret0  
        NOP
	NOP
	NOP
        SUB   R9,  R1,  R25
        ADD   R10, R0,  R26 
	NOP
        CALL  R24, bin	
        NOP
	NOP
	NOP
	ADD   R27, R0,  R11  
	SUB   R26, R1,  R26
	NOP
	CALL  R24, bin	
        NOP
	NOP
	NOP
	ADD   R27, R11, R11 
	NOP
	RET   R8 
        NOP
	NOP
	NOP
ret0:	ADD   R0,  R0,  R11
	NOP
        RET   R8
        NOP
	NOP
	NOP
ret1:	ADD   R1,  R0,  R11 
	NOP
        RET   R8 
        NOP
	NOP
	NOP

2. Aufgabe (Pipelining)

erg = max( b * b - 4 * a * c, 0 )

Eine Anweisung, die ein NOP impmlementiert, ist ADD R0, R0, R0. Die Vorgehensweise zur Bestimmung der Pipelinekonflikte ist dieselbe wie im obigen Beispiel. Da aber in diesem Beispiel Daten in der 2. Hälfte des 3. Taktes gelesen und schon in der 1. Hälfte des 5. Taktes geschrieben werden, kann die nötige Verzögerung bei Datenkonflikten auf 1 reduziert werden (siehe Zeilen (00)-(01), (03)-(04), (05)-(06), (06)-(07), (07)-(08), (11)-(12)).

(00) LOAD  b,  R2      12345
(01) MUL   R2, R2, R2    12345
(02) LOAD  vier, R3       12345
(03) LOAD  a,  R4          12345
(04) MUL   R3, R4, R3        12345
(05) LOAD  c,  R4             12345
(06) MUL   R3, R4, R3           12345
(07) CMP   R2, R3                 12345
(08) JMP   GE, high                 12345
(09) ADD   R0, R0, R2                   12345
(10) JMP   T, join                       12345
(11) SUB   R2, R3, R2                        12345
(12) STORE R2, erg                             12345

Dementsprechend wird das Codefragment dann mit NOPs ergänzt:

max:    LOAD  b,  R2
        NOP
        MUL   R2, R2, R2 
        LOAD  vier, R3 
        LOAD  a,  R4
        NOP 
        MUL   R3, R4, R3 
        LOAD  c,  R4
        NOP  
        MUL   R3, R4, R3 
        NOP 
        CMP   R2, R3
        NOP   
        JMP   GE, high
        NOP
        NOP
        NOP  
low:    ADD   R0, R0, R2  
        JMP   T, join   
        NOP
        NOP
        NOP
high:   SUB   R2, R3, R2 
        NOP
join:   STORE R2, erg

max:    LOAD  vier, R3  
        LOAD  a,  R4
        LOAD  b,  R2
        MUL   R3, R4, R3 
        LOAD  c,  R4
        MUL   R2, R2, R2 
        MUL   R3, R4, R3 
        NOP 
        CMP   R2, R3
        NOP   
        JMP   GE, join
        SUB   R2, R3, R2
        NOP
        NOP  
low:    ADD   R0, R0, R2  
        NOP
join:   STORE R2, erg

3. Kontrollfragen

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

Sebastian Wilhelmi <wilhelmi@ira.uka.de>
Informatikgebäude am Schloß, Raum 263
Telefon: 608-4353
Sprechstunde: Dienstags 9.00-11.00 Uhr

Institut für Rechnerentwurf und Fehlertoleranz

Prof. Dr. Th. Ungerer

Sebastian Wilhelmi

Sommersemester 1998

Lösungen zum Übungsblatt 2

1. Aufgabe (RISC-Rechner)

2. Aufgabe (Pipelining)

3. Kontrollfragen

IO	L	IO	L	IO	L	IO	L	IO
?	?	2 1 ?
		2 1 ?	?	1 1 ?
				1 1 ?	?	0 1 ?
						0 1 0	?	?
				1 1 0	?	0 0 0
						0 0 1	?	?
				1 1 1	?	0 0 1
		2 1 1	?	1 0 1
				1 0 1	?	?
		2 1 2	?	1 0 1
?	?	2 1 2