## Useful stuff
Kontrollsignale:
```
architecture behave of maindec is
signal controls: STD_ULOGIC_VECTOR(10 downto 0);
begin
process(op) begin
case op is
when "0000011" => controls <= "reg_write=1|imm_src=00|alu_src=1|mem_write=0|result_src=01|0branch=0|alu_op=00"; -- lw
when "0100011" => controls <= "reg_write=0|imm_src=01|alu_src=1|mem_write=1|result_src=00|0branch=0|alu_op=00"; -- sw
when "0110011" => controls <= "reg_write=1|imm_src=--|alu_src=0|mem_write=0|result_src=00|0branch=1|alu_op=00"; -- R-type
when "1100011" => controls <= "reg_write=0|imm_src=10|alu_src=0|mem_write=0|result_src=00|1branch=0|alu_op=10"; -- beq
when "0010011" => controls <= "reg_write=1|imm_src=00|alu_src=1|mem_write=0|result_src=00|0branch=1|alu_op=00"; -- I-type ALU
when "1101111" => controls <= "reg_write=1|imm_src=11|alu_src=0|mem_write=0|result_src=10|0branch=0|alu_op=01"; -- jal
when "0001011" => controls <= "reg_write=1|imm_src=00|alu_src=1|mem_write=0|result_src=00|0branch=1|alu_op=10"; -- popcount
when others => controls <= "reg_write=-|imm_src=--|alu_src=-|mem_write=-|result_src=--|-branch=-|alu_op=--"; -- not valid
end case;
end process;
(RegWrite, ImmSrc(1), ImmSrc(0), ALUSrc, MemWrite,
ResultSrc(1), ResultSrc(0), Branch, ALUOp(1), ALUOp(0), Jump) <= controls;
end;
```
**Schaltsymbole**:

Bin/Hex/Dec:

**Writethrough**:


**Writeback**:


**LRU/LFU/FIFO:**

---
# Klausur 2022
## RISC-V Assembler
### a)
```
int a = -1;
int b = 0x0C0FFEE;
```
```
addi s0, zero, -1
```
Problem: Imm bei addi darf maximal 12 Bit (signed, 2048 bis -2047) groß sein. Solution: Aufsplitten
0x0c0ffee
0000|1100|0000|1111|**1**111|1110|1110
lui sonderfall 12. Bit (11...0) -> 1
- 1 zu den oberen 20 addieren zur korrektur
0000|1100|0001|0000|**1**111|1110|1110
upper 20: 0000|1100|0001|0000 = 0x0C10
lower 12: 1111|1110|1110 = 0xFEE
```
addi s0, zero, -1
lui s1, 0x0C10
addi s1, 0xFEE
```
### b)
```c
if (a <= b) {
a = b;
} else {
b = a;
}
```
```
; s0 = a, s1 = b
cond_if:
; ble rs1, rs2, label = bge rs2, rs1, label
; b >= a <-> a <= b
; a < b <-> b > a
blt s1, s0, cond_else ; PC += 12
add s0, s1, zero
jal zero, done ; PC += 8
; 3 instructions = 12 + 20 = 32
cond_else:
add s1, s0, zero
; 4 instructions = 16 + 20 = 36
done:
```
### c)
```c
int foo(int a) {
int b = foo(a+1)
}
```
```
; a0 = a
; t0 = b
foo:
addi sp sp -4
sw ra 0(sp)
; a = a + 1
addi a0, a0, 1
; foo(a + 1)
jal ra, foo
; int b = foo(a+1)
add t0, a0, zero
; load ra
lw ra 0(sp)
addi sp sp 4
jalr zero, ra, 0 ; ret = jr ra
```
- Recursive ohne Abbruchbedingung -> stack overflow
- Der berechnete wert in `b` wird aufgrund der calling-convention nicht gespeichert und wird nicht korrekt zurueckgegeben. Denn b ist ein temporary register.
## Arithmetische Schaltungen
## Singlecycle

### a)

