# Ćwiczenia 8, grupa śr. 10-12, 19 kwietnia 2023

###### tags: `SYK23` `ć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? |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk | | | | | | | | | |
Mikołaj Dworszczak | | | | | | | | | |
Kacper Jóźwiak | X | X | X | | | | | | |
Dominik Kiełbowicz | | | | | | | | | |
Michał Kolasa | | | | | | | | | |
Konrad Kowalczyk | X | X | X | | | | | | |
Oskar Kropielnicki | X | X | X | | | | | | |
Anna Krysta | X | X | X | X | X | X | | | |
Jakub Krzyżowski | X | X | X | X | X | | | | |
Oskar Kubkowski | X | X | X | X | ==X== | | | | |
Mateusz Mazur | X | X | X | | | | | | |
Barbara Moczulska | X | X | X | X | X | | | | |
Kacper Sojda | X | X | X | X | X | | | | |
Marta Strzelec | X | X | | X | X | | | | |
Mikołaj Swoboda | | | | | | | | | |
Filip Szczepański | X | X | X |X | X | | | | |
Julian Włodarek | X | X | X |X | X | | | | |
Beata Łakoma | X | X | X | X | X | | | | |
Michał Łukasik | X | X | X | | | | | | |
:::

Tu można zadeklarować zad 5. z listy 7:
-
-
-

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

## Zadanie 1
:::success
Autor: Konrad Kowalczyk
:::

hazard sterowania - sytuacja, w której procesor dostaje instrukcję skoku warunkowego. Aż do 4 fazy cyklu wykonywania instrukcji nie wiadomo, czy skok będzie należało wykonać czy też nie, tymczasem kolejna instrukcja jest uruchamiana już podczas 2 fazy.

hazard strukturalny - sytuacja, w której kilka instrukcji chce w tym samym momencie skorzystać z tego samego zasobu.

RAW (read after write) - sytuacja, w której instrukcja zapisuje wartość w rejestrze, a któraś z kolejnych instrukcji chce ją odczytać (możliwe jest, że wartość nie jest jeszcze zapisana)

WAR (write after read) - sytuacja, w której instrukcja odczytuje wartość z rejestru, a któraś z kolejnych instrukcji ją nadpisuje (możliwe jest, że wartość zostanie zmieniona przed odczytaniem)

WAW (write after write) - sytuacja, w której instrukcja zapisuje wartość w rejestrze, a któraś z kolejnych instrukcji ją nadpisuje (możliwe jest, że dwie instrukcje będą chciały zapisać inne wartości pod ten sam rejestr lub że rejestr zostanie nadpisany w niewłaściwej kolejności)

a) procesor jednocyklowy - nie występują żadne hazardy, ponieważ każda instrukcja wykonuje się dopiero po skończeniu poprzedniej

b) procesor potokowy z pojedynczym ALU - występują hazard sterowania oraz hazard RAW (hazardy WAR i WAW tylko jeśli zezwolimy na out-of-order)
hazard strukturalny nie występuje, ponieważ odczyt i zapis danych z rejestru wykonują się w osobnych połowach fazy, a nie zachodzi sytuacja, w której dwa cykle są w tej samej fazie w tym samym momencie
hazard WAR nie występuje, ponieważ zapisanie wartości w późniejszej instrukcji zawsze nastąpi później niż jej odczytanie we wcześniejszej instrukcji
hazard WAW nie występuje, ponieważ ponownie nie ma sytuacji, w której dwa cykle są w tej samej fazie w tym samym momencie, oraz każda instrukcja wykonuje zapis w ostatniej fazie, a nie ma możliwości, żeby późniejsza instrukcja wykonała się wcześniej

hazard sterowania:

   if t1 = t2 goto L
   t1 = t3 + t4
L  t1 = t2 + t4

hazard RAW:

   t1 = t2 + t3
   t4 = t1 + t5

c) procesor potokowy z wieloma jednostkami wykonawczymi - mogą wystąpić wszystkie hazardy (hazard WAR tylko jeśli zezwolimy na out-of-order)

hazard sterowania:

   if t1 = t2 goto L
   t1 = t3 + t4
L  t1 = t2 + t4

hazard RAW:

   t1 = t2 + t3
   t4 = t1 + t5

hazard WAR:

   t1 = t0 + s1
   t0 = s2 - s3

hazard WAW:

   t1 = t0 + s1
   t2 = t0 + s2
   t1 = s2 - s3

hazard strukturalny:

   t1 = t0 + s1
   t1 = s2 * s3

