# Ćwiczenia 9, grupa cz. 10-12, 25 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Borys Adamiak | X | | X | X | | X | |
Michał Chawar | X | X | X | | | X | X |
Julia Cygan | X | X | X | X | |==X==| |
Maciej Dengusiak | X | | X | X | | X | |
Patryk Flama | | | | | | | |
Szymon Fluder | X | X | X | X | | X | |
Aleksandra Jędrzejak | X | X | X | | | | |
Mikołaj Karapka | ==X== | X | X | X | | X | |
Viktoriia Kashpruk | X | X | X | X | | X | X
Wiktor Małek | X | X | X | X | | X | X |
Błażej Molik | X | X | X | X | | X | |
Andrzej Morawski | | | | | | | |
Konrad Oleksy | | | | | | | |
Lucjan Pucelak | X | X | ==X== | X | | X | X |
Aleksandra Sęk | | | | | | | |
Radosław Śliwiński | | | | | | | |
Piotr Traczyński | X | X | X | ==X== | | X | X |
Katarzyna Trzos | X | | X | X | | X | |
Piotr Warząchowski | | | | | | | |
Olga Zaborska | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Mikołaj Karapka
:::

### Bufor predykcji skoków
Bufor predykcji skoków posiada informację czy dana instrukcja warunkowa została wykonana czy też nie.

Jest sprawdzany w fazie **Fetch**, co przekłada się na szybsze wykonanie instrukcji programu występującej bezpośrednio po instrukcji **goto**.

### Bufor 1-bitowy
- **Not taken** (0)
- **Taken** (1)

### Bufor 2-bitowy

### Przechowywanie danych
Bity mogą być zapamietywane wraz z informacjami o instrukcji (co wykorzystuje więcej pamięci) lub procesor może miec osobny moduł odpowiedzialny za predykcję skoków.

### Zasada działania
W obu przypadkach jeśli skok zostanie wykonany to zwiększamy wartość licznika o $1$, a gdy nie został wykonany to zmniejszamy $1$.

Predyktor **1-bitowy** myli się przed wyjściem z pętli i po ponownym wejściu do niej, jeśli został już wykonany skok.

Natomiast predyktor **2-bitowy** myli **tylko raz**. Tę róznice jeszcze bardziej widać kiedy mamy zgnieżdżone pętle.

### Przykład programu

(1) x = n
L1: ...

L2:
  (2)  if(x == 0){
          goto L3
       } else {
            x--
            goto L2
       }
L3: ...

Zakładamy, że predyktor statyczny w kroku (2) będzie przewidywał skok. W programie jest to skok wyjścia z pętli więc zostanie wykonany raz, czyli predyktor pomyli się $(n-1)$ razy. Bufor dynamiczny pomyli się **tylko raz**.

### Uogólnienie dla n-bitów
Jeżeli wykonano skok
- zwiększ licznik o $1$,

wpp.
- zmniejsz o $1$

$1$ w najbardziej znaczącym bicie oznacza przewidanie skoku, a $0$ przewidywanie braku skoku. Liczba stanów będzie równa $2^n$.

## Zadanie 2
:::success
Autor: Wiktor Małek
:::


predyktor $(m, n)$ to predyktor korelujący, który pamięta historię $m$ ostatnich instrukcji skoku, z których każda ma $n$-bitowy predyktor.


W powyższym przykładzie w branch history mamy zapisane dla ostatnich m=10 branchy czy się dany branch wykonał czy nie, dla każdej kombinacji (jest ich 2^m) mamy osobny predyktor dwubitowy(n=2) w kolumnie po prawej.

jest to predyktor, który do indeksowania Branch target buffera używa xora z adresu instrukcji i bitów historii skoków;

## Zadanie 3
:::success
Autor: Lucjan Pucelak
:::

Globalny predyktor - jest zależny od historii skoków dla całego programu
Lokalny predyktor - jest zależny od skoków konkretnych instrukcji
Turniejowy predyktor - używa kilku predyktorów, zwykle globalnego predyktora i lokalnego predyktora, oraz selektora do wybierania pomiędzy nimi.


Selektor - działa jak 2-bitowy predyktor, gdy dwukrotnie z rzędu wystąpi błędna prognoza to następnym razem wybierzemy inny predyktor.
Jeżeli wystąpi błędna prognoza to musimy zmienić zarówno tabelę selektora, jak i predyktor, który dokonał nieprawidłowej prognozy.

## Zadanie 4
:::success
Autor: Piotr Traczyński
:::


Struktura predyktora TAGE wygląda w taki sposób, że mamy kilka tablic predyktorów.
Pierwsza tablica jest lokalna i indeksowana numerem instrukcji.
Następne tablice korzystają z historii skoków - każda z coraz dłuższej.


Każda z tych tablic jest indeksowana tag-iem, który jest kilkoma ostatnimi bitami xor-a adresu i historii (tak jak w gshare). Przez to, że pamiętamy tylko kilka ostatnich bitów (4 - 8) na tag każda z tablic nie jest zbyt duża.
W każdym z predyktorów sprawdzamy czy mamy wpis z tagiem pasującym do otrzymanego taga i wybieramy ten pasujący z najdłuższą historią - jeśli żaden nie pasuje to korzystamy z lokalnego predyktora.

## Zadanie 5
:::danger
Autor: do zadeklarowania następnym razem!
:::

