Übungsblatt 2  

Institut für Rechnerentwurf und Fehlertoleranz

Prof. Dr. Th. Ungerer

Sebastian Wilhelmi

Sommersemester 1998

Die Besprechung dieses Übungsblattes findet am Donnerstag, den 14. Mai 1997 um 14.00 Uhr im Tulla-Hörsaal statt. Die Musterlösung ist nach der Übung im WWW zu finden.

2. Übungsblatt zur Vorlesung Rechnerstrukturen

Für die nachfolgenden beiden Aufgaben wird im folgenden eine vereinfachte RISC-Maschine definiert. Sie verfüge über acht globale Register R0-R7 (dabei ist das Register R0 mit 0 und das Register R1 mit 1 belegt) und über achtzig weitere Register als Umlaufspeicher für die überlappenden Registerfenster. Ein Fenster umfasse acht "in"-Register R8-R15, acht lokale Register R16-R23 und acht "out"-Register R24-R31. Die Maschine besitze außerdem ein Statusregister SR , den Befehlszähler PC und ein Register für den Zeiger auf das aktuelle Registerfenster CWP. Die einzelnen Befehle werden in einer fünfstufigen Befehls-Pipeline verarbeitet. (Befehl-Holen, Befehl-Dekodieren, Operand-Holen, Operation-Ausführen, und Operand-Speichern). Dabei wird in der 2. Hälfte des Taktes von Stufe 5 gespeichert und in der 1. Hälfte des Taktes von Stufe 3 geladen. Der Befehlszähler wird bei allen Sprungbefehlen in der 2. Hälfte des Taktes in Stufe 4 geändert. Der Zeiger auf des aktuelle Registerfenster wird ebenfalls in der 4. Stufe geändert (bei den Unterprogrammbefehlen CALL und RET). In den folgenden Tabellen sind die Befehle des Prozessors angegeben. Die Semantik wird durch Pseudo-C-Code dargestellt. Dabei bezeichnet Ri ein Register, Addr eine Adresse, Val eine Konstante und Cond eine Bedingung.

Ladebefehle
LDC   Val, Ri Ri = Val
LOAD  Ri, Rj Rj = *Ri
LOAD  Addr, Ri Ri = *Addr
STORE Ri, Rj *Rj = Ri
STORE Ri, Addr *Addr = Ri

Arithmetische Befehle
ADD   Ri, Rj, Rk Rk = Ri + Rj
SUB   Ri, Rj, Rk Rk = Ri - Rj
MUL   Ri, Rj, Rk Rk = Ri * Rj
OR    Ri, Rj, Rk Rk = Ri | Rj
AND   Ri, Rj, Rk Rk = Ri & Rj
NOT   Ri, Rj Rj = ~ Ri

Vergleichsbefehl
CMP   Ri, Rj SR = Ri - Rj
Sprungbefehle
JMP   Cond, Addr if( Cond ) PC = Addr
CALL  Ri, Addr Ri = PC; PC = Addr; CWP--
RET   Ri PC = Ri; CWP++
Bedingungen für JMP
     Ttrue
     Ffalse
     LTSR < 0
     LESR <= 0
     GTSR > 0
     GESR >= 0
     ZSR == 0

