# Ćwiczenia 8, grupa cz. 14-16, 27 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? |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | | |
Wojciech Bogucki | X | X | X |==X==| X | X | | | |
Mateusz Cerulewicz | X | X | X | X | | | | | |
Mateusz Garncarczyk | ==X== | X | X | X | | | | | |
Mateusz Golisz | | | | | | | | | |
Mateusz Kitzol | X | X | X | X | X | | | | |
Piotr Mańkowski | | | | | | | | | |
Michał Mękarski | | | | | | | | | |
Aleksandra Nicpoń | X | X | X | X | X | | | | |
Ksawery Plis | X | ==X== | X | X | | | | | | | |
Patryk Rybak | X | X | | X | | X | | | |
Rafał Spyra | X | X | X | | | X | | | |
Dominik Szczepaniak | X | X | X | X | X | | | | |
Taras Tsehenko | | | | | | | | | |
Maksymilian Wiśniewski | | | | | | | | | |
Martyna Wybraniec | X | X | X | X | X | | | | |
Natalia Zychowicz | X | X | | | | X | | | |
Patryk Maciąg | | X | X | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Mateusz Garncarczyk
:::

### Hazard sterowania (Control Hazard):
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.

### Hazard strukturalny (Structural hazard):
Sytuacja, w której kilka instrukcji chce w tym samym momencie skorzystać z tego samego zasobu.

### RAW, WAR, WAW (Data hazard):

**a) Procesor jednocyklowy:**
Nie ma żadnego hazardu, ponieważ każda instrukcja wykonuje się dopiero po skończeniu poprzedniej.

**b) Potokowy z pojedynczym ALU:**
sterowania - może być
strukturalny - nie może być
RAW - może być
WAR, WAW - nie może być

**c) Potokowy z wieloma jednostkami wykonawczymi:**
sterowania - może być
strukturalny - nie może być
RAW, WAR, WAW - może być

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: Ksawery Plis
:::

**Przetwarzanie potokowe z wykorzystaniem scoreboardingu jest podzielone na następujące etapy:**
1. Issue - instrukcja zostaje zlecona do wykonania
2. Read operands - czytanie argumentów
3. Execution - wykonanie operacji (arytmetycznej, logicznej, ...)
4. Write result - wdrożenie wyniku

**Jak algorytm radzi sobie z hazardami:**

* **WAW**
Przed rozpoczęciem fazy "Issue" scoreboard upewnia się, że żadne inne aktywne jednostki funkcyjne nie chcą zapisać wyników do naszego rejestru docelowego.
Jeśli trzeba, faza ta jest wstrzymywana i czekamy, aż będziemy mogli już zapisać.
* **RAW**
Przed rozpoczęciem fazy "Read operands" scoreboard sprawdza dostępność argumentów instrukcji.
Argumenty są dostępne jeśli żadna wcześniej zlecona instrukcja nie zamierza ich nadpisać.
W razie potrzeby faza czytania argumentów jest wstrzymywana, aż będą dostępne.
* **WAR**
Faza "Write result" jest wstrzymywana przez scoreboard w wypadku wykrycia hazardu WAR.
WAR występuje, jeśli jakaś wcześniejsza instrukcja ma jako jeden z argumentów rejestr, który chcemy nadpisać, ale jeszcze go nie przeczytała.
## Zadanie 3
:::success
Autor: Martyna Wybraniec
:::


Algorytm przetwarzania potokowego przy użyciu reorder buffera:

* pozwala na uruchamianie niezależnych instrukcji podczas stallingu
* instrukcje mogą obliczać się poza kolejnością (rozpoczęcie i zakończenie pozostaje w oryginalnej kolejności)
* obliczone wartości przechowywane są w Reorder Buffer Entry i są dostępne dla kolejnych instrukcji
* ostatecznie wartości są zapisywane do pamięci w oryginalnej kolejności

Jak algorytm radzi sobie z hazardami RAW, WAR, WAW?

Algorytm nie pozwala na hazardy RAW, WAR, WAW, ponieważ każda instrukcja zapisuje do Reorder Buffer Entry obliczoną wartość, z której przyszłe instrukcje mogą odpowiednio korzystać, natomiast do pamięci zawsze zapisuje wartości w prawidłowej kolejności. W przypadku RAW algorytm czeka, aż potrzebna wartość zostanie obliczona przed odczytaniem.

## Zadanie 4
:::success
Autor: Wojciech Bogucki
:::
:::info
Zadanie 4. Dany jest program

