2. Übungsblatt zur Vorlesung Rechnerstrukturen

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

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:

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.
  1. Wie viele Zeiteinheiten werden durchschnittlich benötigt?
  2. Wie viele Befehle pro Zeiteinheit werden bei der Ausführung von m Befehlen erwartet? Betrachten Sie den Grenzwert bei Variation der Programmgröße m .
  3. In der Vorlesung wurde die Kenngröße Sk für die Leistungssteigerung (Speedup) eines Pipeline-Prozessors eingeführt. 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: 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
  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 das Programm aus 2), indem Sie durch Verschiebung von Anweisungen NOP-Befehle ersetzen.
  4. Kann das Programm aus 3) durch Registerumbenennung weiter optimiert werden? Nehmen Sie dabei an, daß eine ausreichende Zahl von Registern zur Verfügung steht.

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.
Michael Berthold