# Ćwiczenia 8, grupa śr. 14-16, 17 kwietnia 2024

###### tags: `SYK24` `ć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 |
| ----------------------:| -----| --- | --- | --- | --- | --- |
Krzysztof Chorzempa | X | X | X | X | X | |
Maciej Ciepiela | X | X | X | | | |
Szymon Fica | X | X | X | X | X | |
Agnieszka Grala | X | X | X | X | X | |
Karolina Jędraszek | X | ==X== | X | X | X | |
Katarzyna Jodłowska | X | X | ==X== | | X | |
Dominik Kiełbowicz | | | | | | |
Michał Kolasa | | | | | | |
Rafał Krysa | X | | | | | |
Miłosz Krzysiek | X | X | X | X | X | |
Łukasz Kulczycki | | | | | | |
Leon Lepkowski | | X | X | X | ==X== | |
Hanna Makowska | X | X | X | ==X== | X | |
Jan Marek | X | X | X | X | | |
Cezary Miłek | X | X | X | | | |
Anna Pierzchała | X | X | X | X | X | |
Alan Pietrasz | X | X | X | | | |
Kacper Ponikowski | X | X | X | X | X | |
Dominik Walecko | X | X | X | | | |
Michał Włodarczak | X | X | | | | |
:::

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

## Zadanie 1
:::success
Autor: Dominik Walecko
:::


Hazard sterowania może wystąpić przy instrukcjach warunkowych, jeśli wyliczenie warunku korzysta z wartości, które nie zostały jeszcze poprawnie wyliczone.

Hazard strukturalny może wystąpić wtedy, kiedy wiele jednostek w tym samym czasie musi skorzystać z tego samego rejestru.

Hazardy danych podzielone wg typu:
1. RAW- Read After Write- kiedy dalsza instrukcja odczytuje rejestr, którego wartość nie jest jeszcze poprawnie wyliczona
2. WAR- Write After Read- kiedy dalsza instrukcja zapisuje wartość, która została przeczytana wcześniej
3. WAW- Write After Write- kiedy dalsza instrukcja zapisuje wartość, która została zapisana wcześniej

Rodzaje hazardów, które mogą wystąpić dla danych procesorów:
**a. Jednocyklowy**
Nie może wystąpić żaden hazard, bo do rejestrów zawsze odwołujemy się chronologicznie, zgodnie z kolejnością instrukcji.

**b. Potokowy z pojedynczym ALU**

1. Hazard sterowania może wystąpić
2. RAW- może wystąpić, WAW i WAR- nie może wystąpić
4. Hazard strukturalny- nie może wystąpić, powód jak w **a.**

**c. Potokowy z wieloma jednostkami wykonawczymi:**
Może wystąpić każdy z hazardów.

**Fragmenty kody generujące odpowiednie hazardy:**
1. **RAW**
ADD t, s, w
ADD y, z, t
2. **WAR**
MUL p, q, r
MUL s, t, y
ADD t, a, b
3. **WAW**
MUL t, s, y
ADD t, w, z
4. **strukturalny**
ADD t, s, y
ADD t, w, z
5. **sterowania**

> [name=Piotr Witkowski] Założenie: procesor potokowy ze scoreboardem, po jednej jednostce wykonawczej dla dodawania i mnożenia liczb całkowitych. Opóźnienie jednostki dodającej to 1 cykl, jednostki mnożącej to 7 cykle:
3. **WAW**
MUL t, s, y
ADD t, w, z

4. **WAR**
MUL p, q, r
MUL s, t, y
ADD t, a, b

## Zadanie 2
:::success
Autor: Karolina Jędraszek
:::

*Zapoznaj się z algorytmem przetwarzania potokowego przy użyciu scoreboardu. W jaki sposób ten algorytm radzi sobie z hazardami RAW, WAR i WAW?*

Fazy algorytmu:
1. Issue - pobranie instrukcji, ew. sprawdzenie czy nie występuje hazard WAW
2. Read operands - oczekiwanie na dostępność komponentów procesora (RAW)
3. Execution - wykonanie obliczeń
4. Write result - zapis wyniku do rekestru (WAR)

**Scoreboard** - komponent odpowiedzialny za zlecanie instrukcji do wykonania i rozstrzyganie hazardów.
Każda instrukacja przechodzi przez scoreboard, gdzie wykrywane są zależności danych. Scoreboard decyduje o tym kiedy instrukcja może zostać wykonana. W szczególności może w nim być kilka instrukcji i może okazać się, że np. trzecia w kolejności wejścia nie powoduje już hazardu i wtedy zakończy wykonanie przed pierwszą i drugą, które nadal czekają (out of order).

Podczas fazy decode może okazać się, że argumenty insturukcji nie są jeszcze dostępne (**hazard RAW**), wtedy przetrzymujemy ją w scoreboardzie (do momentu wykonania poprzedniej instrukcji).