r3 = r1 * r2
r5 = r4 + r3
r6 = r4 + r1
r7 = r8 * r9
r4 = r3 + r7
r10 = r5 * r6

Podaj diagram wykonania i wylicz liczbę cykli zużytych przez ten program uruchomiony na następujących procesorach
1. procesorze potokowym z pojedynczym ALU. To ALU samo jest w pełni potokowe i działa w 6 cyklach. Każda instrukcja wykonuje się więc w fazach$^2$ F D E1 E2 E3 E4 E5 E6 WB.
1. procesorze potokowym z w pełni potokowymi niezależnymi jednostkami (po jednej sztuce) dla mnożenia (6 cykli) i dodawania (4 cykle). Instrukcja mnożenia wykonuje się więc w fazach F D E1 E2 E3 E4 E5 E6 WB, a dodawania w fazach F D E1 E2 E3 E4 WB. Procesor używa scoreboardu.
1. procesorze potokowym jak wyżej, ale używającym reorder buffera.

Jedynie procesor z punktu c) może używać forwardingu danych.
Możesz zignorować ewentualne hazardy strukturalne, ale
zaobserwuj fazy procesora, w którym mogą one wystąpić.

$^2$ Dla uproszczenia nie ma fazy MEM.
:::

1) procesor potokowym z pojedynczym ALU
Ignorujemy hazard struktularnych

r3 = r1 * r2  F D E1 E2 E3 E4 E5 E6 WB
r5 = r4 + r3    F D  D  D  D  D  D  D E1 E2 E3 E4 E5 E6 WB 
r6 = r4 + r1                        F D  E1 E2 E3 E4 E5 E6 WB
r7 = r8 * r9                          F  D  E1 E2 E3 E4 E5 E6 WB
r4 = r3 + r7                             F  D  D  D  D  D  D  D  E1 E2 E3 E4 E5 E6 WB
r10 = r5 * r6                                                 F  D  E1 E2 E3 E4 E5 E6 WB

26 cykle

2) procesor potokowy z w pełni potokowymi niezależnymi jednostkami

r3 = r1 * r2  F D E1 E2 E3 E4 E5 E6 WB
r5 = r4 + r3    F D  D  D  D  D  D  D  E1 E2 E3 E4 WB 
r6 = r4 + r1                        F  D  E1 E2 E3 E4 WB
r7 = r8 * r9                           F  D  E1 E2 E3 E4 E5 E6 WB
r4 = r3 + r7                              F  D  D  D  D  D  D  D  E1 E2 E3 E4 WB
r10 = r5 * r6                                                  F  D  E1 E2 E3 E4 E5 E6 WB

26 cykle

3) procesor potokowym jak wyżej, ale używającym reorder buffera

r3 = r1 * r2  F D E1 E2 E3 E4 E5 E6 WB
r5 = r4 + r3    F D              E1 E2 E3 E4 WB 
r6 = r4 + r1      F  D  E1 E2 E3 E4             WB
r7 = r8 * r9         F  D  E1 E2 E3 E4 E5 E6       WB
r4 = r3 + r7                        F  D  E1 E2 E3 E4 WB
r10 = r5 * r6                          F  D  E1 E2 E3 E4 E5 E6 WB

18 cykli
## Zadanie 5
:::success
Autor: Mateusz Kitzol
:::


a)

| Kolejne_instrukcje | 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 | WB | | | | | | | | | | | | | | | | | | | | | |
| r5 = r4 + r3 | | F | D | D | D | D | D | D | D | E1 | E2 | E3 | E4 | E5 | E6 | WB | | | | | | | | | | | | | | |
| r7 = r2 + r6 | | | F | F | F | F | F | F | F | D | E1 | E2 | E3 | E4 | E5 | E6 | WB | | | | | | | | | | | | | |
| r10 = r8 + r9 | | | | | | | | | | F | D | E1 | E2 | E3 | E4 | E5 | E6 | WB | | | | | | | | | | | | |
| r11 = r7 * r10 | | | | | | | | | | | F | D | D | D | D | D | D | E1 | E2 | E3 | E4 | E5 | E6 | WB | | | | | | |
| r5 = r5 + r11 | | | | | | | | | | | | F | F | F | F | F | F | D | D | D | D | D | D | E1 | E2 | E3 | E4 | E5 | E6 | WB |

Liczba cykli: 30

b)
| Kolejne_instrukcje | 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 |

Liczba cykli: 36

c)
| Kolejne_instrukcje | 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 |

Liczba cykli: 30

## Zadanie 6
:::success
Autor: Patryk Rybak
:::