Extend Unit adden:
- Input: Nur Bits 7:0 relevant. Erweitern [31:8] mit wert von bit 7
- Output: 31:0
Multiplexer erweitern -> ResultSrc 11 gibt Ergebnis der Extend-Unit weiter
Siehe load-word
LW aus RISCV: aber mit neuem **result_src=11**
```
when "0000011" => controls <= "reg_write=1|imm_src=00|alu_src=1|mem_write=0|result_src=01|0branch=0|alu_op=00"; -- lw
```
### b)
#### Durch einen Fehler in der Produktion kam es zu einem Fehler. Der untere Eingang des Addierers vor dem PCPlus4 Signal hat eine 8, statt einer 4 anliegen und dadurch wird der PC um 8, statt um 4 erhöht. (i) Wie wirkt sich dieser Fehler aus? (ii) Welche Instruktionen sind davon betroffen? (iii) Mit welchem Software Workaround könnte die CPU trotzdem betrieben werden?
(i) Jede 2. Instruktion wird übersprungen
(ii) Nicht betroffen sind alle instruktion die direkt zum PC schreiben:
- Branch instructions
- Nur wenn die Condition eintritt, dann nicht betroffen.
- Tritt die Condition nicht ein, dann wird trotzdem
- JALR
- JAL (pc+4 von ALU berechnet)
- jal zero label -> RD nicht verwendet
Alles was PC+4 verwendet ist betroffen.
(iii) Nach jeder Instruktion ein NOP einfügen, so dass nur die NOPS übersprungen werden.
## Multicycle
### a)
#### Um einen Wert von einem Register in ein anderes zu kopieren haben wir bisher zB den Befehl addi genutzt, weil es keinen eigenen Befehl für das Kopieren gibt. Wir könnten einen mv rd, rs1 Befehl mit der Semantik rd = rs1 einführen. Mit Blick auf den Multicycle RISC-V Prozessor: Sollte ein mv-Befehl zum Kopieren in den Befehlssatz aufgenommen werden? Was spricht dafür, was dagegen?

Pros:
- Man braucht den ExecuteR state nicht mehr, da der Wert direkt geladen wird. `0 + wert` ist jetzt keine sinnvolle operation.
Cons:
- Overhead durch neuen Befehl -> **Reduced** Instruction Set!
### b)
#### Nimm an, dass durch einen Fehler in der Fertigung das LSB des Signals ALUSrcB (siehe auch Ausgang der Control Unit) konstant auf 0 gesetzt ist. (i) Welche der folgenden Befehl funktionieren dadurch nicht mehr einwandfrei? (ii) Begründe kurz deine Auswahl.

