# Ćwiczenia 8, grupa cz. 16-18, 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- |
Marcin Banak | X | X | X | ==X== | X | X |
Bartosz Borecki | | X | X | | |==X== |
Karol Burczyk | X | X | X | X | X | |
Yelyzaveta Ilman | X | X | X | X | X | X |
Antoni Kamiński | X | X | | X | | |
Jan Kamyk | X | X | X | | | |
Bartosz Kruszewski | X | X | X | X | ==X== | X |
Hanna Laszkiewicz | X | X | X | X | X | X |
Kaja Matuszewska | | | | | | |
Dominik Muc | | | | | | |
Krzysztof Ostrowski | ==X== | X | | X | X | X |
Franciszek Przeliorz | X | ==X== | X | X | X | X |
Yaryna Rachkevych | X | X | | | | |
Mikołaj Kalitka | X | X | X | X | X | X |
Piotr Thamm | X | X | X | | | |
Taras Tsehenko | X | X | X | X | X | X |
Wiktor Małek | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Krzysztof Ostrowski
:::

### Rodzaje hazardów:

#### Sterowania
> Występuje w instrukcjach skoku, gdy warunek skoku nie zostaje wyliczony przed jego wykorzystaniem.

#### Strukturalny
> Występuje gdy zasobow procesora nie starcza na wykonanie danych operacji tego samego typu w jednym momencie.

#### RAW (read after write)
> Występuje gdy wartość zmiennej zostaje wczytana przed jej poprawnym wyliczeniem.

#### WAR
> Wystepuje gdy wartość zmiennej zostaje nadpisana przed jej wykorzystaniem.

#### WAW
> Wystepuje gdy wartość zmiennej zostaje nadpisana przed jej wykorzystaniem.

### Wystepowanie w procesorach

#### a) Procesor jednocyklowy

> wszystkie operacje są wykonywane hronologicznie jedna po drugiej, więc hazardy **nie występują**

#### b) Procesor potokowy z pojedynczym ALU
> - [ ] **strukturalny** - fazy ustawione są tak, że operacje tego smaego typu nie zachodzą w tym samym momencie
> - [x] **sterowania** - na przykładzie b.1
> - [x] **RAW** - na przykładzie b.2
> - [ ] **WAR** - fazy ustawione są tak, że operacje tego smaego typu nie zachodzą w tym samym momencie
> - [ ] **WAW** - fazy ustawione są tak, że operacje tego smaego typu nie zachodzą w tym samym momencie

b.1)

b.2)

#### c) Procesor potokowy z wieloma jednostkami wykonawczymi

> - [x] **strukturalny** - na przykładzie c.3
> - [x] **sterowania** - na przykładzie b.1
> - [x] **RAW** - na przykładzie c.2
> - [x] **WAR** - na przykładzie c.2
> - [x] **WAW** - na przykładzie c.3

c.2)

c.3)

a = b + c
a?
a = d + e

Założenie: procesor ma jednostkę wykonawczą dodawania (1 cykl) i jednostkę wyk. mnożenia(7 cykli), ale nie ma jednostki wykrywania hazardów. Przykład hazrdu
> WAW:
> mul t, a, b
> add t, a, b

> WAR:
> mul a, b, c
> mul z, t, c
> add t, q, r

## Zadanie 2
:::success
Autor: Franciszek Przeliorz

## Scoreboard:

Komponent procesora, który na bieżąco przechowuje listę zadań do wykonania oraz sprawdza, które jednostki funkcjonalne są dostępne. Wykorzystuje algorytm który pozwala na poprawne zarządzanie hazardami i zlecanie instrukcji.

## Algorytm

Algorytm wykorzystuje buforowanie instrukcji oraz sprawdzanie zależności między nimi. Manipuluje czasem wykonania, aby zapewnić, że instrukcje wykonywane są w odpowiedniej kolejności, co pozwala uniknąć hazardów danych.

#### Przebieg algorytmu:

