# Rechnerarchitektur: Übung 5

## Aufgabe 1

a)
- ALU: Die Arithmetic Logic Unit ist eine Einheit, die arithmetische und logische Operationen ausführt.
- Control Unit: Verknüpft zwischen den Komponenten, steuert die Abfolge der Befehle und sagt der ALU, welche Operation ausgeführt werden soll.
- Memory: Hier werden Daten und Befehle gespeichert.
- BUS: Übertragung von Daten/Adressen/Steuerbefehlen.
- I/O Unit: Datenein- und ausgabe von Geräteschnittstellen.

b) Kombinatorische Elemente arbeiten nur auf der Eingabe und berechnen basierend darauf eine Ausgabefunktion.
Sequentielle Elemente speichern Informationen, sind also zustandsbasiert im Gegensatz zu kombinatorischen Elementen.

## Aufgabe 2

a) Sie erhält die niederwertigsten Bits der Instruction (31-26), also den Opcode, als Eingabe. Mithilfe dieser Information wird die ALU control und mehrere Multiplexer gesteuert, sodass der entsprechende Befehl umgesetzt werden kann.
b) Damit wird der Bytestring einer 16 Bit Adresse oder Immediate auf 32 Bit erweitert, wobei das Vorzeichen erhalten bleibt.
c) Er liefert entweder (bei Load/Store) eine Adresse oder (bei R-type und Branch Befehlen) den Wert des zweiten Source-Registers an die ALU.
d)
- summiere $t0 und $t1 mit der ALU
- schreibe Ergebnis in Register $s0
- erhöhe PC um 4

e) Performanz! Es lässt sich dadurch Pipelining durchführen, da ein Befehl, der keine Ladeoperation benötigt bereits begonnen werden kann, bevor der vorige Befehl komplett ausgeführt ist.
f) Bei Branch on equals z. B. werden die beiden Werte subtrahiert. Ist das Ergebnis 0, so wird der Sprung durchgeführt, da der Multiplexer durch das gesetzte Zero-Bit die neu berechnete Adresse an PC weitergibt.

## Aufgabe 3
a) Die Information wird in den niederwertigsten 6 Bit codiert (funct)
b) Die ALU Ansteuerung kann durch eine Wahrheitstabelle, implementiert in kombinatorischer Logik, umgesetzt werden.
c) Die Zieladresse setzt sich zusammen aus den 4 höchstwertigsten Bits des aktuellen PCs, der 26 Bit langen Adresse aus dem Befehl und zwei Nullen (da die Adresse immer durch 4 teilbar ist).

## Aufgabe 4
a) Ein Hazard ist eine Situation, die die Abarbeitung des nächsten Befehls im nächsten Zyklus verhindert.
- Structure Hazards: zwei Befehle können nicht gleichzeitig ausgeführt werden, weil sie die gleiche Resource benötigen.
Beispiel:
lw $s0 $t1
lw $s1 $t2
Beide Load Befehle benötigen den Datenspeicher, können jedoch nicht gleichzeitig darauf zugreifen
- Data Hazards: Warten auf Abschluss des vorherigen Befehls
Beispiel:
sub **\$s1** $t0 $t1
and $s2 **\$s1** $t3
Der And-Befehl benötigt den Inhalt von $s1, um ausgeführt zu werden, allerdings muss er warten, bis der Sub-Befehl sein Ergebnis im Speicher abgelegt hat.
- Control Hazards: Welcher Befehl als nächstes ausgeführt wird, hängt vom vorherigen ab.
Beispiel:
add $s0 $t0 $t1
beq $s0 $t2 foobar
add $s1 $t3 $t4

b) IF --> ID --> EX --> MEM --> WB
- IF (Instruction Fetch): Befehl aus dem Speicher laden
- ID (Instruction Decode): Decodieren der Instruktionen und Zugriff auf die jeweiligen Register
- EX (Execution): Ausführen des jeweiligen Befehls mithilfe der ALU bzw Ausrechnen der Sprungadresse
- MEM (Memory): Lesen bzw Schreiben von Befehlen in den Datenspeicher
- WB (Write Back): Zurückschreiben des Ergebnisses in die Register

In einem Taktzyklus sind 5 Instruktionen in Ausführung.

