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

## Zadanie 2
:::success
Autor: Yaryna Rachkevych (punkty a i b), Bartosz Borecki (punkty c i d)

**Forwardowanie** danych polega na przekazywaniu danych pomiędzy falami potoku zanim znajdą się w rejestrach.

**Stalling** polega na tym, że procesor sam wykrywa hazart danych i wprowadza opóźnienia.
a)
b)

:::

## Zadanie 3
:::success
Autor: Hanna Laszkiewicz


:::

## Zadanie 4
:::success
Autor: Jan Kamyk
:::

## Zadanie 5
:::success
Autor: Hanna Laszkiewicz

Poprawka: wykonają się 2 instrukcje zamiast 3, a nowy, poprawny adres instrukcji będzie znany po fazie DM instrukcji, w której sprawdzamy warunek skoku.


:::

## Zadanie 6
:::success
Autor: Yelyzaveta Ilman
W predyktorie **always-taken**, wszystkie skoki są przewidywane jako skoki taken. Zatem, jeśli przewidujemy skok jako wzięty, a rzeczywiście tak nie jest, to mamy dodatkowy $1$ **cykl opóźnienia**

Z rozkładu instrukcji w progrzmie (pierwsza tabelka) widzimy, że
instrukcji skoku (if $x$ relop $y$ goto $L$) jest $25$%
prawdopodobieństwo błędu dla każdej instrukcji $= 100-45=55$%

Wtedy:
Average $CPI = 0,25 * 0,55 * 1 = 0,1375$

> [name=Piotr Witkowski] Dla programu z $n$ instrukcjami załóżmy, że jego czas wykonania na procesorze z bezbłędną predykcją skoków wynosi $n$ cykli. Dla procesora z punktu a) mamy $0,25n$ instrukcji skoku warunkowego. Spośród tych instrukcji 55% wymaga dodatkowego cyklu (błędnie przewidziana instrukcja). Czyli $0,25*0,55*n$ - liczba dodatkowych instukcji, a zatem tyle samo dodatkowych cykli. Zatem przyrost CPI wynosi $(0,25*0,55*n)/n$.

prawdopodobieństwo błędu dla każdej instrukcji $= 100-55=45$%
Wtedy:
Average $CPI$ = $(0,25*0,45*n)/n$= 0,1125$
prawdopodobieństwo błędu dla każdej instrukcji $= 100-85=15$%
Wtedy:
Average $CPI = (0,25*0,15*n)/n= 0,0375$
Zmniejszamy liczbę skoków o $50$%, ale zwiększamy liczbę instrukcji arytmetycznych o taką samą liczbę, więc:
**always taken**
New Average $CPI = 0,125 * 0,55 * 1 = 0,06875$

**always not taken**
New Average $CPI = 0,125 * 0,45 * 1 = 0,05625$

**predykator 2-bitowy**
New Average $CPI = 0,125 * 0,15 * 1 = 0,01875$

alternatywnie:

**always taken**
New Average $CPI =$ Average $CPI / 2 = 0,1375 / 2 = 0,06875$

**always not taken**
New Average $CPI =$ Average $CPI / 2 = 0,1125 / 2 = 0,05625$

c) **predykator 2-bitowy**
New Average $CPI =$ Average $CPI / 2 = 0,0375 / 2 = 0,01875$
:::

## Zadanie 7
:::success
Autor: Bartosz Kruszewski
:::
#### Modyfikacja procesora

Procesor wykorzystujący tylko jedną jednostkę pamięci na dane oraz instrukcje. Hazard Strukturalny występuje, kiedy faza Fetch będzie wykonywana jednocześnie z fazą Memory, ponieważ nie możliwy jest jednoczesny dostęp do dwóch różnych komórek pamięci w jednym cyklu. Rozwiązaniem jest wstrzymanie potoku, poprzez Stalling.

#### Program

*(s3 + 12) = s5
s5 = *(s3 + 8)
s4 = s2 - s1
if s4 == 0 goto Label
s2 = s0 + s1
s2 = s6 - s1

#### Diagram wykonania

Dla uproszczenia zakładamy, że wykorzystujemy statyczną predykcję always not taken, a warunek skoku nie jest spełniony (czyli ignorujemy efekty działania beq).

Bez tych założeń w przypadku skoku, nastąpił hazard, ale dla instrukcji, które i tak nie mają znaczenia dla programu.