R-typ: sub funktioniert (verwendet nur register)
Es geht nichts mit Immediates.
BEQ: Wird in S1 falsche berechnet. Branch target wird precomputed im Decode
lw,sw,addi
## Pipelined
#### Gegeben ist ein RISC-V Prozessor mit fünfstufier Pipeline (fetch, decode, execute, memory, writeback). Wird ein Register von einem Befehl geschrieben, so ist der geschriebene Wert erst nach der writeback Stufe verfügbar. Bedingte (branches) als auch unbedingte Sprünge (jumps) werden in der execute Stufe getätigt. Dabei werden auch fälschlicherweise geladene Befehle aus der Pipeline gelöscht. (flushen der Pipeline).
#### Auf dem Prozessor wird folgendes Programmfragment aussgeführt:
Achtung: Pseudoinstructions
j end = jal zero, end
```
s1 addi t3, zero, -5
s2 lw t2, 5(s0)
s3 beq t0, t1, else
s4 or t0, t2, t1
s5 j end
else:
s6 sub t2, t0, t1
end:
s7 xor a0, t3, t2
```
### a)
#### Gib alle Datenabhängigkeiten im Programm an, die den Befehl s7 betreffen, und klassifiziere diese entsprechend (RAW, WAR, WAW)
RAW:
s1, s7
s2, s7
s6, s7
### b)
#### Finde und erläutere alle Pipeline-Konflikte des Programms
JAL: Immer ein KK
KK: S3 -> S4, S5 (bei Jump)
DK: S2 -> S4 (bei keinem Jump in S3) - RaW (t2)
KK: S5 -> S6, S7
DK: S6 -> S7 - RaW (t2)
https://docs.google.com/spreadsheets/d/1e0Y5xpG3QHzW_wlWyPzO2kd5bGy0k9aMZssAP7elz7o/edit?usp=sharing
### c)
#### Behebe alle Pipeline-Konflikte des Programms durch Einfügen der minimlaen Anzanl an NOPs. Hinweis: Es ist ausreichend, statt der vollständigen Befehle die Bezeichner (s0, s1, ...) zu verwenden.
Jump/Branch: 2 NOPS danach.
Daten Konflikt: 3 NOPs danach.
1. KK beheben.
2. Schauen ob die DK noch immer bestehen.
```
s1 addi t3, zero, -5
s2 lw t2, 5(s0)
s3 beq t0, t1, else
nop
nop
s4 or t0, t2, t1
s5 j end
nop
nop
else:
s6 sub t2, t0, t1
nop
nop
nop
end:
s7 xor a0, t3, t2
```
### d)
#### Minimiere die Anzahl der benötigten NOPs durch Umordnen der Befehle. Die Semantik des Programms darf dabei nicht verändert werden.
- Inverten der Condition explain please???
- Anstatt BEQ, BNE
- Also: `or t0, t2, t1` und `sub t2, t0, t1` tauschen
- Aber eigentlich darf man das nicht, weil man nur umordnen soll. Hier müsst man die Instruktion umschreiben.
- BEQ: Instruktionen danach werden nicht executed, daher kann man die NOPs (eigentlich) entfernen. Werden sowieso geflushed.
Unsere Variante: Es kann nichts nur durch Umordnung verändert werden.
```
s1 addi t3, zero, -5
s2 lw t2, 5(s0)
s3 beq t0, t1, else
nop
nop
s4 or t0, t2, t1
s5 j end
nop
nop
else:
s6 sub t2, t0, t1
nop
nop
nop
end:
s7 xor a0, t3, t2
```
Tobi Variante:
```
s2 lw t2, 5(s0)
s1 addi t3, zero, -5
s3 beq t0, t1, else´
nop
s4 or t0, t2, t1 (flushen wenn sprung genommen)
s5 j end
else:
s6 sub t2, t0, t1 (wenn nicht sprung genommen durch jump geflused)
nop
nop
nop
end:
s7 xor a0, t3, t2
```
### e)
$n + 4$ Instruktionen!
4 aufgrund laden und entladen
**branch taken**: 10 Instruktionen = 10 + 4 Cycles
lw
addi
beq
nop
nop
sub
nop
nop
nop
xor
**branch not taken**: 10 Instruktionen = 10 + 4 Cycles
lw
addi
beq
nop
nop
or
j
nop
nop
xor
### f)
Bestmöglicher Speedup: n
Also in diesem Fall: 12
(theoretisch)
## Leistungsbewertung
### a)
Bei der Anschaffung eines RISC-V Prozessors stehen zwei Varianten zur Verfügung:
- Singlecycle-CPU P1 (ohne Pipelining), mit 1 GHz
- Multicycle-CPU P2 mit 2.5 GHz, CPI-Werte der einzelnen Befehle können der folgenden Tabelle entnommen werden.

Befehl Anzahl CPI
R-Typ 39000 4
addi 13000 4
beq 9000 3
lw 20000 5
jump 9000 3
sw 10000 4
Summe 100000
i)
$T_{exe} = I_c \cdot CPI \cdot T$ wobei $I_c$ die Anzahl der Instruktionen, $CPI$ die durchschnittliche Anzahl an Taktzyklen pro Instruktion und $T$ die Taktperiode = (1/Taktfrequenz)
$CPI_P1 = 1 (single cycle!)$
Relative Klassenhäufigkeiten berechnen!
$CPI_P2 = 0.39*4 + 0.13*4 + 0.09*3 + 0.2*5 + 0.09*3 + 0.1*4 = 4.02$
ii)

