---
# System prepended metadata

title: Untitled
tags: [SYK21, pwit, ćwiczenia]

---

#Konsultacje, 29. kwietnia 2022, lista 6

###### tags: `SYK21` `ćwiczenia` `pwit`



:::danger
|                        | 1     | 2   | 3   | 4   | 5   | 6   |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
 Maria Szlasa              | 1     | 1   | 1   | 1   |     | 1    | 
:::

## Zadanie 1
:::info
Przedstawiony poniżej fragment kodu wykonujemy na procesorze potokowym bez jednostki wykrywania hazardów. Początkowa wartość rejestru $s_0$ to $11$ a $s_1$ to $22$.
$s_0 = s_1 + 5$
$s_2 = s_0 + s_1$
$s_3 = s_0 + 15$
$s_4 = s_0 + s_0$
Jakie będą końcowe wartości rejestrów $s_2$ , $s_3$ i $s_4$, a jakie powinny być, gdyby procesor wykonał program poprawnie? Uzupełnij kod o instrukcje nop by usunąć hazardy danych i pokaż, że program wykona się teraz poprawnie. Omawiając wykonanie kodu posługuj się diagramami wykonania.

**Wskazówka** Pamiętaj, że plik rejestrów jest zapisywany w pierwszej połowie cyklu, a odczytywany w drugiej. Tzn. odczyt rejestru w fazie ID zwróci wartość zapisaną tam w fazie WB odbywającej się w tym samym cyklu.
:::

