# Ćwiczenia 9, grupa śr. 14-16, 24 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Krzysztof Chorzempa | X | X | X | X | | X | |
Maciej Ciepiela | X | | X | | | X | X |
Szymon Fica | | | X | | | X | X |
Agnieszka Grala | | | X | | | X | X |
Karolina Jędraszek | X | X | ==X== | X | | X | X |
Katarzyna Jodłowska | | | X | X | | X | X |
Dominik Kiełbowicz | | | | | | | |
Michał Kolasa | | | | | | | |
Rafał Krysa | X | X | X | X | | X | X |
Miłosz Krzysiek | X | X | X | X | | ==X== | X |
Łukasz Kulczycki | | | | | | | |
Leon Lepkowski | | | X | | | | |
Hanna Makowska | X | X | X | X | | X | ==X== |
Jan Marek | X | X | X | | | | |
Cezary Miłek | X | X | X | X | | X | |
Anna Pierzchała | X | X | X | X | | X | X |
Alan Pietrasz | X | X | X | | | X | X |
Kacper Ponikowski | | X | X | | | | |
Dominik Walecko | X | X | X | | | X | X |
Michał Włodarczak | X | X | X | | | | X |
:::

Poniżej można zadeklarować zadanie **6** z **listy 8**:

:::danger
| | 8.6 |
| ----------------------:| -----|
Krzysztof Chorzempa | |
Maciej Ciepiela | |
Szymon Fica | |
Agnieszka Grala | |
Karolina Jędraszek | |
Katarzyna Jodłowska | |
Dominik Kiełbowicz | |
Michał Kolasa | |
Rafał Krysa | |
Miłosz Krzysiek | |
Łukasz Kulczycki | |
Leon Lepkowski | |
Hanna Makowska | |
Jan Marek | |
Cezary Miłek | |
Anna Pierzchała | |
Alan Pietrasz | X |
Kacper Ponikowski | |
Dominik Walecko | |
Michał Włodarczak | ==X== |
:::

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

## Zadanie 1
:::success
Autor: Alan Pietrasz
:::
Bufor predykcji skoków to pamięć, która dla danej instrukcji skoku zapamiętuje pod adresem równym kilku najmłodszym bitom jej adresu jeden bit informacji, czy ostatnio skok został wykonany, czy nie. Dlatego, że instrukcję kojarzymy tylko z kilkoma bitami adresu, to zapamiętany bit może być wspólny dla kilku instrukcji.

W buforze predykcji można także przechowywać więcej bitów stanu predyktora skoków:

2-bitowy predyktor skoków

Zaczynamy od wybranego stanu, na przykład 00.
Następne instrukcje wynkonujemy zgodnie z predyktorem.
Po rzeczywistym obliczeniu warunku przechodzimy w prawo jeśli skok nie powinien zajść i w lewo jeśli powinien.

n-bitowy predyktor będzie miał $2^{n}$ stanów. Połowa z nich będzie predict taken, a druga połowa predict not taken.

## Zadanie 2
:::success
Autor: Cezary Miłek
:::


### Motywacja

Predyktory korelujące, jak sama nazwa wskazuje, opierają się na relacjach pomiędzy podjętymi decyzjami w poprzednich gałęziach kodu.

Uwzględniają one $m$ poprzednich decyzji w predyktorach $n$-bitowych.

**Więc celem jest poprawienie skuteczności przewidywania skoków gałęziowych.**

### Budowa

Chcemy stworzyć rejestry przesuwne *shift register* o długości $m$ przechowujących historię $m$ ostatnich decyzji.

Predykcja polega na kombinacji mniejszych fragmentów bitów oraz ich łączeniu. Otrzymany wynik stanowi indeks, który wykorzystujemy do odczytu odpowiedniej wartości licznika z tablicy przechowującej stan naszych predyktorów.

| | |
|:--------:|:------------------ |
| $00$ | Strongly not taken |
| $01$ | Weakly not taken |
| $10$ | Weakly taken |
| $11$ | Strongly taken |

### Przykład kodu

if (a == 2) a = 0
if (b == 2) b = 0
if (a != b) ...

W tym przykładzie decyzja o skoku w ostatnim rozgałęzieniu jest powiązana z wcześniejszymi skokami. Jeśli na przykład wystąpią warunki `a == 2` i `b == 2`, warunek `a != b` nie zostanie spełniony.

Standardowy predyktor 2-bitowy **niekoniecznie spełni** ostatni warunek `a != b`, jeśli wcześniej spełnione zostały oba poprzednie warunki.

