# Ćwiczenia 8, grupa cz. 10-12, 18 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- |
Borys Adamiak | X | X | ==X== | X | X | X |
Michał Chawar | X | X | X | X | X | |
Julia Cygan | X | X | X | X | | X |
Maciej Dengusiak | X | X | X | X | X | ==X== |
Patryk Flama | ==X== | X | X | X | X | X |
Szymon Fluder | X | X | X | X | | |
Aleksandra Jędrzejak | X | X | X | X | X | |
Mikołaj Karapka | X | ==X== | X | X | X | X |
Viktoriia Kashpruk | X | X | X | X | | |
Wiktor Małek | X | X | X | X | X | X |
Błażej Molik | X | X | X | | | |
Andrzej Morawski | | | | | | |
Konrad Oleksy | | | | | | |
Lucjan Pucelak | X | X | X | | | |
Aleksandra Sęk | | | | | | |
Radosław Śliwiński | | | | | | |
Piotr Traczyński | X | X | X | X | X | |
Katarzyna Trzos | X | X | X | ==X== | X | X |
Piotr Warząchowski | X | X | X | X | | X |
Olga Zaborska | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Patryk Flama
:::


### Hazard sterowania
Występuje przy skokach warunkowych, aż do końca 4 fazy cyklu nie wiadomo którą ścieżkę rozgałęzienia wykonać (nie wiadomo jeszcze co będzie kolejną instrukcją)

### Hazard strukturalny
kilka instrukcji w tym samym momencie chce skorzystać z tego samego zasobu procesora

### Hazard danych
#### RAW (read after write)
jedna instrukcja nie zdążyła jeszcze zapisać, a inna już odczytuje wartość tej komórki
#### WAR (write after read)
jedna intrukcja nie zdążyła jeszcze odczytać, a inna już nadpisała wartość tej komórki
#### WAW (write after write)
jedna instrukcja po drugiej zapisują - jedna nadpisuje wynik drugiej

### a) procesor jednocyklowy
każda instrukcja wykonuje się dopiero po skończeniu poprzedniej, więc nie ma hazardów

### b) procesor potokowy z pojedynczym ALU
każada faza wykonuje się osobno, więc hazard WAW ani strukturalny nie zajdzie
procesor składa się z 5 faz, więc hazard WAR też nie zajdzie
zachodzą za to hazardy RAW

oraz sterowania

### c) procesor potokowy z wieloma jednostkami wykonawczymi (superscalar)
w tym procesorze mogą zajść wszystkie hazardy
RAW, WAR:

WAW:

add $t0, $t1, $t2
add $t0, $t3, $t4

sterowania analogicznie do jednego ALU

zakładając, że nie mamy współdzielonej pamięci instrukcji i pamięci danych hazard strukturalny nie zachodzi, w pp jest on analogiczny do WAW

> [name=Piotr Witkowski] Założenie: mamy procesor potokowy z jedną jednostką dla dodawania i jedną dla mnożenia. Mnożenie zajmuje 7 cykle, dodawanie 1 cykl.
> Hazard typu WAW:
> MUL t, a, b
> ADD t, c, d

> Hazard typu WAR:
> MUL c, d, e
> MUL x, t, y
> ADD t, p, q

## Zadanie 2
:::success
Autor: Mikołaj Karapka
:::
### Scoreboard
czarna skrzynka, dba o poprawne zarządzanie hazardami danych i o poprawne zlecanie instrukcji.

### Algorytm

1. ***Issue:***:
- Pobranie instrukcji i sprawdzenie czy nie występuje jeden z konfliktów **RAW**/**WAR**/**WAW**
3. ***Read operands:***
- Sprawdzenie czy nowa instrukcja jest dostępna i nie korzysta z **RAW**
5. ***Execution:***
- Wykonanie obliczeń.
6. ***Write result:***
- Sprawdzenie czy w potoku nie występuje **WAR**, jeśli tak, to czekanie aż przestaniemy mieć ten hazard dla instrukcji i zapisanie wyniku do rejestru.

