# Ćwiczenia 7, grupa śr. 17-19, 27. kwietnia 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | |
Kamila Brzozowska | X | X | X | X | X | X |
Adam Ciężkowski | X | ==X== | X | X | X | X |
Natalia Czerep | ==X== | X | X | X | X | X |
Jan Dalecki | X | X | X | X | X | ==X== |
Marko Golovko | X | X | X |==X==| X | X |
Adam Górkiewicz | X | X | X | X | X | X |
Piotr Gunia | X | X | X | X | X | |
Krzysztof Jadłowski | X | X | X | X | | X |
Magdalena Jarecka | | X | | | | |
Mikołaj Jaszcza | X | X | X | X | X | |
Monika Jędrzejkowska | | | | | | |
Michał Kierul | | | | | | |
Damian Lukas | | | | | | |
Karol Ochman-Milarski | | | | | | |
Piotr Piesiak | | | | | | |
Damian Ratajski | | | | | | |
Aleksandra Rozkrut | | | | | | |
Marcin Sarnecki | X | X | X | X | X | |
Maria Szlasa | X | X | X | X | | |
Mateusz Burdyna | X | X | X | | | |
Magdalena Słonińska | X | X | X | | | |
Nikola Wrona | X | X | X | X | X | |
Marcin Wróbel | X | X | X | X | X | X |
:::

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

## Zadanie 1
:::success
Autor: Natalia Czerep
:::

hazardy - problemy z potokiem instrukcji w mikroarchitekturach procesora, gdy następna instrukcja nie może zostać wykonana w kolejnym cyklu zegara i może to potencjalnie prowadzić do błędnych wyników obliczeń.

hazard sterowania - występuje gdy błędnie próbujemy przewidywać skoki

hazard strukturalny - występuje, gdy dwie (lub więcej) instrukcje, które są już w potoku, wymagają tego samego zasobu.

hazard danych - występuje, gdy instrukcje modyfikują dane, od których są zależne, na różnych etapach potoku.

RAW - Read after write - instrukcja odnosi się do wyniku drugiej, który nie został jeszcze obliczony lub zapisany


forwarding:
F D EX MEM WB      R2 = R5 + R3
     -|
      |-|  
  F D   EX  MEM WB  R4 = R2 + R3
  

A co się dzieje, gdy jest hazard typu RAW i jedna z instrukcji jest instr. dostępu do pamięci?

forwarding + stalling:
F D EX MEM WB       R2 = *R5
        -|
         |-|
  F D  D   EX  MEM WB   R4 = R2 + R3

WAR - jedna instr próbuje zapisać coś do rejestru, zanim zostanie on odczytane przez poprzednią


WAW - jedna inst próbuje zapisać coś do rejestru/zmiennej, zanim zostanie do nej zapisana wartość z poprzedniej instr


procesor jednocyklowy - nie występują - 1 cykl 1 instr

procesowe potokowy z pojedynczym ALU - RAW, bo jedyne co można zrobić równolegle to coś wczytać

procesor potokowy z wieloma jedn. wyk. - wszystkie typy

## Zadanie 2
:::success
Autor: Adam Ciężkowski
:::


Etapy:
* Issue - sprawdzenie, czy nie ma hazardu WAW
* Read operands - sprawdzenie, czy argumenty są dostępne (RAW) i odczytanie ich (jeśli są)
* Execution - wykonanie operacji, zapis do scoreboard'u kiedy rejestr będzie dostępny (zakończy wykonywanie operacji)
* Write Result - sprawdzenie, czy wystąpi WAR, jeśli nie, to zapis do rejestru

Jak sobie radzi z hazardami?
* RAW - stall póki argumenty nie są dostępne (w fazie Read operands)
* WAR - stall w fazie Write Result, jeśli jakaś wcześniejsza instrukcja potrzebuje poprzedniej wartości rejestru, a nie zdążyła go odczytać
* WAW - stall póki wykonujemy wcześniejszą instrukcję, która nadpisuje ten sam rejestr (w fazie Issue)

## Zadanie 3
:::success
Autor: Mikołaj Jaszcza
:::

Analizowany przez nas sposób przetwarzania programu jest "out-of-order", kolejność rozpoczęcia i zakończenia instrukcji jest zgodna z kolejnością w programie. Jednakże w trakcie wykonywania instrukcji - wyniki nie będą wyliczane w tej samej kolejności - zostaną skolejkowane i wdrożone we właściwy sposób. Korzystamy z kolejki FIFO.

