---
# System prepended metadata

title: 'Ćwiczenia 8, grupa śr. 14-16, 17 kwietnia 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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	
:::

![image](https://hackmd.io/_uploads/rktByHTlA.png)


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**
![image](https://hackmd.io/_uploads/B1sa1H6lR.png)


> [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.*



![Screenshot 2024-04-16 at 19.42.49](https://hackmd.io/_uploads/SkosuV2g0.png)



## 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
:::
![436419249_3696666273945543_6753635931818536303_n](https://hackmd.io/_uploads/rJsf1rax0.png)


## Zadanie 5
:::success
Autor: 	Leon Lepkowski	
:::
![image](https://hackmd.io/_uploads/BytIBc2lR.png)

#### a)
![image](https://hackmd.io/_uploads/ryhfdq2eC.png)


#### b)
![image](https://hackmd.io/_uploads/HJ3KoqhxA.png)


#### c)
![image](https://hackmd.io/_uploads/H13xT93gR.png)

## Zadanie 6
:::success
Autor: Michał Włodarczak
:::
![Tresc6](https://hackmd.io/_uploads/S1I5Fd8-C.png)

![Do 6 a](https://hackmd.io/_uploads/HkvjK_8WA.png)

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ą

![Do 6 b](https://hackmd.io/_uploads/HJE0YuI-R.png)

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.