---
# System prepended metadata

title: 'Ćwiczenia 8, grupa cz. 14-16, 27 kwietnia 2023'
tags: [pwit, ćwiczenia, SYK23]

---

# Ćwiczenia 8, grupa cz. 14-16, 27 kwietnia 2023

###### tags: `SYK23` `ć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   | 7?  | 8?  | 9?  |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki         |       |     |     |     |     |     |     |     |     |
Wojciech Bogucki         |   X   |  X  |  X  |==X==|  X  |  X  |     |     |     |
Mateusz Cerulewicz       |   X   |  X  |  X  |  X  |     |     |     |     |     |
Mateusz Garncarczyk      |   ==X==   |  X  |  X  |  X  |     |     |     |     |     |
Mateusz Golisz           |       |     |     |     |     |     |     |     |     |
Mateusz Kitzol           |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Piotr Mańkowski          |       |     |     |     |     |     |     |     |     |
Michał Mękarski          |       |     |     |     |     |     |     |     |     |
Aleksandra Nicpoń        |   X    |  X   |  X   |  X   | X    |     |     |     |     |
Ksawery Plis             |     X  |  ==X== |  X  | X |    |     |     |     |     |     |     |
Patryk Rybak             |   X    |   X  |     |  X   |     |  X   |     |     |     |
Rafał Spyra              |   X    |  X   |  X   |     |     |  X   |     |     |     |
Dominik Szczepaniak      |   X    | X    |  X   |   X  |   X  |     |     |     |     |
Taras Tsehenko           |       |     |     |     |     |     |     |     |     |
Maksymilian Wiśniewski   |       |     |     |     |     |     |     |     |     |
Martyna Wybraniec        |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Natalia Zychowicz        |   X   |  X  |     |     |     |   X |     |     |     |
Patryk Maciąg            |       |  X   |  X   |     |     |     |     |     |     |
:::






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



