1. 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.
2. Aufgabe (Pipelining)
Nehmen wir an, daß Maschinenbefehle in einer k-stufigen Pipeline ausgeführt werden. Die Verzögerung in einer Pipelinestufe betrage eine Zeiteinheit. Hängt ein Befehl vom n-ten vorhergehenden Befehl ab, so muß jener schon vollständig abgearbeitet sein, bevor der aktuelle Befehl bearbeitet werden kann. Der Befehl muß deswegen um max(0, k-n) Zeiteinheiten verzögert werden. Die Wahrscheinlichkeit pn für eine Abhängigkeit vom n-ten vorhergehenden Befehl sei definiert als:
/ 1
| _ für 1 <= n <= L
pn := < L
|
\ 0 für n > L
Dabei sei L>k. Somit bezeichnet L den größten Abstand zweier
abhängiger Instruktionen.
Ein vorgegebenes Programm habe nun m Instruktionen auszuführen.
- Wie viele Zeiteinheiten werden durchschnittlich benötigt?
- Wie viele Befehle pro Zeiteinheit werden bei der Ausführung von m Befehlen erwartet? Betrachten Sie den Grenzwert bei Variation der Programmgröße m .
- In der Vorlesung wurde die Kenngröße Sk für die Leistungssteigerung (Speedup) eines Pipeline-Prozessors eingeführt (siehe Skript Seite 160). Bei der Berechnung des Speedup's für einen Pipeline-Prozessor wurden allerdings keine Verzögerungen berücksichtigt. Wie hängt die im vorigen Aufgabenteil berechnete Größe mit Sk zusammen?
3. Aufgabe (Pipelining)
In einer Load-/Store-Architektur sollen die Befehle in der fünfstufigen Befehlspipeline aus Aufgabe 1 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.
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.
4. 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.- In welche fünf Phasen kann man die Befehlsausführung im allgemeinen zerlegen?
- Welche Konflikte können bei einem Fließband auftreten?
- 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?
- Was versteht man unter der Effizienz eines Pipeline-Prozessors ?
- Unter welchen Bedingungen ist ein Pipeline-Prozessor von der Bearbeitungszeit her günstiger als ein serieller Prozessor ?
Christian Blumenröhr, Sprechstunde: Montags 14 - 15 Uhr