$s_0$ jest modyfikowane w pierwszej instrukcji, ale informacja o jego zmienionej wartości pojawia się w pamięci dopiero w 5 fazie cyklu (w pierwszej jego części).
![](https://i.imgur.com/Qc2u46X.png)
Dlatego zez wykrywania hazardów informacja o prawidłowej wartości $s_0$ będzie poprawna tylko dla instrukcji nr. 4. 
Końcowe wartości rejestrów to:
$s_0=27$
$s_1=22$
$s_2=33$
$s_3=26$
$s_4=54$

Poprawne wartości to:
$s_0=27$
$s_1=22$
$s_2=49$
$s_3=42$
$s_4=54$

Po dodaniu instrukcji $nop$ algorytm będzie wyglądał następująco:
$s_0 = s_1 + 5$
$nop$
$nop$
$s_2 = s_0 + s_1$
$s_3 = s_0 + 15$
$s_4 = s_0 + s_0$
Diagram:
![](https://i.imgur.com/51gDffI.png)

## Zadanie 2
:::info
Przedstawione poniżej fragmenty kodu wykonujemy na procesorze potokowym z jednostką wykrywania hazardów danych, forwardingiem i możliwością wstrzymywania (ang. stall) potoku. Przedstaw ich diagramy wykonania i pokaż, w jaki sposób procesor upora się z hazardami danych.
:::
W tym zadaniu trzeba zwrócić szczególną uwagę na instrukcje typu $x=*y$, ponieważ o ich wartości dowiadujemy się dopiero w fazie RF. W przypadku kiedy po tego typu instrukcji, $x$ będzie używany w kolejnej instrukcji, to trzeba zastosować stalling.
a) 
$s_1 = s_2 + 5$ 
$t_0 = t_1 - t_2$
$t_3 = *(s_1 + 15)$
$*(t_0 + 72) = t_5$
$t_2 = s_4 \& s_5$

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


b) 
$s_0 = t_0 + t_1$
$s_1 = t_2 - t_3$
$s_2 = s_0 \& s_1$
$s_3 = t_4 | t_5$
$s_4 = s_2 + s_3$
![](https://i.imgur.com/O2ykqsg.png)

c) 
$t0 = s0 + s1$
$t0 = t0 - s2$
$t1 = *(t0 + 60)$
tutaj powinno być zatrzymanie (Stall)
$t2 = t1 \& t0$
![](https://i.imgur.com/N7fRErc.png)

d) 
$t_0 = s_0 + s_1$
$t_1 = *(s_2 + 60)$
$t_2 = t_0 - t_3$
$t_3 = t_1 \& t_0$
![](https://i.imgur.com/qz7m5Vu.png)

## Zadanie 3
:::info
Rozważmy następujący program:
$LOOP: s_0 = *s_3$
$s_1 = *(s_3 + 8)$
$s_2 = s_0 + s_1$
$s_3 = s_3 - 16$
$if s_2 != 0 goto LOOP$
Załóżmy, że procesor (z jednostką wykrywania hazardów danych, forwardingiem i możliwością wstrzymywania potoku) używa bezbłędnego predyktora skoków (nie będzie żadnych wstrzymań potoku spowodowanych hazardami sterowania), oraz że decyzja o skoku podejmowana jest w fazie EX.
a) Narysuj diagram wykonania dla pierwszych dwóch iteracji pętli
b) Zaznacz fazy potoku, w których procesor nie wykonuje użytecznej pracy.
:::
$LOOP: s_0 = *s_3$
$s_1 = *(s_3 + 8)$
tutaj powinno być wstrzymanie i tutej procesor nie wykonuje żadnej pożytecznej pracy 
$s_2 = s_0 + s_1$
$s_3 = s_3 - 16$
$if s_2 != 0 goto LOOP$
a)
![](https://i.imgur.com/52yxHDq.png)
b)
![](https://i.imgur.com/0knBx7k.png)


## Zadanie 4
:::info
Powtórz zadanie 3. dla procesora ze statycznym predyktorem skoków w wariancie a) always-taken oraz b) always-not-taken. 
W punkcie b) możesz przyjąć, że po kodzie pętli następuje dowolny wybrany przez Ciebie ciąg instrukcji.
:::
UWAGA - jak poprzednio zapomniałam o stallingu i jest on w tych samych miejscach co w poprzednim zadaniu
a) always-taken
zakładamy, że zawsze wpadniemy do pętli, dlatego (trzy) instrukcje wykonają się niepotrzebnie tylko w ostatnim przebiegu pętli
![](https://i.imgur.com/EwJJCqw.png)
b) always not taken
zakładamy, że warunek pętli nie zostanie spełniony, dlatego przy każdym powtórzeniu pętli będziemy wykonywali trzy dodatkowe instrukcje. skok będzie przewidziany poprawnie tylko ostatni raz
![](https://i.imgur.com/iMpjsZV.png)


## Zadanie 6
:::info
Załóżmy, że rozkład instrukcji w programie wykonywanym na procesorze potokowym jest następujący:
![](https://i.imgur.com/m1oy467.png)
![](https://i.imgur.com/Y2lcGvf.png)
Dla tego programu prawdopodobieństwa poprawnej predykcji skoków przez różne predyktory widnieją w tabelce:
![](https://i.imgur.com/lg0ja43.png)
Przy tych (realistycznych) założeniach porównamy wydajność predyktorów skoków.
a) Jaki jest przyrost wartości CPI wywołany błędnie przewidzianymi skokami dla procesora z predyktorem always-taken? Procesor używa wczesnego wykonywania
skoków, a w programie nie ma hazardów danych.
b) Powtórz punkt a) dla procesora z predyktorem always-not taken.
c) Powtórz punkt a) dla procesora z predyktorem 2-bitowym.
d) Załóżmy, że nasz program potrafimy przepisać w taki sposób, że połowę skoków zastąpiliśmy instrukcjami arytmetycznymi. Jakie otrzymamy przyśpieszenie? Załóż, że poprawnie i niepoprawnie przewidziane skoki mają taką samą szansę bycia zastąpionymi.
:::
CPI: Cycles/instruction

Wczesne wykonywanie skoków, czyli kara w przypadku błędnego skoku wynosi 1.

a) Always-taken 
błędne predykcje: 100% - 45% = 55%
wzrost CPI: 0.25 * 0.55 * 1 = 0,1375
b) Always-not-taken
błędne predykcje: 100% - 55% = 45%
wzrost CPI: 0.25 * 0.45 * 1 = 0,1125
c) 2-bitowy
błędne predykcje: 100% - 85% = 15%
wzrost CPI: 0.25 * 0.15 * 1 = 0,0375
d) Redukcja liczby skoków
Ilość skoków zminiejsza się o połowę, zatem wynosi 12.5%
* Always-taken
błędne predykcje: 100% - 45% = 55%
wzrost CPI: 0.125 * 0.55 * 1 = 0,06875
* Always-not-taken
błędne predykcje: 100% - 55% = 45%
wzrost CPI: 0.125 * 0.45 * 1 = 0,05625
* 2-bitowy
błędne predykcje: 100% - 85% = 15%
wzrost CPI: 0.125 * 0.15 * 1 = 0,01875