1:      2:      3:      4:      5:      6:      7:      8:      9:      10:     11:     12:
F sw    D s3 12 E s3 12 M       W
        F lw    D s3 8  E s3 8  M s5    W
                F -     D s2 s1 E       M s4    W
                        F beq   F beq   F beq   D s4 0  E       M       W //stalling x2
                                                F +     D s0 s1 E       M s2    W
                                                        F -     D s6 s1 E       M s2    W

#### Czy zmiana kolejnośći instrukcji z zachowaniem semantyki pomoże?

Tak, jeżeli przeniesiemy instrukcje wykorzystujące pamięć danych na koniec programu, gdzie nie będą miały następujących po nich instrukcji do wykonania.

#### Zmodyfikowany program

Ciężko określić czy ta zmiana wpływa na semantykę, jest to zależne od etykiety Label.

s4 = s2 - s1
s2 = s0 + s1
s2 = s6 - s1
if s4 == 0 goto Label
*(s3 + 12) = s5
s5 = *(s3 + 8)

#### Diagram wykonania zmodyfikowanego programu

1:      2:      3:      4:      5:      6:      7:      8:      9:      10:
F -     D s2 s1 E       M s4    W
        F +     D s0 s1 E       M s2    W
                F -     D s6 s1 E       M s2    W
                        F beq   D s4 0  E       M       W
                                F sw    D s3 12 E s3 12 M       W
                                        F lw    D s3 8  E s3 8  M s5    W

#### Czy wstawianie nop rozwiązuje problem?

NOP jest pobierany z pamięci, a to właśnie dostęp do pamięci powoduje hazard, więc NOP spowoduje identyczny problem jak dowolna inna instrukcja.

## Zadanie 8
:::success
Autor: Bartosz Kruszewski
:::

#### Co powoduje wstrzymanie potoku?

Wstrzymanie potoku powodują instrukcje wykorzystujące pamięć danych, umieszone wcześniej niż jako 3 ostatnie instrukcje. Instrukcje te stanowią razem 36% całego programu, więc możemy założyć, że jedna z 3 ostatnich instrukcji będzie taką instrukcją. Jedna instrukcja zwiększa ilość wstrzymanych cykli o 1.

#### Obliczenia

Oznaczamy liczbę instrukcji jako $N$.
Liczba wstrzymanych cykli to $0.36N - 1$

## Zadanie 9
:::success
Autor: Bartosz Kruszewski
:::

Zastępując instrukcje jak w zadaniu, zmniejszamy liczbę faz do 4, ale zwiększamy liczbę instrukcji w programie.

Zakładając czasy działania podzespołów jak z listy 6:

- **IM**: pamięć instrukcji $(250ps)$
- **DM**: pamięć danych $(250ps)$
- **RF**: plik rejestrów $(150ps)$
- **MX**: multiplekser $(25ps)$
- **ALU**: jednostka arytmetyczno logiczna $(200ps)$
- **ADD**: adder do wyliczania BTA $(150ps)$
- **PC**: licznik rozkazów $(50ps)$
- **SE**: rozszerzenie reprezentacji $(50ps)$
- **CU**: jednostka kontrolna $(50ps)$

Długość faz 5-fazowego procesora będzie wynosić:

- **F**: Fetch (250ps)
- **D**: Decode (150ps + 25ps = 175ps)
- **E**: Execute (200ps)
- **M**: Memory (250ps + 25ps = 275ps)
- **W**: Writeback (150 + 25ps = 175ps)

Długość faz 4-fazowego procesora będzie wynosić:

- **F**: Fetch (250ps)
- **D**: Decode (175ps)
- **E**: Execute/Memory (275ps)
- **W**: Writeback (175ps)

Nowa ilość instrukcji:

N * (0.25 * 2 + 0.11 * 2 + 0.12 + 0.52) = N * 1.36

Zakładając, że każda instrukcja przechodzi przez wszystkie fazy uzyskujemy czasy wykonania jednej instrukcji:

5-fazowy procesor: 250ps + 175ps + 200ps + 275ps + 175ps = 1075ps
4-fazowy procesor: 250ps + 175ps + 275ps + 175ps = 875ps

Uwzględniając zmianę ilości instrukcji otrzymujemy czasy wykonania programu:

5-fazowy procesor: N * 1075ps
4-fazowy procesor: N * 1.36 * 875ps = N * 1190ps

Więc dla programów o podanej strukturze, 5-fazowy procesor będzie szybszy.