* ##### Wydawanie instrukcji **(issue)**:
Procesor pobiera kolejne instrukcje do wykonania. Przed wykonaniem instrukcji sprawdzane jest, czy żadna poprzednia instrukcja nie zapisuje danych w tym samym miejscu -> uniknięcie **WAW**

* ##### Odczytywanie operandów **(read operands)**:
Sprawdzane jest, czy nowa instrukcja nie korzysta z tych samych danych, które są używane przez inne instrukcje, aby uniknąć sytuacji, w której instrukcja używa nieaktualnych lub nieprawidłowych danych -> uniknięcie **RAW**.

* ##### Wykonanie **(execution)**

* ##### Zapis wyniku **(write result)**:
Jeśli wszystkie inne instrukcje, które wpływają na te same dane, zostały już wykonane, to wynik bieżącej instrukcji jest zapisywany. Zapobiega to sytuacji, w której inne instrukcje próbują odczytać nieaktualne dane -> uniknięcie **WAR**

:::

## Zadanie 3
:::success
Autor: Jan Kamyk
:::



#### Rozwiązania hazardów

**RAW**: zapisujemy instrukcje w oryginalnej kolejności
**WAR**: instrukcje mają sprawdzaną dostępność zasobów przed rozpoczęciem obliczania
**WAW**: zapisujemy instrukcje w oryginalnej kolejności


## Zadanie 4
:::success
Autor: Marcin Banak

#### Program


#### Procesor potokowy z pojedynczym ALU

F D E E E E E E W
  F D _ _ _ _ _ D E E E E E E W     <- stalling aby zaczekać na r3
    F F F F F F F D E E E E E E W
                  F D E E E E E E W
                    F D _ _ _ _ _ D E E E E E E W     <- stalling aby zaczekać na r7
                      F F F F F F F D E E E E E E W    <- stalling aby zaczekać na r5

Liczba cykli: $26$

#### Procesor potokowy z w pełni potokowymi niezależnymi jednostkami

F D E E E E E E W
  F D _ _ _ _ _ D E E E E W      <- stalling aby zaczekać na r3, krócej bo dodawanie w 4 cyklach
    F D E E E E W                <- hazard strukturalny ponieważ write w 2 miejsach 
      F D E E E E E E W
        F D _ _ _ _ _ D E E E E W     <- stalling aby zaczekać na r7
          F D _ _ _ _ _ _ D E E E E E E W    <- stalling aby zaczekać na r5, krócej o 2 cykle bo trzeba krócej czekać na zapis operacji 2

Liczba cykli: $21$

Faza W kolejnych instrukcji nie zachowuje kolejności programu.

#### Procesor jak wyżej, ale używający reorder buffera

F D E E E E E E R W
  F D _ _ _ _ _ E E E E R W     <- obliczamy szybciej w buforze
    F D E E E E R           W      <- obliczamy szybciej w buforze, ale zapisujemy później
      F D E E E E E E R       W
        F D _ _ _ _ _ E E E E R W     <- Wykonuje się szybciej bo nie musi czekać na zapisanie r7 tylko bierze jego wartość z buforu
          F D _ _ _ _ _ E E E E E E R W    <- Bierze wartość r5 z buforu i nie czeka na jego zapisanie do pamięci

Liczba cykli: $20$

Faza W kolejnych instrukcji zachowuje kolejność programu.
Jest trochę szybciej bo pomijamy czekanie na zapis do rejestru, ale kosztem operacji na buforze.

:::

## Zadanie 5
:::success
Autor: Bartosz Kruszewski
:::

#### Program

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

#### Procesor a

Liczba cykli: $38$

FD123456W
 FD.....D123456W
        FD123456W
         FD123456W
          FD.....D123456W
                 FD.....D123456W

#### Procesor b

Liczba cykli: $25$

FD123456W
 FD.........1234W
  FD1234W
   FD...1234W
    FD......D123456W
     FD............D1234W

#### Procesor c

Liczba cykli: $28$

FD123456RW
 FD.....1234RW
  FD1234R     W
   FD.......1234RW
    FD..........123456RW
     FD...............1234RW

## Zadanie 6
:::success
Autor: Bartosz Borecki
:::