# Ćwiczenia 6, grupa śr. 17-19, 13. kwietnia 2022

###### tags: `SYK21` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |--- |
Grzegorz Bielecki | | | | | | | | | |
Kamila Brzozowska | X | X | X |==X==| X | X | X | X | X |
Adam Ciężkowski | X | X | X | X | X | ==X== | X | X | |
Natalia Czerep | X | X | | | | | | | |
Jan Dalecki | X | X | X | X | X | X | X | X | X |
Marko Golovko | X | X |==X==| X | X | X | | | |
Adam Górkiewicz | X | X | X | X | X | X | X |==X==| X |
Piotr Gunia | X |==X==| X | X | | | | | |
Krzysztof Jadłowski | x | x | x | | | | | | |
Magdalena Jarecka | X | X | X | X | X | | | | X |
Mikołaj Jaszcza | X | X | X | X | | | | | |
Monika Jędrzejkowska | | | | | | | | | |
Michał Kierul | X | | X | X | | | | | |
Damian Lukas | | | | | | | | | |
Karol Ochman-Milarski | | | | | | | | | |
Piotr Piesiak | | | | | | | | | |
Damian Ratajski | | | | | | | | | |
Aleksandra Rozkrut | X | X | | X | X | | | | |
Marcin Sarnecki | X | X | X | X | X | | | | |
Maria Szlasa | | | | | | | | | |
Mateusz Burdyna | X | X | X | X |==X==| | | | X |
Nikola Wrona | X | X | X | X | X | | | | |
Marcin Wróbel | ==X==| X | X | X | X | X | X | X | X |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Marcin Wróbel
:::

Program:
$s0 = s1 + 5$
$s2 = s0 + s1$
$s3 = s0 + 15$
$s4 = s0 + s0$

Początkowe wartości rejestrów
$s0 = 11$
$s1 = 22$

Końcowe wartości rejestrów to
$s0 = 27$
$s1 = 22$
$s2 = 33$ (powinno być $49$)
$s3 = 26$ (powinno być $42$)
$s4 = 54$
Uniknięcie hazardów danych używając **nop**ów
Końcowe wartości rejestrów to
$s0 = 27$
$s1 = 22$
$s2 = 49$
$s3 = 42$
$s4 = 54$

## Zadanie 2
:::success
Autor: Piotr Gunia
:::


a)

b)

c)

d)

## Zadanie 3
:::success
Autor: Marko Golovko
:::


## Zadanie 4
:::success
Autor: Kamila Brzozowska
:::

### Always taken

### Always not taken

Dla always taken w każdej iteracji wyliczamy kolejne instrukcje tak, jakby pętla miała się wykonać. Zatem wykonają się niepotrzebnie 3 instrukcje przed wyjściem z pętli w trakcie oczekiwania na informację czy skok się wykona.
Liczba niepotrzebnie wykonanych instrukcji: 3 + i

Dla always not taken w każdej iteracji liczymy 3 pierwsze instrukcje, które są po wyjściu z pętli.
Liczba niepotrzebnie wykonanych instrukcji: 3*i + i

i-liczba iteracji

## Zadanie 5
:::success
Autor: Mateusz Burdyna
:::


### a)

Rozwiązanie podobne do poprzedniego zadania, ale tym razem marnujemy jeden cykl, a nie trzy.


### b)
s0 = *(t0 + 4)
s1 = *(s0 + 4)
if t1 = 0 goto L
...
L: s2 = s1 + 1

Gdybyśmy nie mieli wczesnego wykonywania skoków to diagram wyglądałby tak:


Pierwsza instrukcja spowodowała STALL drugiej, jednak w momencie gdy **S1** jest odczytywane to w pamięci znajduje się już poprawna wartość.

W przypadku early branch resolution w ostatniej instrukcji pojawi się hazard danych (oznaczony kolorem pomarańczowym)


s0 = t0 + t1
if s0 = 0 goto L

1. "późne" wykonywanie skoków

F D E M W
F D E M W

2. "wczesne" wykonywanie skoków

F D E M W
F D D E M W
F F D E M W (jakaś trzecia instrukcja)

## Zadanie 6
:::success
Autor: Adam Ciężkowski
:::


We wszystkich przypadkach mamy wczesne wykonywanie skoków, czyli kara wynosi 1 (w przypadku błędnego skoku).

