# Rechnerarchitektur: Übung 6

## Aufgabe 1

### a)

- Zeitlokalität: Annahme, dass auf ein Objekt nach dem Zugriff bald ein erneuter Zugriff erfolgt
- Platzlokalität: Annahme, dass auf ein Objekt in der Nähe des zugegriffenen Objektes ein Zugriff erfolgen wird.

### b)

- Der Cache wird benötigt, um das Lokalitätsprinzip richtig ausnutzen zu können, da kurzfristig zugegriffene Objekte und deren Nachbarn in den Cache kopiert werden. Im Vergleich zum Festplattenspeicher ist der Cache wesentlich schneller, was das System insgesamt beschleunigt
- Speicherhierarchie: Bevorzugt werden die Daten aus den schnelleren, aber kleineren Caches in den Arbeitsspeicher geladen. Sind sie dort nicht anzutreffen, wird versucht sie aus dem Hauptspeicher (DRAM) zu lesen; Funktioniert auch das nicht, so müssen sie in einem sehr langsamen Prozess von der Festplatte geladen werden.
- Beim Auftreten von Änderungen gibt es 2 Möglichkeiten:
- write-through: Werden Daten modifiziert, die im Cache gespeichert sind, so werden diese auch direkt in der darunterliegenden Speicherebene geändert.
- write-back: Daten werden zunächst nur im Cache geändert und als dirty markiert. Modifiziert werden sie bei der Verdrängung aus dem Cache.

### c)

- Hit: Datum, auf das zugegriffen werden soll, ist im Cache enthalten.
- Miss: Datum, auf das zugegriffen werden soll, ist nicht im Cache enthalten.

$\text{Hit ratio} = \frac{\text{Hits}}{\text{Zugriffe}}$
$\text{Miss ratio} = \frac{\text{Misses}}{\text{Zugriffe}}$

Verhältnis: $\text{Miss ratio} = 1 - \text{Hit Ratio}$

### d)
Eine Exception entsteht im Prozessor, ein Interrupt außerhalb (z. B. von einem I/O Controler). Beides sind Ausnahmezustände, die den normalen Arbeitsablauf unterbrechen.

## Aufgabe 2
### a)
Sowohl static multiple-issue als auch dynamic multiple-issue Prozessoren behandeln Parallelität zwischen unterschiedlichen Threads.
Bei Static multiple issue werden gleichzeitig auszuführende Befehle schon beim Compilen gruppiert und Hazards erkannt und umgangen.
Bei Dynamic multiple issue werden die auszuführenden Befehle von der CPU ausgewählt und Hazards mithilfe von hochkomplexen Techniken von der CPU umgangen.

### b)
Register Renaming ist eine Technik, um von physikalischen zu logischen Registern zu abstrahieren. Um Interferenzen bei der Parallelisierung zu vermeiden, werden doppelt verwendete Register umbenannt.

### c)
Loop unrolling: Schleifenkörper replizieren, um Sprünge zu vermeiden/vermindern und so höhere Parallelität zu erlauben.

## Aufgabe 3
### a)
Penalty pro Befehl I-Cache $= 6 \% * 10 \text{ Zyklen} = 0.6 \text{ Zyklen}$
Penalty pro Befehl D-Cache $= 10 \% * 10 \text{ Zyklen} * 20\% = 0.2 \text{ Zyklen}$
Tatsächliche CPI: $3 + 0.6 + 0.2 = 3.8$
Ideale CPU ist $3.8 / 3 = 1.27$ schneller.

### b)

$\text{Anzahl Zyklen} = 2 \text{ Zyklen} + 20 \% * 10 \text{ Zyklen} = 4 \text{ Zyklen}$

AMAT = 4 * 3 ns = 12 ns

## Aufgabe 4

direkt abbildender Cache:

| Block-Adresse | Cache-Index | Hit/Miss | 0 | 1 | 2 | 3 |
| ------------- | ----------- | -------- | ------- | ------- | ------- | ------- |
| 2 | 2 | Miss | | | Mem[ 2] | |
| 5 | 1 | Miss | | Mem[ 5] | Mem[ 2] | |
| 8 | 0 | Miss | Mem[ 8] | Mem[ 5] | Mem[ 2] | |
| 0 | 0 | Miss | Mem[ 0] | Mem[ 5] | Mem[ 2] | |
| 10 | 2 | Miss | Mem[ 0] | Mem[ 5] | Mem[10] | |
| 14 | 2 | Miss | Mem[ 0] | Mem[ 5] | Mem[14] | |
| 0 | 0 | Hit | Mem[ 0] | Mem[ 5] | Mem[14] | |
| 15 | 3 | Miss | Mem[ 0] | Mem[ 5] | Mem[14] | Mem[15] |
| 3 | 3 | Miss | Mem[ 0] | Mem[ 5] | Mem[14] | Mem[ 3] |

2-Wege assoziativer Cache:

| Block-Adresse | Cache-Index | Hit/Miss | Set 0 | - | Set 1 | - |
| ------------- | ----------- | -------- | ------- | ------- | ------ | ------- |
| 2 | 0 | Miss | Mem[2] | | | |
| 5 | 1 | Miss | Mem[2] | | Mem[5] | |
| 8 | 0 | Miss | Mem[2] | Mem[8] | Mem[5] | |
| 0 | 0 | Miss | Mem[0] | Mem[8] | Mem[5] | |
| 10 | 0 | Miss | Mem[0] | Mem[10] | Mem[5] | |
| 14 | 0 | Miss | Mem[14] | Mem[10] | Mem[5] | |
| 0 | 0 | Miss | Mem[14] | Mem[0] | Mem[5] | |
| 15 | 1 | Miss | Mem[14] | Mem[0] | Mem[5] | Mem[15] |
| 3 | 1 | Miss | Mem[14] | Mem[0] | Mem[3] | Mem[15] |

Vollassoziativer Cache:

| Block-Adresse | Hit/Miss | - | - | - | - |
| ------------- | -------- | ------- | ------- | ------- | ------ |
| 2 | Miss | Mem[2] | | | |
| 5 | Miss | Mem[2] | Mem[5] | | |
| 8 | Miss | Mem[2] | Mem[5] | Mem[8] | |
| 0 | Miss | Mem[2] | Mem[5] | Mem[8] | Mem[0] |
| 10 | Miss | Mem[10] | Mem[5] | Mem[8] | Mem[0] |
| 14 | Miss | Mem[10] | Mem[14] | Mem[8] | Mem[0] |
| 0 | Hit | Mem[10] | Mem[14] | Mem[8] | Mem[0] |
| 15 | Miss | Mem[10] | Mem[14] | Mem[15] | Mem[0] |
| 3 | Miss | Mem[3] | Mem[14] | Mem[15] | Mem[0] |

## Aufgabe 5

### a)

Codewort:

| 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | | | | | # | | | | |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |

| 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | | | # | | | | # | | # | # |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |

20 = 10100
17 = 10001
15 = 01111
10 = 01010
09 = 01001
07 = 00111
06 = 00110
05 = 00101
xor= 01101 (Paritätbits)

### b)

| 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | | | | | # | | | | |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |

| 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | | | # | | | | # | | # | # |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |

$\rightarrow$ Paritätsbits: 11000
$\rightarrow$ Berechnung:
21 = 10101
18 = 10010
17 = 10001
12 = 01100
11 = 01011
10 = 01010
09 = 01001
05 = 00101
03 = 00011
pb = 11000
xor= 01100 = 12 $\rightarrow$ At Index 12 bitflip

Korrekte Zahl mit korrigiertem Bit-Flip: 1001100001110011