1. Aufgabe (RISC-Rechner)

  1. Eine mögliche Definition für die (ganzzahlige positive) Binomialfunkion n über k lautet:
     / 1wenn k == 0
    bin( n, k ) :={0wenn n < k
     \bin( n - 1, k ) + bin( n - 1, k - 1 )sonst
    Schreiben Sie für die gegebene Funktion bin( n, k ) ein Programm für den gegebenen RISC-Prozessor. Die Parameter n und k sollen vom aufrufenden Assemblerprogramm in den Registern R25 bzw. R26 übergeben werden und das Ergebnis soll nach Abarbeitung des Algorithmus im Register R27 sein. Das Register R24 diene zur Aufnahme der Rückkehradresse bei Unterprogrammaufrufen.
  2. Testen Sie Ihr Programm für bin( 2, 1 ) auf dem Papier und zeichnen Sie sich die Fensterwechsel für diesen Testlauf auf. Trennen Sie die einzelnen Registertypen voneinander und machen Sie sich die Überlappung der einzelnen Registerfenster klar, indem Sie die Fenster in zeitlicher Reihenfolge untereinander anordnen und dieselben Register auf dieselbe Spalte ausrichten. Die Inhalte der verwendeten Register sollen in die Fenster eingetragen werden.
  3. Für wieviele Rekursionen reicht die Gesamtanzahl der Register aus? Was passiert bei zu großen Argumenten? Welche Techniken könnten Sie sich vorstellen, um auch größere Rekursionstiefen zu ermöglichen?
  4. Treten bei der Abarbeitung Ihres Programms Pipeline-Konflikte auf? Stellen Sie diese Konflikte dar.
  5. Auf welche Weise könnte man die Konflikte aus der vorigen Teilaufgabe beheben? Führen Sie die entsprechenden Korrekturen aus.

2. Aufgabe (Pipelining)

Auf dem oben angegeben Prozessor soll ein Programm ausgeführt werden. Dabei gelten die folgenden Modifikationen: Die folgende Codesequenz enthält noch Pipelinekonflikte, welche die in den Kommentaren angedeutete Arbeitsweise der einzelnen Befehle beeinflussen. Die Adressen a, b, c, vier und erg bezeichnen Variablen im Speicher, welche bereits geeignet initialisiert sind. 
max:    LOAD  b,  R2        ; R2 = *b
        MUL   R2, R2, R2    ; R2 *= R2
        LOAD  vier, R3      ; R3 = *vier
        LOAD  a,  R4        ; R4 = *a
        MUL   R3, R4, R3    ; R3 *= R4
        LOAD  c,  R4        ; R4 = *c
        MUL   R3, R4, R3    ; R3 *= R4
        CMP   R2, R3        ; ST = R2 - R3
        JMP   GE, high      ; if ( ST >= 0 ) goto high
low:    ADD   R0, R0, R2    ; R2 = 0
        JMP   T, join       ; goto join
high:   SUB   R2, R3, R2    ; R2 -= R3
join:   STORE R2, erg       ; *erg = R2
  1. Welcher Ausdruck soll (nach den Kommentaren) für erg berechnet werden?
  2. Finden Sie eine Assembler-Anweisung, mit der ein NOP-Befehl realisiert werden kann, und lösen Sie alle Pipelinekonflikte durch das Einfügen einer minimalen Anzahl von NOP-Befehlen auf.
  3. Optimieren Sie dieses mit NOPs ergänzte Programm weiter, indem Sie durch Verschiebung von Anweisungen NOP-Befehle einsparen.

3. Kontrollfragen

Das folgende sind Fragen zu Stichworten des bisher behandelten Stoffs. Sie sollen dazu dienen, das eigene Wissen zu überprüfen und dazu anregen, die entsprechenden Kapitel im Skript noch einmal aufzuschlagen.
  1. In welche fünf Phasen kann man die Befehlsausführung im allgemeinen zerlegen?
  2. Was sind die charakteristischen Eigenschaften einer RISC-Architektur?
  3. Warum benötigen RISC-Rechner mehr Register als CISC-Rechner?
  4. Können die von CISC-Rechnern bekannten Adressierungsarten auch mit den wenigen Adressierungsarten der RISC-Rechner realisiert werden?
  5. Welche Pipelinekonfikte gibt es und wie können diese umgangen werden?
  6. Worin besteht der Unterschied zwischen Superpipeline-Prozessoren und superskalaren Prozessoren?
  7. Warum ist der Compilerbau für VLIW-Maschinen aufwendiger als für superskalare Prozessoren?
  8. Was versteht man unter der Effizienz eines Pipeline-Prozessors ?
  9. Unter welchen Bedingungen ist ein Pipeline-Prozessor von der Bearbeitungszeit her günstiger als ein serieller Prozessor ?
Sebastian Wilhelmi <wilhelmi@ira.uka.de>
Informatikgebäude am Schloß, Raum 263
Telefon: 608-4353
Sprechstunde: Dienstags 9.00-11.00 Uhr