---
# System prepended metadata

title: 'Ćwiczenia 8, grupa cz. 16-18, 18 kwietnia 2024'
tags: [pwit, ćwiczenia, SYK24]

---

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

    
#### WAR
> Wystepuje gdy wartość zmiennej zostaje nadpisana przed jej wykorzystaniem.
![image](https://hackmd.io/_uploads/HyeNmoRx0.png)


#### WAW 
> Wystepuje gdy wartość zmiennej zostaje nadpisana przed jej wykorzystaniem.
![image](https://hackmd.io/_uploads/B1uEmiCeR.png)

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

b.2)
![image](https://hackmd.io/_uploads/H1EqudTxA.png)

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

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	
:::
![z8_treść](https://hackmd.io/_uploads/S1zppsCeA.png)

![Z8](https://hackmd.io/_uploads/rkt7b2Cl0.png)


![Z8_1](https://hackmd.io/_uploads/BJ7vpoAg0.png)

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

![z8 tradeoffs](https://hackmd.io/_uploads/HyR-PnCl0.png)



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

#### Program 

![syk program](https://hackmd.io/_uploads/HJOK2iRgA.png)

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