Blatt3

3. Übungsblatt zur Vorlesung Rechnerstrukturen

Die Besprechung des Übungsblattes findet am Donnerstag, den 8. Juni 1995 um 14.00 Uhr im HMU statt. Die Musterlösung ist ausschließlich im WWW zu finden.

7. Aufgabe (Risc-Rechner)

Eine vereinfachte Risc-Maschine verfüge über acht globale Register R0-R7 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 und ein Register für den Zeiger auf das aktuelle Fenster CWP. Die einzelnen Befehle werden in einer fünfstufigen Befehls-Pipeline verarbeitet. (Befehl-Holen, Befehl-Dekodieren, Operand-Holen, Operation-Ausführen, und Operand-Speichern). Es seien die folgende Befehle vorhanden:

```
     f(x) = if x<=1 then x else f(x-1)+f(x-2)
```
Schreiben Sie für die gegebene Funktion f(x), die die Fibonacci-Zahlen berechnet, ein Programm für den gegebenen Risc-Prozessor, wobei das globale Register R0 mit dem Wert 0 und R1 mit dem Wert 1 vorbelegt sei. Der Parameter x soll vom aufrufenden Assemblerprogramm im Register R25 übergeben werden und das Ergebnis soll nach Abarbeitung der zu implementierenden Rechenvorschrift im Register R26 zu lesen sein. Das Register R24 diene zur Aufnahme der Rückkehradresse.
Testen Sie Ihr Programm für f(3) 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 nebeneinander anordnen und dieselben Register auf dieselbe Höhe ausrichten. Die Inhalte der verwendeten Register sollen in die Fenster eingetragen werden.
Für welche Argumentwerte reicht die Gesamtanzahl der Register aus? Was passiert bei größeren Argumentwerten? Welche Techniken könnten Sie sich vorstellen, um auch größere Rekursionstiefen zu ermöglichen?
Treten bei der Abarbeitung Ihres Programms Pipeline-Konflikte auf? Stellen Sie diese Konflikte graphisch dar.
Auf welche Weise könnte man die Konflikte aus der vorigen Teilaufgabe beheben? Führen Sie die entsprechenden Korrekturen aus.

8. Kontrollfragen (ohne Musterlösung)

Was sind die charakteristischen Eigenschaften einer RISC-Architektur?
Warum benötigen RISC-Rechner mehr Register als CISC-Rechner?
Können die von CISC-Rechnern bekannten Adressierungsarten auch mit den wenigen Adressierungsarten der RISC-Rechner realisiert werden?
Welche Pipelinekonfikte gibt es und wie können diese umgangen werden?
Worin besteht der Unterschied zwischen Superpipeline-Prozessoren und superskalaren Prozessoren?
Warum ist der Compilerbau für VLIW-Maschinen aufwendiger als für superskalare Prozessoren?

Zusatzaufgabe

In einer Load-/Store-Architektur sollen die Befehle in der fünfstufigen Befehlspipeline aus Aufgabe 7 ausgeführt werden. Dabei gelten die folgenden Modifikationen:

In der 3. Stufe wird der Operand in der zweiten Hälfte des Taktes gelesen.
In der 5. Stufe wird der Operand in der ersten Hälfte des Taktes gespeichert.
Bei allen Varianten von Sprüngen wird der neue Befehlszähler in der 4. Stufe gesetzt.
Mit dem Befehl LD a, Rx wird der Speicheroperand an der Adresse a in der ersten Takthälfte der 5. Stufe in das Register Rx geschrieben.
Das Ergebnis eines Vergleichs wird in ein Register geschrieben, welches bei einem bedingten Sprung angegeben wird.
Das Register R0 enthält die Konstante 0 und kann nicht überschrieben werden.

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:    LD    b,  R1        ; R1 := [b]
        MUL   R1, R1, R1    ; R1 := R1*R1
        LD    vier, R2      ; R2 := [vier]
        LD    a,  R3        ; R3 := [a]
        MUL   R2, R3, R2    ; R2 := R2*R3
        LD    c,  R3        ; R3 := [c]
        MUL   R2, R3, R2    ; R2 := R2*R3
        CMP   R1, R2, R3    ; R3 := Vergleichsergebnis von R1 mit R2
        BGE   R3, high      ; falls R1-R2 >= 0, dann springe nach high
low:    ADD   R0, R0, R1    ; R1 := 0 ( = 0+0 )
        JMP   join          ; springe nach join
high:   SUB   R1, R2, R1    ; R1 := R1-R2
join:   ST    R1, erg       ; [erg] := R1

Welcher Ausdruck soll (nach den Kommentaren) für erg berechnet werden?
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.
Optimieren Sie das Programm aus 2), indem Sie durch Verschiebung von Anweisungen NOP-Befehle ersetzen.
Kann das Programm aus 3) durch Registerumbenennung weiter optimiert werden? Nehmen Sie dabei an, daß eine ausreichende Zahl von Registern zur Verfügung steht.

Heidrun Dücker