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

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


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$

c)
$t0 = s0 + s1$
$t0 = t0 - s2$
$t1 = *(t0 + 60)$
tutaj powinno być zatrzymanie (Stall)
$t2 = t1 \& t0$

d)
$t_0 = s_0 + s_1$
$t_1 = *(s_2 + 60)$
$t_2 = t_0 - t_3$
$t_3 = t_1 \& t_0$

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

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

## Zadanie 6
:::info
Załóżmy, że rozkład instrukcji w programie wykonywanym na procesorze potokowym jest następujący:
Dla tego programu prawdopodobieństwa poprawnej predykcji skoków przez różne predyktory widnieją w tabelce:
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