**Hazard WAW** - wykonanie instrukcji mogłoby spowodować nadpisanie rejestru. Aby temu zapobiec instrukcja czeka na wejście do scoreboardu i wstrzymuje dalsze wczytywanie instrukcji do niego.

**Hazard WAR** - wykonanie instrukcji mogłoby spowodować błędne odczytanie rejestru. Wykrywamy go po wykonaniu instrukcji a przed zaktualizowaniem wyniku działania instrukcji w rejestrze (scoreboard wstrzymuje zapis wyniku do rejestru).

*Korzystamy z opóźnień wykonania instrukcji, które uczestniczą w hazardach.*


## Zadanie 3
:::success
Autor: Katarzyna Jodłowska
:::

Reorder Buffer
Idea: Wykonywanie instrukcji poza kolejnością, ale ponowne uporządkowanie ich przed udostępnieniem wyników w architekturze procesora.

Algorytm:
1. Pobieranie instrukcji.
2. Dodanie instrukcji do kolejki.
3. Równoległe obliczanie instrukcji, jeśli jej zasoby są dostępne, ale bez zapisywania wyników w rejestrach docelowych.
4. Gdy najstarsza instrukcja jest gotowa, zapisuje się jej wynik i usuwa się ją z kolejki.

Rozwiązanie hazardów:
* RAW (Read After Write): Reorder buffer zapewnia, że instrukcje są zapisywane w oryginalnej kolejności, więc nie ma problemu z dostępem do danych przed ich zapisaniem.
* WAR (Write After Read): Zasoby są sprawdzane przed rozpoczęciem obliczeń, aby uniknąć pisania danych przed ich odczytem.
* WAW (Write After Write): Instrukcje są zapisywane w oryginalnej kolejności, więc kolejność zapisu jest zachowana.

Porównanie ze Scoreboardem:
* Wykonanie operacji: Reorder buffer wykonuje dużo operacji na buforze w celu monitorowania i zarządzania instrukcjami. Scoreboard natomiast sprawdza wykorzystanie zasobów procesora i blokuje instrukcje, które wykorzystują zajęte rejestry.
* Obsługa wyjątków: ROB jest skutecznym narzędziem do obsługi wyjątków w przetwarzaniu potokowym. Ponieważ instrukcje są przetwarzane poza kolejnością, ROB zapewnia, że wyniki instrukcji są zapisywane dopiero po sprawdzeniu, czy nie wystąpiły żadne wyjątki. Dzięki temu możliwe jest uniknięcie błędów i niepoprawnych wyników. W przeciwieństwie do Scoreboardu, który może mieć trudności w obsłudze wyjątków związanych z nieterminowym wykonaniem instrukcji.
Algorytm z Reorder Bufferem umożliwia wykonanie instrukcji poza kolejnością, co może poprawić wydajność, zachowując jednocześnie precyzyjną obsługę wyjątków. W porównaniu z scoreboardem, ROB może być bardziej efektywny w niektórych przypadkach, ale wymaga więcej zasobów na zarządzanie kolejnością wykonania instrukcji.

## Zadanie 4
:::success
Autor: Hanna Makowska
:::

## Zadanie 5
:::success
Autor: Leon Lepkowski
:::

#### a)

#### b)

#### c)

## Zadanie 6
:::success
Autor: Michał Włodarczak
:::


Alias Table:
1. Register - nazwa rejestru
2. Valid - 1 lub 0 w zależności czy rejestr ma policzoną wartość
3. Tag - numer stacji rezerwacyjnej w której będzie liczyć się wartość rejestru (kiedy Valid jest 0)
4. Value - wartość rejestru (kiedy Valid jest 1)

Działanie:
Po kolei zostają pobierane i dekodowane instrukcje i w każdym cyklu jednostka wykonawcza patrzy na stacje rezerwacyjne i wybiera pierwszą instrukcję, która jest gotowa do obliczenia (i zaczyna się Execute). Na wyjściu z jednostki wykonawczej znamy wartość właśnie policzoną oraz Tag w którym liczyliśmy. Procesor dla wszystkich instrukcji z tym tagiem zmieni Valid z 0 na 1 i ustawi value na właśnie policzoną wartość.

Register renaming:
Zamiana na stacje rezerwacyjne, w których będzie wartość rejestru.

Jak radzimy sobie z hazardami:

RAW -> odwołujemy się do stacji rezerwacyjnych w których będzie wyliczona wartość danego rejestru (jeśli nie jest ona jeszcze zapisana w Alias Table)

WAR -> do odczytu skorzystamy ze stacji rezerwacyjnej więc po zmianie rejestru w jednostce wykonawczej dalej mamy tag do tej stacji

WAW -> w przypadku kiedy nadpisujemy rejestr to zmienimy tag na ten który wyliczy wartość tą zgodną z kolejnością


Wydajnościowo w porównaniu z reorder bufferem będzie podobnie, różni się tym, że w przypadku reorder buffera wartości będą zmieniane dopiero kiedy pierwsza instrukcja się całkowicie wykona.