# Ćwiczenia 7, grupa cz. 14-16, 21. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | |
Mateusz Burdyna | | | | | | |
Dariusz Ciesielski | | | | | | |
Dawid Dudek | X | X | X | X | X | |
Mikołaj Dworszczak | | | | | | |
Przemysław Grochal | X | X | X | X | X | |
Adam Jarząbek | X | ==X== | X | X | | |
Anna Karykowska | X | X | | X | | |
Oleś Kulczewicz | | | | | | |
Pola Marciniak | X | X | X | X | X | ==X== |
Mikołaj Mroziuk | | | | | | |
Marcelina Oset | | | | | | |
Natalia Piasta | | | | | | |
Krzysztof Piekarczyk | X | ==X== | | X | X | |
Marcin Płaza | X | X | X | X | | |
Paweł Richert | X | X | | X | X | |
Rafał Starypan | X | X | | X | X | |
Dawid Strojek | X | X | X | | | |
Mateusz Suszek | X | X | X | ==X== | X | X |
Wojciech Śniady | X | X | X | | | |
Volha Tsekalo | X | X | X | | | |
Yana Vashkevich | | X | | | | |
Konrad Woźniak | | X | | | | |
Natalia Czerep | | | | | | |
Joanna Stachowicz | | X | | | | |
:::

**Tutaj można do-deklarować zad. 9. z listy 6:**
*
* Anna Karykowska
*

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

## Zadanie 1
:::success
Autor: Wojciech Śniady
:::

instrukcje a i b (a jest przed b w programie)
RAW (ang. read after write) - b próbuje odczytać rejestr zanim a go skończy modyfikować
WAW (ang. write after write) - b próbuje nadpisać rejestr zanim a go skończy modyfikować
WAR (ang. write after read) - b próbuje nadpisać zmienną zanim zostaje ona przeczytana przez a

data hazard - jeszcze nie została zapisana nowa wartość, a już jest ta zmienna używana
control hazard - występuje branch misprediction, wykonujemy na darmo instrukcje, które nie powinny być wykonane, bo warunek został źle przewidziany

a) procesor jednocyklowy:
nie ma hazardów, bo instrukcje są wykonywane, dopiero po zakończeniu poprzednich
b) procesor potokowy z pojedynczym ALU:
-data hazard
-control hazard

c) procesor potokowy z wielomana jednostkami wykonawczymi:
-WAR
-RAW
-WAW
-hazard sterowania

Przykład hazardu typu WAR w punkcie c):

s2 = s7 / s8 <- ta instrukcja wykonuje się bardzo długo (dzielenie trwa wiele cykli). Instrukcja wykonuje się na jednostce wykonawczej.
s0 = s1 + s2 <- ta instrukcja nie wykona się, bo argument s2 jest jeszcze niepoliczony. Instrukcja przebywa w buforze.
s1 = s4 + s5 <- ta instrukcja wykonała się szybko, bo s4 i s5 są już policzone

Ostatnia instrukcja zapisała rejestr s1 wcześniej niż odczytała go instrukcja druga.

## Zadanie 2
:::success
Autor: Adam Jarząbek
:::
Przetwarzanie potokowe z wykorzystaniem scoreboardingu jest podzielone na etapy:
* Issue - instrukcja zostaje zlecona do wykonania
* Read operands - czytanie argumentów
* Execution - wykonanie operacji (arytmetycznej, logicznej, ...)
* Write result - wdrożenie wyniku

Algorytm scoreboarding radzi sobie z hazardami w następujący sposób:

**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: Marcin Płaza
:::


Do jednostki reorder buffer wstawiane są instrukcje w porządku takim, w jakim występują w programie, które będą wykonywać się równolegle (out-of-order) w różnym czasie, a wyniki ich działań buforowane będą w odpowiedniej kolejności - w kolejności dodania ich do reorder buffera.
Algorytm wypisuje dane w kolejności ich wykonywania i czeka na wykonanie się odpowiednich poleceń, zanim wykona kolejne, które korzystają z nieobliczonych rejestrów, więc nie jesteśmy narażeni na hazardy RAW, WAR i WAW. W metodzie używającej reorder buffera nie wstrzymujemy całego potoku zadań ustawionych w kolejności (tak jak to miało miejsce przy scoreboardingu), tylko konkretną instrukcję zależną od wykonującej się. W tym czasie wykonują się out-of-order pozostałe instrukcje niezależne. Reorder buffer jest więc szybszy, bo w czasie wstrzymania instrukcji mogą wykonywać się inne instrukcje.