1. **Always-taken:**
operacje skoku: 25%
błędne predykcje: 55%
wzrost CPI: 25/100 * 55/100 * 1 = 0,1375
2. **Always-not-taken:**
operacje skoku: 25%
błędne predykcje: 45%
wzrost CPI: 25/100 * 45/100 * 1 = 0,1125
3. **Predyktor 2-bitowy:**
operacje skoku: 25%
błędne predykcje: 15%
wzrost CPI: 25/100 * 15/100 * 1 = 0,0375
4. **Redukcja liczby skoków:**
* Always-taken:
operacje skoku: 12.5%
błędne predykcje: 55%
wzrost CPI: 12.5/100 * 55/100 * 1 = 0,06875
* Always-not-taken:
operacje skoku: 12.5%
błędne predykcje: 45%
wzrost CPI: 12.5/100 * 45/100 * 1 = 0,05625
* Predyktor 2-bitowy:
operacje skoku: 12.5%
błędne predykcje: 15%
wzrost CPI: 12.5/100 * 15/100 * 1 = 0,01875

## Zadanie 7
:::success
Autor: Jan Dalecki
:::
a)
Pierwsze dwie instrukcje w programie wymagają dostępu do pamięci odpowiednio w 4 oraz 5 cyklu działania procesora. Podczas tych cykli nie możemy wczytać nowej instrukcji zatem procesor zatrzyma się z wczytaniem instrukcji warunkowej do 6 cyklu. Kolejne instrukcje nie wymagają dostępu do pamięci zatem utracimy 2 cykle czekając na odczyt z pamięci w całym programie.

b)
Zauważmy, że dostęp do pamięci instrukcji jest wykonywany w każdym cyklu działania naszego potoku. Hazardy strukturalne zależą zatem od tego w którym cyklu nastąpi dostęp do pamięci na rzecz dereferencji. Instrukcje, które używają pamięci zawsze spowodują zatrzymanie w dalszym działaniu programu.

c)
Instrukcja nop jest pustą instrukcją, która razem z innymi instrukcjami programu jest zapisana w pamięci instrukcji. Jeżeli hazard strukturalny polega na tym, że dostęp do pamięci jest wykonywany jednocześnie do wczytania nowej instrukcji oraz innej wartości to pusta instrukcja nie poprawi działania programu, ponieważ sama wymaga dostępu do pamięci.

## Zadanie 8
:::success
Autor: Adam Górkiewicz
:::
Każda z operacji składa się z faz: M -> D -> E -> M -> W.
Startowy dostęp do pamięci w pierwszej fazie jest konieczny dla każdej instrukcji.
Dostęp do pamięci w czwartej fazie jest konieczny jedynie dla instrukcji typu (a) oraz (b).
Rozpoczęcie instrukcji (a) lub (b) powoduje, że dokładnie 3 cykle później nie może rozpocząć się nowa instrukcja, ponieważ potrzebowałaby ona dostępu do pamięci w tym samym momencie.
Jej rozpoczęcie musimy więc odłożyć na późniejszy cykl (a więc musimy wstrzymać potok na jeden cykl).
Liczbę utraconych cykli procesora możemy więc oszacować przez liczbę operacji (a) oraz (b).
Zgodnie z tabelką, wyniesie ona #operacji * 0.36.

## Zadanie 9
:::success
Autor: Magdalena Jarecka
:::

graph LR
A[IM] -->B[RF]
    B --> C[EXMEM]
    C --> D[RF]

Zwykle jeśli stosowaliśmy forwarding, to dane przekierowywaliśmy z miejsc pomiędzy EX i MEM lub MEM i RF. Po połączeniu EX i MEM nie możemy już robić forwardingu ze ścieżki pomiędzy nimi.

W przypadku poniżej niebieska strzałka symbolizująca forwarding nie miałaby już sensu i trzeba by było przenieść ją na ścieżkę pomiędzy DM a RF.

W ten sposób, pomimo że mamy mniej kroków do wykonania (4 a nie 5) to w niektórych przypadkach późniejsze instrukcje musielibyśmy dodatkowo wstrzymywać (stalling), aby poczekały krok dłużej na wyniki z poprzednich instrukcji. Tak więc nie pogorszy to wydajności ale też znacząco nie poprawi.

s1 = *(s2)
s3 = s4 + s5

F D EXMEM WB <- nie wykorzystuje EX a wykorzystuje MEM
F D EXMEM WB <- wykorzystuje ALU (EX), a nie wykorzystuje MEM

s1 = s2 + s3
s4 = *(s1)

s1 = *(s2)
s3 = s1 + s4

F D EXMEM WB
F D EXMEM