c)
(i) Data Hazards in Zeile 8 auf 9 und in Zeile 10 auf 11. Verursacht durch das Schreiben des endgültigen Wertes in der WB Phase (Zeile 8, 10), während dieser Wert bereits in der EX Phase von Zeile 9 und 11 benötigt wird.

(ii) Vertausche Zeile 9 und 10.

(iii) Neues Problem: Data Hazard zwischen MEM von Zeile 10 (nach vertauschen) und EX von Zeile 11

## Aufgabe 5

a)
- Zwischen $s0 in Z.1 und dem in Z.2 herrscht eine Read-After-Write-Beziehung, da der Wert für $s0 in Z.1 gesetzt wird aber für Z.2 benötigt
- Zwischen $s1 in Z. 1 und 2: WAR
- Zwischen $s0 in Z. 1 und 3: WAW, da beide Male ein neuer Wert für $so gesetzt wird. Und zusätzlich RAW, da der in Z.1 gesetzte Wert für $s0 für die Berechnung in Z.3 benutzt wird
- Zwischen $s0 in Z. 2 und 3: WAR
- Zwischen $s0 in Z. 2 und 3: RAW
- Zwischen $s1 in Z. 2 und 3: RAW

b) Hazards:
- Data Hazard zwischen Zeile 1 & 2
- Data Hazard zwischen Zeile 2 & 3

jeweils bei RAW. Lösung: Einfügen von 2 NOPS zw. den Zeilen 1 & 2, sowie 4 NOPS zwischen 2 & 3.

a = Zeile 1, b = Zeile 2, c = Zeile 3, 0 = NOP
   aaaaa
    00000
     00000
      bbbbb
       00000
        00000
         ccccc

c) keine NOPS benötigt.

d)
ohne forwarding: $(7 + 4) * 250 ps = 2750ps$
volles forwarding: $7 * 300 ps = 2100ps$
Speedup: $2750ps/2100ps = 1,3$x so schnell

## Aufgabe 6

a) Durch die Steuersignale ForwardA und ForwardB ist es möglich, entweder Werte aus den Registern zu nehmen, oder Werte, die im Taktzyklus vorher in der Execute Phase des vorhergehenden Befehls berechnet wurden oder Werte, aus der MeM Phase eines vorigen Befehls, bevor diese wieder in die Register übernommen werden. ForwardA und ForwardB steuern die Multiplexer, die die Quelle dafür auswählen.

b)

if ( MEM/WB.RegWrite &&                         // MEM/WB wird auf ein Register schreiben      
   ( MEM/WB.RegisterRD != 0) &&                 // Register rd ist nicht $zero
   ( MEM/WB.RegisterRD = ID/EX.RegisterRs ) )   // Register wird in MEM/WB und ID/EX verwendet und muss daher forgewardet werden.
        ForwardA = 01;                          // Forward von MEM/WB

// analog für Rt Register:

if ( MEM/WB.RegWrite &&                                 
   ( MEM/WB.RegisterRd != 0) &&                         
   ( MEM/WB.RegisterRd = ID/EX.RegisterRt ) )           
        ForwardB = 01;

Hazard in MIPS:

add $t1,$t1,$t2
add $t1,$t1,$t3
add $t1,$t1,$t4

c) Bei der dynamischen Branch Prediction wird die Vorhersage von der Historie abhängig gemacht. Dafür werden frühere Verzweigungsergebnisse gespeichert und anhand dessen eine Vorhersage getroffen, z.B. wenn die Bedingung mehrere Male hintereinander wahr war, so wird auch die Vorhersage "wahr" ergeben.

d)

for (i = 0; i < 3; i++)
   for (j = 0; j < 2; j++)
       //CODE

Mithilfe der 2-Bit Vorhersage wird, nachdem man die innere for-Schleife verlassen hat (j == 2), die äußere for-Schleife nicht verlassen, da die einmalige Fehlvorhersage nichts an der nächsten Vorhersage ändert. Somit liegt die Vorhersage immer nur beim Verlassen einer Schleife falsch. Bei der 1-Bit Vorhersage wird nach dem Verlassen der inneren Schleife immer angenommen, dass auch die äußere Schleife verlassen werden muss.