## Zadanie 6
:::success
Autor: Julia Cygan
:::
### Opis:
- Misprediction Penalty: Kara czasowa, która występuje, gdy przewidywany skok okazuje się błędny, wynosi cztery cykle.
- Buffer Miss Penalty: Kara czasowa za niepowodzenie w trafieniu do bufora celów skoków (odwołanie się do nie istniejącej wartości w buforze), wynosi trzy cykle.
- Hit Rate: Odsetek trafień do bufora celów skoków, wynosi 90% (90% skoków warunkowych jest trafionych w buforze).
- Accuracy: Dokładność przewidywania skoków, wynosi 90% (90% przewidywanych skoków jest prawidłowych).
- Branch Frequency: Częstotliwość występowania skoków, wynosi 15% (15% instrukcji to skoki warunkowe).
- Fixed Branch Penalty: Stała kara czasowa za skok, bez względu na jego wynik, wynosi dwa cykle.

### Dla procesora bez bufora:
- Średnia kara za przewidywanie skoku
`branch frequency * branch penalty = 0,15 * 2 = 0,3`
- Średnia kara za brak trafienia w buforze = 0 , ze względu na brak bufora do trafień

### Dla procesora z buforem

- Średnia kara za brak trafienia w buforze
`(Branch Frequency) * (1 - Hit Rate) * Buffer Miss Penalty =
0.15 * (1 - 0.9) * 3 = 0.045`
- Średnia kara za złe przewidywanie skoku
`(Branch Frequency) * Hit Rate * (1 - Accuracy) * Misprediction Penalty =`
`0.15 * 0,9 * (1 - 0,9) * 4 = 0,054`

Całkowita kara = 0,045 + 0,054 = 0,099

### O ile szybszy jest procesor z buforem względem procesora bez bufora?

Niech `Res` - stosunek procesora z buforem celów skoków w do procesora bez bufora skoków

`CPI` - procesor bez bufora skoków

`CPI = 1 + 0,3 = 1,3`

`CPI_BTB` - procesor z buforem skoków
`CPI_BTB = 1 + 0,099 = 1,099`

`S = CPI / CPI_BTB = 1,3 / 1,099 = 1,1829`

Zatem procesor z buforem celów skoków jest około 18% szybszy niż procesor bez bufora skoków.

## Zadanie 7
:::success
Autor: Michał Chawar
:::


**a.** Zauważmy, że skoro w przypadku instrukcji bezwarunkowej otrzymujemy od razu następną instrukcję po skoku i nie musimy dopiero obliczać adresu, aby w następnym cyklu ją pobrać. Równie dobrze można założyć, że wszystkie bezwarunkowe instrukcje skoku w programie są usunięte, a w ich miejsce przesuwają się docelowe instrukcje po skoku. Stąd otrzymujemy bonus (ujemną karę) w wysokości $1$ cyklu.

**b.** Mamy $1-0,9 = 10\%$ instrukcji skoku (bezwarunkowego), które nie trafiają do bufora celów skoku, i nakładają karę w wysokości $2$ cykli. Stąd na jedną instrukcję w programie przypada $10\% \cdot 5\% \cdot 2 = 0,01$ cyklu kary.

Z drugiej strony, $90\%$ instrukcji skoku (bezwarunkowego) trafia do bufora celów skoku i nakłada bonus w wysokości $1$ cyklu (karę w wysokości $-1$ cyklu), więc mamy $90\% \cdot 5\% \cdot 1 = 0,045$ cyklu bonusu na jedną instrukcję w programie.

Ostatecznie więc przypada $0,045 - 0,01 = 0,035$ cyklu bonusu na instrukcję.

Gdyby procesor nie stosował tej techniki, otrzymalibyśmy tylko pierwszą karę za nietrafianie do bufora, a więc na instrukcję przypadałoby $0,01$ cyklu kary. Porównując szybkości (dla jednego cyklu na wykonanie każdej instrukcji)

$$\frac{1 - 0,035}{1 + 0,01} = \frac{0,965}{1,01} \approx 0,955445$$

otrzymujemy ok. $4,5\%$ przyspieszenia.

Aby odpowiedzieć na ostatnie pytanie, uzależnimy ten stosunek od zmiennej reprezentującej *hit rate*. Oznaczmy ten przez $H$ (oczywiście $0 \leqslant H \leqslant 1$). Mamy więc przyspieszenie $S$ w wielkości

$$S = 1 - \frac{1 + [(1 - H) \cdot 0,05 \cdot 2] - [H \cdot 0,05 \cdot 1]}{1 + [(1 - H) \cdot 0,05 \cdot 2]}=$$$$= 1 - \frac{1 + 0,1 - 0,1H - 0,05H}{1 + 0,1 - 0,1H} = 1 - \frac{1,1 - 0,15H}{1,1 - 0,1H} =$$$$= 1 - \frac{1,1 - 0,1H - 0,05H}{1,1 - 0,1H} = 1 - 1 + \frac{0,05H}{1,1 - 0,1H} =$$$$= \frac{0,05H}{1,1 - 0,1H}$$

Okazuje się, że przyspieszenie takie wystąpi zawsze (dopiero dla $H=0$ nie ma przyspieszenia). Ustalmy więc, że interesujące nas przyspieszenie to przynajmniej $1\%$.

$$S \geqslant 0,01 \Leftrightarrow \frac{0,05H}{1,1 - 0,1H} \geqslant 0,01$$$$0,05H \geqslant 0,011 - 0,001H$$$$0,051H \geqslant 0,011$$$$H \geqslant 0,2156862... \approx 22\%$$