Przetwarzanie potokowe przy uzyciu reorder buffera:

Pomysł polega na buforowaniu wyników działania instrukcji w kolejce. W register file trzymamy dodatkowy bit informujący o tym, czy dana wartość jest aktualna, oraz adres w ROB. Jeśli okaże się, że nie jest ona aktualna, patrzymy pod odpowiedni adres w ROB i jeśli tam dana wartość została już zapisana, to możemy z niej skorzystać. Jeśli w głowie kolejki znajdują się już poprawnie zapisane wartości, to wysyłamy je do RF i kolejka ROB przesuwa się do przodu (uprzednio aktualizując rejestry).


Zauważmy, że wynik operacji możemy odczytać z ROB zamiast z rejestru - pozwala to na forwarding.

// PRZYKŁAD DLA 3 INSTRUKCJI
1 -> 2 RAW
2 -> 3 WAR

x = y / z (1)
a = 3 * x (2)
x = t + 7 (3)
b = x + 5

Hazardy WAW i WAR nie występują.
WAW - nie występuje, ponieważ z kolejki (ROB) ściągam elementy w takiej samej kolejności, w jakiej były dołożone (tożsame z kolejnością instrukcji w programie).

WAR - nie występuje - algorytm nie zamieni kolejnością dwóch instrukcji które są w zależności WAR

Hazard RAW nadal występuje, wtedy algorytm czeka aż odpowiednia wartość zostanie zapisana do ROB (zgodnie z opisem algorytmu działania opisanym wyżej)

Wydajność reorder buffera jest lepsza niż scoreboardingu, przyspieszenie wynika z tego że wartość może zostać odczytana z ROB, a w scoreboardingu trzeba by uzyć stallingu.


## Zadanie 4
:::success
Autor: Marko Golovko
:::

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

a) procesorze potokowym z pojedynczym ALU. To ALU samo jest
w pełni potokowe i działa w 6 cyklach. 26 cykli

b) procesorze potokowym z w pełni potokowymi niezależnymi
jednostkami (po jednej sztuce) dla mnożenia (6 cykli) i
dodawania (4 cykle). **Procesor używa scoreboardu**

c) procesorze potokowym jak wyżej, ale używającym reorder
buffera. 20 cykli


## Zadanie 5
:::success
Autor: Marcin Wróbel
:::
Powtórz powyższe zadanie dla programu
r3 = r1 * r2
r5 = r4 + r3
r7 = r2 + r6
r10 = r8 + r9
r11 = r7 * r10
r5 = r5 + r11
a)
| cykl | |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|
| ------------- | - |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|$r3 = r1 * r2$ | |F |D |E1|E2|E3|E4|E5|E6|W | | | | | | | | | | | | | | | | | | | | | | | |
|$r5 = r4 + r3$ | | |F |D |D |D |D |D |D |D |E1|E2|E3|E4|E5|E6|W | | | | | | | | | | | | | | | | |
|$r7 = r2 + r6$ | | | |F |F |F |F |F |F |F |D |E1|E2|E3|E4|E5|E6|W | | | | | | | | | | | | | | | |
|$r10 = r8 + r9$ | | | | | | | | | | |F |D |E1|E2|E3|E4|E5|E6|W | | | | | | | | | | | | | | |
|$r11 = r7 * r10$| | | | | | | | | | | |F |D |D |D |D |D |D |D |E1|E2|E3|E4|E5|E6|W | | | | | | | |
|$r5 = r5 + r11$ | | | | | | | | | | | | |F |F |F |F |F |F |F |D |D |D |D |D |D |D |E1|E2|E3|E4|E5|E6|W |

32 cykle

W punktach b) i c) załóż tym razem, że jednostki wykonawcze
dla dodawania i mnożenia nie są potokowe, tzn. ich czas
działania wynosi, jak poprzednio 4 i 6 cykli, ale można zlecić
wykonanie kolejnej operacji danego typu, dopiero po
zakończeniu poprzedniej.