## Zadanie 4
:::success
Autor: Mateusz Suszek
:::


## Zadanie 5
:::success
Autor: Dawid Dudek
:::

:::spoiler wersja z 21.04

a) 30 cykli


b) 27 cykli


c)19 cykli
:::

**Wersja poprawiona:**

### Procesor potokowy

|operacja------|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|32|33|34|35|36|37|
|--------------|-|-|-|-|-|-|-|-|-|- |- |- |- | -| -| -|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r3 = r1 * r2 |F|D|E|E|E|E|E|E|W|- |- |- |- | -| -| -|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r5 = r4 + r3 | |F|D|D|D|D|D|D|D|E |E |E |E |E | E| W|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r7 = r2 + r6 | | |F|F|F|F|F|F|F|D |E |E |E |E |E | E| W|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|r10 = r8 + r9 | | | | | | | | | |F |D |E |E |E |E |E | E|W |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|r11 = r7 + r10| | | | | | | | | | |F |D |D |D |D |D | D|D |E |E |E |E |E |E |E |W |- |- |- |- |- |- |- |- |- |- |- |- |
|r5 = r5 + r11| | | | | | | | | | | |F |F |F |F |F | F|F |D |D |D |D |D |D |D |D |E |E |E |E |E |E |W |- |- |- |- |- |

### Scoreboard

|operacja------|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|32|33|34|35|36|37|
|--------------|-|-|-|-|-|-|-|-|-|- |- |- |- | -| -| -|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r3 = r1 * r2 |F|D|E|E|E|E|E|E|W|- |- |- |- | -| -| -|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r5 = r4 + r3 | |F|S|S|S|S|S|S|D|E |E |E |E |W | | |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r7 = r2 + r6 | | |F|D|S|S|S|S|S|S |S |S |S |E |E | E| E|W | |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|r10 = r8 + r9 | | | |F|D|S|S|S|S|S |S |S |S |S |S |S | S|E |E |E |E |W |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|r11 = r7 * r10| | | | |F|D|S|S|S| S|S |S | S|S |S |S | S|S |S |S |S |S |E |E |E |E |E |E |W | |- |- |- |- |- |- |- |- |
|r5 = r5 + r11| | | | | |F|D|D|D| D|D |D | D|D |S |S | S|S |S |S |S |S |S |S |S |S |S |S |S |E |E |E |E |W | |- |- |- |

### reorder buffer

|operacja------|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|32|33|34|35|36|37|
|--------------|-|-|-|-|-|-|-|-|-|- |- |- |- | -| -| -|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r3 = r1 * r2 |F|D|E|E|E|E|E|E|R|W |- |- |- | -| -| -|- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -|
|r5 = r4 + r3 | |F|D|R|R|R|R|R|E|E |E |E |R |W | |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- | -| -|
|r7 = r2 + r6 | | |F|D|E|E|E|E|R|R |R |R |R |R |W | | | | |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|r10 = r8 + r9 | | | |F|D|R|R|R|R|R |R |R |E |E |E |E |R |W | | | | | |- |- |- |- |- |- |- |- |- |- |- |- |- |- |- |
|r11 = r7 * r10| | | | |F|D|R|R|R|R |R |R |R |R |R |R |E |E |E |E | E|E |R |W | | | | | | |- |- |- |- |- |- |- |- |
|r5 = r5 + r11| | | | | |F|D|R|R|R |R |R |R |R |R |R |R |R |R |R |R |R |E |E |E |E |R |W | | | | | | | |- |- |- |

## Zadanie 6
:::success
Autor: Pola Marciniak
:::

Stacje rezerwacyjne w trakcie wykonywania się programu. Część wykonujących się instrukcji nie korzysta z obliczonych rejestrów, tylko z tagów.
Instrukcja 2 czeka na wykonanie się mnożenia z instrukcji 1, ale nie zatrzymuje instukcji niezależnych, następujących po niej.