$T_{p1} = 100000 * 1 * 10^{-9} = 0.1ms$
$T_{p2} = 100000 * 4.02 * 1/(2.5*10^{9}) = 0.1608ms$
### b)
#### Ein neuer Compiler wird entwickelt, der ein Teilprogramm in eine andere Sequenz von Befehlen als der alte Compiler übersetzt. Die Sequenzen lauten wie folgt:
- neuer Compiler: drei lw, ein beq, fünf R-Typ
- alter Compiler: fünf lw, ein jump, vier R-Typ
#### Für welche der Prozessoren (P1 oder P2) sollte der neue Compiler verwendet werden? Begründe deine Antwort mithile von Berechnungen.
**singlecycle**: 1 Instruktion weniger, daher 1 Cycle weniger
3 + 1 + 5 = 9
5 + 1 + 4 = 10
neue hat weniger instructions, daher fuer single cycle more efficient
**multicycle**: anschauen wieviele cycles ein lw braucht
unterschied: 2 * 5 weniger, 1 * 4 mehr
-> Du musst die Anzahl der Cycles berücksichtigen
lw: 5 CPI
beq/jmp: 3 CPI
r-typ: 4 CPI
alt: 5 * 5 + 3 * 1 + 4 * 4 = 44
neu: 3 * 5 + 3 * 1 + 5 * 4 = 38
38 < 44, daher ist es auf Multicycle schneller.
Antwort: Neuen compiler für beide verwenden
## Caches
- Least Frequently Used: Cache verwenden, der die minimale Anzahl an Zugriffen erfahren hat
- Least Recently Used: Cache verwenden, der am längsten nicht mehr benutzt wurde
- FIFO: First in First Out
### a)
#### Gegeben ist ein Direct-Mapped Cache mit 4 Blöcken. Es wird nacheinander auf die folgenden Speicheradressen zugegriffen:
#### 0xA, 0xF, 0x4, 0x7, 0xA, 0xB, 0x4, 0x6, 0x4, 0x1, 0x4
siehe Excel
#### (i) Befülle die folgende Tabelle mit den Adressen über die Zeit (ii) Gib den Endzustand des Caches nah den gegebenen Speicherzugriffen an. (iii) Berechne außerdem die Trefferrate des Caches
Direct mapped: Cacheblock für jede Adresse anschreiben (startet beim LSB)

### b)
Mögliche Verdrängungsstrategien: LRU, LFU, FIFO
LFU: frequenz des ...cacheblocks (nicht der adresse) wird gezählt.
- Count nur Hits oder alle arten von Zugriffe?