### RAW - Read After Write
Przetrzymujemy wtedy instrukcje w **scoreboardzie** aż inna od niej zależna instrukcja się wykona.
### WAR - Write After Read
Wykonanie mogłoby spowodować błędne odczytanie z rejestru, dlatego przed zaktualizowaniem wyniku dana instrukcja czeka w **scoreboardzie** jako wykonana.

### WAW - Write After Write
Wykonanie mogłoby spowodować zagrożenie wynikające z nadpisania rejestru, żeby temu zapobiec instrukcja czeka przed wejściem do **scoreboardu** . Dodatkowo uniemożliwiamy wtedy na wejście innych instrukcji do **scoreboardu**.

### Czekanie

Przed Scoreboard           W Scoreboard
        |                  /           \
       WAW         Przed wykonaniem   Po wykonaniu 
                         |                 |
                        RAW               WAR

## Zadanie 3
:::success
Autor: Borys Adamiak
:::

### Koncept reorder buffera:
Wykonujemy instrukcje w wygodnej kolejnosci a na koniec je porządkujemy.
### Alg:
1) pobieramy instrukcje i dodajemy ja do kolejki
2) wykonujemy instrukcje rownolegle jesli mamy dostep do jej danych
3) Kiedy instrukcja z gory kolejki jest gotowa zapisujemy jej wynik do docelowego rejestru i popujemy z kolejki
### Jak algorytm radzi sobie z hazardami:
1) RAW (Read after write) - reorder buffer zapewnia nam że nie bedziemy dotykac danych przed ich zapisaniem
2) WAR - zasoby sprawdzamy przed rozpoczeciem obliczen wiec nie piszemy danych przed ich odczytem
3) WAW - kolejnosc instrukcji sie nie zmienia (dzieki kolejce)

### reorder buffer vs. scoreboard
Reorder buffer wykonuje wiele operacjina buforze aby monitorowac instrukcje. Scoreboard natomiast sprawdza zajete rejestry aby ich nie nadpisywac.
W reorder bufferze wyjatki sa sprawdzane na biezaco (nie zapiszemy bledu do rejestru gdyz najpierw zostanie policzony zanim bedzie wpisany). Scoreboard moze miec problem z wyjatkami przez nieterminowe wykonywanie instrukcji. ROB szybciej działa przez zrownoleglenie i lepiej radzi sobie z wyjatkami ale zuzywa wiecej zasobow.

## Zadanie 4
:::success
Autor: Katarzyna Trzos
:::

## Zadanie 5
:::success
Autor: Piotr Traczyński
:::

## Zadanie 6
:::success
Autor: Maciej Dengusiak


#### Działanie:
1. Zastąpimy plik rejestrów przez **Register Alias Table**.
2. Każda jednostka obliczeniowa będzie posiadać własną stację rezerwującą, w ten sposób zdecentralizujemy ROB.

#### Jak sobie radzi z hazardami:
- RAW: przetrzymujemy instrukcje w stacjach rezerwujacych dopóki argumenty się nie wyliczą więć RAW się nie pojawi

- WAR: nie zapiszemy wartości do rejestru przed odczytem, bo gdy instrukcja potrzebuje starej wartości to ma ją w:
- polu value w jednostce obliczeniowej (gdy argument został policzony)
- w tagu miejsce gdzie ta wartość stara się znajduje

- WAW: analogicznie do WAR

Technika register renaming służy do utrzymania dobrej kolejności obliczeń - eliminuje hazardy WAR i WAW (trzymamy stare, właściwe wartości w polu value lub pod kluczem Tag)

#### Porównanie wydajności:
Zyskujemy wydajność dzięki zrównolegleniu operacji które wykonywał reorder-buffer. Dzięki takiemu podejściu każda jednostka samodzielnie trzyma co potrzebuje a nie odwołuje się do jednego zasobu.