### Predyktor `gshare`

W predyktorze `gshare` indeks jest obliczany przez $(XOR)$ na adresie bieżącego rozgałęzienia oraz $n$ ostatnich podjętych decyzji (gdzie $n$ to długość adresu).

Otrzymany wynik jest używany jako indeks do prognozy w naszym $2$-bitowym liczniku.


## Zadanie 3
:::success
Autor: Karolina Jędraszek
:::

*Czym są predyktory turniejowe. W jaki sposób można połączyć globalne i lokalne predyktory w jeden mechanizm predykcji skoków?*

**Globalne predyktory** - zbierają i analizują skoki globalnie dla całego programu.
**Lokalny predyktor** - śledzi i przewiduje skoki dla konkretnych instrukcji skoku w programie. Przewidywania są oparte na wzorcach zachowań dla wybranej instrukcji skoku, a nie dla całego programu.

**Predyktory turniejowe** korzystają z kilku predykatorów i wybierają najelpszy z nich dla danej instrukcji. Zwykle łączą ze sobą lokalne i globalne predyktory.


Selektor działa jak 2-bitowy predyktor, tzn. jeśli dwa razy z rzędu wybraliśmy zły predyktor (np. lokalny), to następnym razem wybierzemy globalny.
Jeśli wystąpi zła predykcja, musimy zmienić dane w selektorze i w predyktorze, który dokonał nieprawidłowego skoku.

Wiemy też, że liczba bitów *branch history* wykorzystywana do indeksacji globalnego predyktora jest równa liczbie bitów *branch adress*.

## Zadanie 4
:::success
Autor: Katarzyna Jodłowska
:::


**Tage hybrid predykator** - łączy ze sobą predykator globalny (Base predictor) i 4 predyktory lokalne (P(0)...P(4)), jest więc predykatorem turniejowym.


h[0:L(x)] - przechowuje segment historii skoków
tag - zwykle zajmuje 4-8 bitów

Każdy z predyktorów jest 2 lub 3 bitowy.
Predykcje P(1)...P(4) wykonywane są tylko, jeżli tag P(i) pasuje do hasha adresu skoku i globalnej historii skoków. Natomiast P(0) nie ma tagu i jest wykorzystywany domyślnie.
Dodatkowo w P(1)...P(4) znajduje się 2 bitowe pole "use", które pamięta czy użyliśmy danego predyktora (jeśli tak, to mamy większą szansę, że kolejne przewidywania będą poprawne).

Jak rozumieć hasha?
Funkcja, której argumentami jest aktualna instrukcja skoku i fragment historii. Porównujemy jej wynik z tagiem danego P(i), jeśli pasują, tzn. że uważamy predykcję za poprawną.

## Zadanie 5
:::success
Autor: Rafał Krysa
:::

## Zadanie 6
:::success
Autor: Miłosz Krzysiek
:::


### Krótki opis
- Misprediction Penalty: Jest to kara czasowa, która występuje, gdy przewidywany skok okazuje się błędny. W tym przypadku wynosi ona cztery cykle.
- Buffer Miss Penalty: To kara czasowa za niepowodzenie w trafieniu do bufora celów skoków. W tym przypadku wynosi ona trzy cykle.
- Hit Rate: To odsetek trafień do bufora celów skoków. W tym przypadku wynosi 90%, co oznacza, że 90% skoków warunkowych jest trafionych w buforze.
- Accuracy: To dokładność przewidywania skoków. W tym przypadku wynosi 90%, co oznacza, że 90% przewidywanych skoków jest prawidłowych.
- Branch Frequency: To częstotliwość występowania skoków. W tym przypadku wynosi 15%, co oznacza, że 15% instrukcji to skoki warunkowe.
- Fixed Branch Penalty: To stała kara czasowa za skok, bez względu na jego wynik. W tym przypadku 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 (w przypadku braku BTB) = 0 (ponieważ nie ma 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 przewidywanie skoku
`(Branch Frequency) * Hit Rate * (1 - Accuracy) =`
`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

Oznaczmy przyspieszenie procesora z buforem celów skoków w porównaniu z procesorem bez bufora skoków jako `S`

Dla procesora bez bufora skoków:

`CPI` - Dla procesora bez bufora skoków:

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

`CPI_BTB` - Dla procesora z buforem skoków:
`CPI_BTB = 1 + 0,099 = 1,099`

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

Oznacza to, że procesor z buforem celów skoków jest około 18% szybszy niż procesor bez bufora skoków.

## Zadanie 7
:::success
Autor: Hanna Makowska
:::