---
# System prepended metadata

title: 'Ćwiczenia 7, grupa śr. 17-19, 27. kwietnia 2022'
tags: [SYK21, pwit, ćwiczenia]

---

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

![](https://i.imgur.com/m6KslkN.png)
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

![](https://i.imgur.com/j63Cs2y.png)
```
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ą

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


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

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



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

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

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). 
![](https://i.imgur.com/CtcRa6G.png)
![](https://i.imgur.com/VoZe55q.png)

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

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.

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



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

```asm=
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
![](https://i.imgur.com/JP6A8pL.png)




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**
![](https://i.imgur.com/lVYYPUZ.png)




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

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




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

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

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:

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

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):

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

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.