## Zadanie 2
:::success
Autor: Jakub Krzyżowski
:::
Algorytm działa w 4 fazach:
1. Issue - sprawdza, czy żadne aktywne instrukcje nie mają tego samego docelowego rejestru, co obecna. Jeśli tak stallujemy instrukcję, aż hazard przeminie. (WAW)
2. Read operands - scoreboard monitoruje dostępność operandów, operandy są dostępne, jeśli żadna wcześniej zlecona instrukcja do nich nie pisze. (RAW)
3. Execution - wykonanie operacji
4. Write result - sprawdza, czy wszystkie jeszcze niewykonane instrukcje poprzedzające tą właśnie ukończoną odczytały swoje operandy (jeśli jednym z ich operandów jest ten sam rejestr do którego chcemy zapisać), jeśli tak, to czekamy z zapisem wyniku (WAR)

## Zadanie 3
:::success
Autor: Barbara Moczulska
:::


**Algorytm reorder buffera:**

Chcemy wykonywać instrukcje jak najszybciej się da (poza kolejnością, rownolegle) ale wdrażać zgodnie z kolejnością.

* Po dekodowaniu, wrzucamy instrukcję do reorder bufera
* Gdy instrukcja zakończy się, zapisuje wynik we wpisie ROB
* Jeżeli najwyższa instrukcja z buffera się wykona to można ją wdrożyć


Przy decyzji czy możemy rozpocząć jakąś instrukcje, możemy korzystać i z zawartości rejestrów ale i z buffera. Możemy zacząć nową instrukcje jeżeli jej argumenty będą wyliczone.

Jeżeli dekodukjemy instrukcje i nie ma dla niej jeszcze argumentów to wstrzymujemy cały potok. Bo zlecanie instrukcji i wdrożenie jest zgodne z kolejnością, tylko wykonywanie może być niezależne.

**hazady RAW, WAR i WAW:**

**RAW** - read after write - reorder buffer, forwarding, stalling

**WAR** - write after read - wyliczony rejestr jest wpisywany do buffora i jest traktowany jak dodatkowy rejestr, nienazwany i niedostępny z zewnątrz ale możliwy do wykorzystywania przez inne instrukcje w programie. W buferze może być zapamiętane wiele modyfikacji tego samego rejestru. Wtedy niezależnie od kolejności modyfikacji to pozostałe instrukcje zawsze będą korzystały z poprawnej wartości rejestru. A i tak wdrażane będą w kolejności poprawnej

**WAW** - write after write - tak jak w WAR

**porównanie do algorytmów ze scoreboard:**

Reorder buffer wymaga licznych operacji wpisywania i wyciągania informacji z bufora. A Scoreboard śledzi wykorzystanie zasobów procesora przez każdą instrukcje i blokuje instrukcje, które wymagają dostępu do zajętych zasobów.

## Zadanie 4
:::success
Autor: Filip Szczepański
:::

## Zadanie 5
:::success
Autor: Oskar Kubkowski
:::

### a)
ustnie

### b)

| Instrukcja---- | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |
| -------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| r3 = r1 * r2 | F | D | E1 | E2 | E3 | E4 | E5 | E6 | WB | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| r5 = r4 + r3 | | F | D | | | | | | D | E1 | E2 | E3 | E4 | WB | | | | | | | | | | | | | | | | | | | | | | |
| r7 = r2 + r6 | | | F | | | | | | | D | | | | E1 | E2 | E3 | E4 | WB | | | | | | | | | | | | | | | | | | |
| r10 = r8 + r9 | | | | | | | | | | F | | | | D | | | | E1 | E2 | E3 | E4 | WB | | | | | | | | | | | | | | |
| r11 = r7 * r10 | | | | | | | | | | | | | F | | | | | | | | | D | E1 | E2 | E3 | E4 | E5 | E6 | WB | | | | | | | |
| r5 = r5 + r11 | | | | | | | | | | | | | | | | | | | | | | F | D | | | | | | D | E1 | E2 | E3 | E4 | E5 | E6 | WB |

36 cykli

### c)
| Instrukcja---- | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| -------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| r3 = r1 * r2 | F | D | E1 | E2 | E3 | E4 | E5 | E6 | R | WB | | | | | | | | | | | | | | | | | | | | |
| r5 = r4 + r3 | | F | D | | | | | | E1 | E2 | E3 | E4 | R | WB | | | | | | | | | | | | | | | | |
| r7 = r2 + r6 | | | F | D | E1 | E2 | E3 | E4 | | R | | | | | WB | | | | | | | | | | | | | | | |
| r10 = r8 + r9 | | | | F | D | | | | | | | | E1 | E2 | E3 | E4 | R | WB | | | | | | | | | | | | |
| r11 = r7 * r10 | | | | | F | D | | | | | | | | | | | E1 | E2 | E3 | E4 | E5 | E6 | R | WB | | | | | | |
| r5 = r5 + r11 | | | | | | F | D | | | | | | | | | | | | | | | | E1 | E2 | E3 | E4 | E5 | E6 | R | WB |

30 cykli

## Zadanie 6
:::success
Autor: Anna Krysta
:::