## Zadanie 1
:::success
Autor: Mateusz Garncarczyk	
:::
![](https://i.imgur.com/f8mrPpF.png)

### Hazard sterowania (Control Hazard):
Sytuacja, w której procesor dostaje instrukcję skoku warunkowego. Aż do 4 fazy cyklu wykonywania instrukcji nie wiadomo, czy skok będzie należało wykonać czy też nie.

### Hazard strukturalny (Structural hazard):
Sytuacja, w której kilka instrukcji chce w tym samym momencie skorzystać z tego samego zasobu.

### RAW, WAR, WAW (Data hazard):
![](https://i.imgur.com/OkN4hmK.png)

**a) Procesor jednocyklowy:** 
Nie ma żadnego hazardu, ponieważ każda instrukcja wykonuje się dopiero po skończeniu poprzedniej.
![](https://i.imgur.com/xIX0uyU.png)

**b) Potokowy z pojedynczym ALU:**
    sterowania - może być
    ![](https://i.imgur.com/4ohC0AQ.png)
    strukturalny - nie może być
    RAW - może być
    ![](https://i.imgur.com/9cQTKgS.png)
    WAR, WAW - nie może być
    
**c) Potokowy z wieloma jednostkami wykonawczymi:**
    sterowania - może być 
    strukturalny - nie może być
    RAW, WAR, WAW - może być
    ![](https://i.imgur.com/bpvcGAK.png)
    
Hazard WAR:
```
   t1 = t0 + s1
   t0 = s2 - s3
```
Hazard WAW:
```
   t1 = t0 + s1
   t2 = t0 + s2
   t1 = s2 - s3
```
Hazard strukturalny:
```
   t1 = t0 + s1
   t1 = s2 * s3
```

## Zadanie 2
:::success
Autor: Ksawery Plis	
:::
![](https://i.imgur.com/JSLI2Sl.png)

**Przetwarzanie potokowe z wykorzystaniem scoreboardingu jest podzielone na następujące etapy:**
1. Issue - instrukcja zostaje zlecona do wykonania
2. Read operands - czytanie argumentów
3. Execution - wykonanie operacji (arytmetycznej, logicznej, ...)
4. Write result - wdrożenie wyniku

**Jak algorytm radzi sobie z hazardami:**

* **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: Martyna Wybraniec	
:::

![](https://i.imgur.com/uCd3sfR.png)


Algorytm przetwarzania potokowego przy użyciu reorder buffera:

* pozwala na uruchamianie niezależnych instrukcji podczas stallingu
* instrukcje mogą obliczać się poza kolejnością (rozpoczęcie i zakończenie pozostaje w oryginalnej kolejności)
* obliczone wartości przechowywane są w Reorder Buffer Entry i są dostępne dla kolejnych instrukcji
* ostatecznie wartości są zapisywane do pamięci w oryginalnej kolejności 

Jak algorytm radzi sobie z hazardami RAW, WAR, WAW?

Algorytm nie pozwala na hazardy RAW, WAR, WAW, ponieważ każda instrukcja zapisuje do Reorder Buffer Entry obliczoną wartość, z której przyszłe instrukcje mogą odpowiednio korzystać, natomiast do pamięci zawsze zapisuje wartości w prawidłowej kolejności. W przypadku RAW algorytm czeka, aż potrzebna wartość zostanie obliczona przed odczytaniem.

## Zadanie 4
:::success
Autor: Wojciech Bogucki	
:::
:::info
Zadanie 4. Dany jest program
```=
r3 = r1 * r2
r5 = r4 + r3
r6 = r4 + r1
r7 = r8 * r9
r4 = r3 + r7
r10 = r5 * r6
```
Podaj diagram wykonania i wylicz liczbę cykli zużytych przez ten program uruchomiony na następujących procesorach
1. procesorze potokowym z pojedynczym ALU. To ALU samo jest w pełni potokowe i działa w 6 cyklach. Każda instrukcja wykonuje się więc w fazach$^2$ F D E1 E2 E3 E4 E5 E6 WB.
1. procesorze potokowym z w pełni potokowymi niezależnymi jednostkami (po jednej sztuce) dla mnożenia (6 cykli) i dodawania (4 cykle). Instrukcja mnożenia wykonuje się więc w fazach F D E1 E2 E3 E4 E5 E6 WB, a dodawania w fazach F D E1 E2 E3 E4 WB. Procesor używa scoreboardu.
1. procesorze potokowym jak wyżej, ale używającym reorder buffera.

Jedynie procesor z punktu c) może używać forwardingu danych.
Możesz zignorować ewentualne hazardy strukturalne, ale
zaobserwuj fazy procesora, w którym mogą one wystąpić.

$^2$ Dla uproszczenia nie ma fazy MEM.
:::

1) procesor potokowym z pojedynczym ALU
Ignorujemy hazard struktularnych
```=
r3 = r1 * r2  F D E1 E2 E3 E4 E5 E6 WB
r5 = r4 + r3    F D  D  D  D  D  D  D E1 E2 E3 E4 E5 E6 WB 
r6 = r4 + r1                        F D  E1 E2 E3 E4 E5 E6 WB
r7 = r8 * r9                          F  D  E1 E2 E3 E4 E5 E6 WB
r4 = r3 + r7                             F  D  D  D  D  D  D  D  E1 E2 E3 E4 E5 E6 WB
r10 = r5 * r6                                                 F  D  E1 E2 E3 E4 E5 E6 WB
```
26 cykle

2) procesor potokowy z w pełni potokowymi niezależnymi jednostkami
```=
r3 = r1 * r2  F D E1 E2 E3 E4 E5 E6 WB
r5 = r4 + r3    F D  D  D  D  D  D  D  E1 E2 E3 E4 WB 
r6 = r4 + r1                        F  D  E1 E2 E3 E4 WB
r7 = r8 * r9                           F  D  E1 E2 E3 E4 E5 E6 WB
r4 = r3 + r7                              F  D  D  D  D  D  D  D  E1 E2 E3 E4 WB
r10 = r5 * r6                                                  F  D  E1 E2 E3 E4 E5 E6 WB
```
26 cykle

3) procesor potokowym jak wyżej, ale używającym reorder buffera
```=
r3 = r1 * r2  F D E1 E2 E3 E4 E5 E6 WB
r5 = r4 + r3    F D              E1 E2 E3 E4 WB 
r6 = r4 + r1      F  D  E1 E2 E3 E4             WB
r7 = r8 * r9         F  D  E1 E2 E3 E4 E5 E6       WB
r4 = r3 + r7                        F  D  E1 E2 E3 E4 WB
r10 = r5 * r6                          F  D  E1 E2 E3 E4 E5 E6 WB
```
18 cykli
## Zadanie 5
:::success
Autor: Mateusz Kitzol	
:::

![](https://i.imgur.com/Jp7s9qE.png)

a)

| Kolejne_instrukcje | 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  |
| -------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| r3 = r1 * r2   | F   | D   | E1  | E2  | E3  | E4  | E5  | E6  | WB  |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |
| r5 = r4 + r3   |     | F   | D   | D   | D   | D   | D   | D   | D   | E1  | E2  | E3  | E4  | E5  | E6  | WB  |     |     |     |     |     |     |     |     |     |     |     |     |     |     |
| r7 = r2 + r6   |     |     | F   | F   | F   | F   | F   | F   | F   | D   | E1  | E2  | E3  | E4  | E5  | E6  | WB  |     |     |     |     |     |     |     |     |     |     |     |     |     |
| r10 = r8 + r9  |     |     |     |     |     |     |     |     |     | F   | D   | E1  | E2  | E3  | E4  | E5  | E6  | WB  |     |     |     |     |     |     |     |     |     |     |     |     |
| r11 = r7 * r10 |     |     |     |     |     |     |     |     |     |     | F   | D   | D   | D   | D   | D   | D   | E1  | E2  | E3  | E4  | E5  | E6  |  WB  |     |     |     |     |     |     |
| r5 = r5 + r11  |     |     |     |     |     |     |     |     |     |     |     | F   | F   | F   | F   | F   | F   | D   | D   | D   | D   | D   | D   | E1  | E2  | E3  |  E4  | E5  |  E6  |  WB  |

Liczba cykli: 30 


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

Liczba cykli: 36

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

Liczba cykli: 30

## Zadanie 6
:::success
Autor: Patryk Rybak	
:::

![](https://i.imgur.com/GSatYKX.png)

![](https://i.imgur.com/xQZPyYr.png)

![](https://i.imgur.com/1GTzSd2.png)

![](https://i.imgur.com/rB39T25.png)