b)
| cykl | |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|
| ------------- | - |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|$r3 = r1 * r2$ | |F |D |E1|E2|E3|E4|E5|E6|W | | | | | | | | | | | | | | | | | | | | | | | | | |
|$r5 = r4 + r3$ | | |F |D |S |S |S |S |S |S |E1|E2|E3|E4|W | | | | | | | | | | | | | | | | | | | | |
|$r7 = r2 + r6$ | | | |F |D |E1|E2|E3|E4|W | | | | | | | | | | | | | | | | | | | | | | | | | |
|$r10 = r8 + r9$ | | | | |F |D |S |S |S |S |S |S |S |S |E1|E2|E3|E4|W | | | | | | | | | | | | | | | | |
|$r11 = r7 * r10$| | | | | |F |D |S |S |S |S |S |S |S |S |S |S |S |S |E1|E2|E3|E4|E5|E6|W | | | | | | | | | |
|$r5 = r5 + r11$ | | | | | | |F |D |S |S |S |S |S |S |S |S |S |S |S |S |S |S |S |S |S |S |E1|E2|E3|E4|W | | | | |

30 cykli

c)
| cykl | |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|
| ------------- | - |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|$r3 = r1 * r2$ | |F |D |E1|E2|E3|E4|E5|E6|R |W | | | | | | | | | | | | | | | | | | |
|$r5 = r4 + r3$ | | |F |D |D |D |D |D |D |E1|E2|E3|E4|R |W | | | | | | | | | | | | | | |
|$r7 = r2 + r6$ | | | |F |D |E1|E2|E3|E4|R | | | | | |W | | | | | | | | | | | | | |
|$r10 = r8 + r9$ | | | | |F |D |D |D |D |D |D |D |D |E1|E2|E3|E4|R |W | | | | | | | | | | |
|$r11 = r7 * r10$| | | | | |F |D |D |D |D |D |D |D |D |D |D |D |E1|E2|E3|E4|E5|E6|R |W | | | | |
|$r5 = r5 + r11$ | | | | | | |F |D |D |D |D |D |D |D |D |D |D |D |D |D |D |D |D |E1|E2|E3|E4|R |W |

28 cykli

## Zadanie 6
:::success
Autor: Jan Dalecki
:::

Algorytm Tomasulo pozwala na wykonywanie operacji poza kolejnością.

### Problemy z zatrzymaniem potoku:


Przykład pierwszego kodu pokazuje, że ponieważ 2 instrukcja zapisuje i odczytuje do tego samego rejestru co pierwsza to musi nastąpić wstrzymanie potoku. Pierwsza instrukcja IMUL zajmuje rejestr R3, więc kolejna czeka aż się ona zakończy. Z tego powodu kolejne instrukcje które są niezależne od 2 pierwszych również zostają wstrzymane.

Rozwiązaniem jest zbuforowanie instrukcji oczekujących, a następnie wykonanie kolejnych niezależnych instrukcji.

### Struktury danych:

#### Plik rejestrów w formie tabeli:


Znaczenia poszczególnych kolumn:
1) Nazwa rejestru
2) Flaga valid odpowiadająca na pytanie czy w danym momencie wartość zapisana w tym rejestrze jest prawidłowa (czy może dopiero obliczana).
3) Tag - Adres który odnosi się do wiersza tablicy RS gdzie obliczana jest wartość rejestru.
4) Value - wartość rejestru (może być nieaktualna).

#### Tablice RS (reservation station):


1) Tag, który identyfikuje wiersz w tabeli
2) V - flaga valid
3) Tag - Odniesienie do innego wiersza w którym przechowywany jest odpowiedni argument
4) Value - wartość argumentu

### Ogólne działanie algorytmu:

W każdym cyklu następuje faza Fetch dla kolejnej instrukcji w programie.

Sprawdzane są rejestry które zostały podane jako argumenty oraz rejestr docelowy.

#### Dany argument jest dostępny

W przypadku gdy widnieje jako valid dany argument w Reg File to pobieramy bezpośrednio jego wartość do tablicy RS dla danej operacji tablicy RS.

#### Rejestr docelowy jest dostępny

W przypadku gdy rejestr do zapisu jest dostępny - wpisujemy go do pierwszego dostępnego wiersza w tablicy RS oraz aktualizujemy Reg File odpowiednio ustawiając V rejestru na 0 oraz dodając odniesienie do wpisu w RS.

#### Argument jest niedostępny

Jeżeli w pliku rejestrów argument jest niedostępny to sprawdzamy do jakiego wpisu w RS się on odnosi.

#### Rejestr docelowy jest niedostępny

Aktualizujemy tag w Reg file nowym wpisem do RS

#### Wykonanie obliczenia

Gdy zakończone zostanie obliczenie w jednostce funkcyjnej aktualizujemy reg file z odpowiednim tagiem oraz rozprowadzamy wynik w RS do tagów, które czekały na obliczenie danego rejestru.