---
# Klausur 2021
- 3 kurze Assembly Fragen (eine davon rekursive Fkt.)
- Befehl in Maschinencode umwandeln
- Kombinatorische Schaltung: Wahrheitstabelle ausfüllen und angeben, um welche arithmetische Operation es sich handelt
- Single Cycle CPU um den Befehl load byte erweitern
- MultiCycle CPU entscheiden, ob ein move befehl ( move rd rs1 entspricht rd =rs1) sinnvoll ist. Welche Vorteile/Nachteile gibts. Zweite Frage war was passiert wenns LSB vom AluSrcB konstant 0 is
- Pipelined Datenabhängigkeiten und Konflikte erkennen. Diese mit NOPs lösen und als Letztes dann umsortieren
- Leistungsbewertung war a klassisches Bsp mit Single cycle und Multi cycle CPI ausrechnen und Ausführungszeit
- Caches: direct mapped cache ausfüllen, Trefferrate ausrechnen; assoziativer cache war gegeben, du musstest bestimmen welche Strategie verwendet wurde
# Rechnerarchitektur (Sommersemester 2021)
## 1. MIPS-Assembler (10 P.)
### a)
Übersetze das folgende C-Fragment in MIPS-Assembler. Benutze dafür nur native Befehle (keine Pseudo-Instruktionen). Nimm an, dass die Variablen a, b und c in den Registern $s0, $s1 und $s2 liegen
```c
if(a > b) {
c = a%b;
} else {
c = 8*a - b;
}
```
```asm
# s0 = a, s1 = b, s2 = c
ble cond_else
; if branch
rem s2, s0, s1
j done
; else branch
cond_else:
; t0 = s0 << 3
slli t0, s0, 3
; s2 = t0 - s1
sub s2, t0, s1
done:
```
### b)
#### Übersetze die folgende C-Funktion in MIPS-Assembler. Beachte dabei die Kon-ventionen bezüglich Funktionsaufrufen. Hinweis: Nimm an, dass eine Funktion mit dem Label bar bereits existiert und Parameter gemäß Konvention übernimmt. Du kannst außerdem annehmen, dass a2 mit 32-Bit darstellbar ist.
```c
int foo(int a, int b) {`
int a2 = a*a;
return bar(a2, b) + a;
}
```
```asm
; a0 = a; a1 = b
foo:
; 4 = return address, 4 = variable
addi sp sp -8
sw ra 0(sp)
sw s0 4(sp)
; a2 ... s0
addi s0 a0 0
; a2 = a*a
mul a0 a0 a0
jal ra bar # jal bar
; ret_val + a
add a0 a0 s0
; load ra; restore s0
lw ra 0(sp)
lw s0 4(sp)
addi sp sp 8
jalr zero, ra, 0 # ret = jr ra
```
#### Ausführbare Version
```asm
.globl main
main:
addi a0, zero, 1
addi a1, zero 1
jal foo
addi a1 a0 0
addi a0 zero 1
ecall
addi a0 zero 10
ecall
# a0 = a; a1 = b
foo:
# 4 = return address, 4 = variable
addi sp sp -8
sw ra 0(sp)
sw s0 4(sp)
# a2 ... s0
addi s0 a0 0
# a2 = a*a
mul a0 a0 a0
jal ra bar # jal bar
# ret_val + a
add a0 a0 s0
# load ra; restore s0
lw ra 0(sp)
lw s0 4(sp)
addi sp sp 8
jalr zero, ra, 0 # ret = jr ra
bar:
addi sp sp -4
sw ra 0(sp)
add a0 a0 a1
lw ra 0(sp)
addi sp sp 4
jalr zero, ra, 0
```
## 2. Maschinensprache (5 P.)
Startadresse: 0x40000088
Angabe (angepasst)
blez t0 , aneg
bgez t1 , bpos
andi a0 , t0 , 1
and s0 , a0 , t1
j end
bpos:
... 5 Befehle
aneg:
... 3 Befehle
end:
...
### Pseudobefehle
B-Typ: imm[12,10:5], rs2, rs1, funct3, imm[4:1,11], opcode
**bge zero, t0, aneg** :
imm = jmp target: 10 * 4Byte = 40 = 101000
- Sign Extend: 0000000|101000 -> [12:0]
imm[12, 10:5]: 0 | 000001
rs2: 00101 -> t0 = x5
rs1: 00000 -> zero = x0
funct3: 101
imm[4:1,11]: 0100
opcode: 1100011
0|000001|00101|00000|101|01000|1100011
0000|0010|0101|0000|0101|0100|0110|0011 -> convert blocks to hex -> 0x02505463
---
bge t1, zero, bpos
R-Typ
and s0 , a0 , t1
a0: x10 -> 01010
s0: x8 -> 01000
t1: x6 -> 00110
funct7: 0000000
funct3: 000
op: 0110011
rd: s0
rs1: a0
rs2: t1
0000000|00110|01010|000|01000|0110011
I-Typ
andi a0 , t0 , 1
a0: x10 -> 01010
t0: x5 -> 00101
rd: a0
rs1: t0
imm[11:0]: 000000000001
funct3: 000
000000000001|00101|000|01010|0010011
## 3. Arithmetische Schaltungen (6 P.)
// Maybe later
## 4. MIPS-Prozessor mit kombinatorischem Steuerwerk (14 P.)
### a)
Single Cycle:

or: R-type
addi: I-type
beq: B-type
sw: S-type
```
architecture behave of maindec is
signal controls: STD_ULOGIC_VECTOR(12 downto 0);
begin
process(op) begin
case op is
when "0000011" => controls <= "reg_write=1|imm_src=000|alu_src=1|pc_ctrl=1|mem_write=0|result_src=01|branch=0|alu_op=00|jump=0"; -- lw
when "0100011" => controls <= "reg_write=0|imm_src=001|alu_src=1|pc_ctrl=1|mem_write=1|result_src=00|branch=0|alu_op=00|jump=0"; -- sw
when "0110011" => controls <= "reg_write=1|imm_src=---|alu_src=0|pc_ctrl=1|mem_write=0|result_src=00|branch=0|alu_op=10|jump=0"; -- R-type
when "1100011" => controls <= "reg_write=0|imm_src=010|alu_src=0|pc_ctrl=1|mem_write=0|result_src=00|branch=1|alu_op=01|jump=0"; -- beq
when "0010011" => controls <= "reg_write=1|imm_src=000|alu_src=1|pc_ctrl=1|mem_write=0|result_src=00|branch=0|alu_op=10|jump=0"; -- I-type ALU
when "1101111" => controls <= "reg_write=1|imm_src=011|alu_src=0|pc_ctrl=1|mem_write=0|result_src=10|branch=0|alu_op=00|jump=1"; -- jal
when "1100111" => controls <= "reg_write=1|imm_src=000|alu_src=-|pc_ctrl=0|mem_write=0|result_src=10|branch=-|alu_op=--|jump=1"; -- jalr
when "0010111" => controls <= "reg_write=1|imm_src=100|alu_src=-|pc_ctrl=1|mem_write=0|result_src=11|branch=0|alu_op=--|jump=-"; -- auipc
when others => controls <= "reg_write=-|imm_src=---|alu_src=-|pc_ctrl=-|mem_write=-|result_src=--|branch=-|alu_op=--|jump=-"; -- not valid
end case;
end process;
(RegWrite, ImmSrc(2), ImmSrc(1), ImmSrc(0), ALUSrc, PCControl, MemWrite,
ResultSrc(1), ResultSrc(0), Branch, ALUOp(1), ALUOp(0), Jump) <= controls;
end;
```
### b)
TODO: for later
## 5. Gleitkommazahlen (8 P.)
$(-1)^S \times 2^{E-127} \times 1.M$
### a)
Berechne den dezimalen Wert der folgenden IEEE-754 Single-Precision Zahl.

**Exponent** 01111101 = 64+32+16+8+4+1 = 125
**Mantisse**: 011 + 20 bits
011 => $0 \cdot 0.5 + 1 \cdot 0.25 + 1 \cdot 0.125 = 0.375$
$(-1)^S \cdot 2^{E - 127} \cdot (1 + M)= (-1)^0 \cdot 2^{125 - 127} \cdot 1.375 = 0.34375$
### b)
Stelle −6.5 im IEEE-754 Single-Precision Format dar.
$-6.5 = - 110.1_2 = (-1)^1 \cdot 2^{129-127} \cdot (1.101_2)$
Also:
$S = 1$
$E = 129 = 0b10000001$ (110.1 zu 1.101 -> 2 Stellen verschieben)
$M = 1010..0$
Daher
$1|10000001|10100...0$
### c)
Berechne das Produkt der Zahlen aus a) und b) im IEEE-754 Single-Precision
Format und wandle das Resultat zusätzlich in eine Dezimalzahl um. Gib deinen
Lösungsweg an.
1) sign bit $0\ \text{XOR}\ 1 = 1$
2) exponent $129 + 125 - 127 = (0+127) = 01111111_2$
- Bias muss einmal abgezogen werden, da man es sonst doppelt hat.
- $(A + Bias) + (B + Bias) - Bias = (A + B ) + Bias$
4) mantissen produkt:
reminder: exponent geht von 128 bis -127
$$
\begin{align}
1.101*1.011 = \\
1.011 + \\ 0.1011 + \\ 0.001011 = \\ 10.001111
\end{align}
$$
$=10.001111 \cdot 2^{E}$
$=1.0001111 \cdot 2^{E+1}$
$E+1= (0+1 + 127)=128= 10000000_b$
1 | 10000000 | 0001111
$(-1)^1 \cdot 2^{1} \cdot (1 + \frac{1}{2^4} + \frac{1}{2^5} + \frac{1}{2^6} + \frac{1}{2^7}) = -2.234375$
## 6. Pipelining (12 P.)
### b)
```c
int main () {
int a = 42;
int b = 14;
while ( b != 0) {
int t = b ;
b = a % b ;
a = t ;
}
int gcd = a ;
```
## 7. MIPS-Prozessor mit sequenziellem Steuerwerk (9 P.)
## 8. Leistungsbewertung (7 P.)
## 9. Caches (9 P.)