# Ćwiczenia 8, grupa śr. 17-19, 4. maja 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | |
Kamila Brzozowska | X | X | X | X | X | |
Adam Ciężkowski | X | X | X | X | X | |
Natalia Czerep | X | X | X | X | | |
Jan Dalecki | X | X | X | X | X | |
Marko Golovko | X | X | X | X | | |
Adam Górkiewicz | X | X | X | X | X | X |
Piotr Gunia | X | X | X | X | | |
Krzysztof Jadłowski | | x | x | x | | |
Magdalena Jarecka | X | | X | X | X | |
Mikołaj Jaszcza | X | X | X |==X==| | |
Monika Jędrzejkowska | | | | | | |
Michał Kierul | X | X | X | | | |
Damian Lukas | | | | | | |
Karol Ochman-Milarski | | | | | | |
Piotr Piesiak | | | | | | |
Damian Ratajski | | | | | | |
Aleksandra Rozkrut | | X | X | X | | |
Marcin Sarnecki | X | X |==X==| X | | |
Maria Szlasa | | X | X | X | | |
Mateusz Burdyna | X | X | X | X | | |
Magdalena Słonińska | | | | | | |
Nikola Wrona | X | X | X | X | | |
Marcin Wróbel | X |==X==| X | X | X | |
:::

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

## Zadanie 1
:::success
Autor: Mateusz Burdyna
:::




(źródło: https://slideplayer.com/slide/14469754/)

Algorytm tomasulo zapisuje dane out of order (w taki sposób, że w efekcie i tak dostajemy taki sam wynik jak w przypadku in order). Problem pojawia się gdy chcemy taki program debbugować. W środku działania programu instrukcje zapisywane są out of order, co jest problemem dla programisty.

Aby rozwiązać problem skorzystamy z reorder buffera.
Zamiast zapisywać do rejestrów będziemy zapisywać do reorder buffera, którego mechanika działania zadba o to, żeby zapis do rejestrów odbywał się in order.

## Zadanie 2
:::success
Autor: Marcin Wróbel
:::
Branch-target buffer to stuktura przechowująca historię poprzednich skoków. Zawiera ona adres instrukcji będącej instrukcją skoku, adres następnej instukcji, oraz to czy następna instukcja była wynikiem wykonania skoku, czy nie.
Schemat użycia w prostym 5-fazowym procesorze potokowym:
Automat będacy schematem 2-bitowego predyktora skoków

for (int i = 0; i < 1000000; i++) {
    if (i > 500000) {
        // ...
    }
}

for (int i = 0; i < 1000000; i++) {
    int j =0;
    do {
        j++;
    } while(j<3);
}

W przypadku predyktora statycznego połowa instrukcji if zostanie błędnie przewidziana. Predyktor 2-bitowy błędnie przewidzi ten skok maksymalnie 4 razy.
Bity predyktora 2-bitowego można zapamiętać razem z instrukcją w pamięci instrukcji.

Uogólniony predyktor $n$ bitowy będzie w jednym z $2^n$ stanów.

## Zadanie 3
:::success
Autor: Marcin Sarnecki
:::

Correlating predictors

Pomysł polega na zapamiętaniu $m$ poprzednich decyzji. Mamy $2^m$ wszystkich
możliwych kombinacji poprzednich $m$ decyzji, dla każdej z nich trzymamy osobno $n$ bitowy predyktor.

Przykład kodu, dla którego predyktor lokalny nie jest w stanie osiągnąć
idealnej precyzji:

for(int i = 0; i < n; i++)
$\quad$ if(i % 2 == 0)
$\quad\quad$ ...

W tym przykładzie if w środku pętli będzie wykonywał się naprzemiennie, predyktor lokalny nie będzie w stanie poprawnie przewidywać, czy wykonywać skok, natomiast correlating predictor poradzi sobie z tym bez problemu, ponieważ będzie osobno rozpatrywał maski bitowe poprzednich decyzji (01 oraz 11)

Ogólnia struktura: (m, n)

pamiętamy m ostatnich decyzji
dla każdej z nich trzymamy n bitowy predyktor


Predyktor gshare korzysta z pomysłu haszowania adresu instrukcji oraz stanu historii. Funkcja haszującą jest XOR

## Zadanie 4
:::success
Autor: Mikołaj Jaszcza
:::

Predyktory turniejowe to rodzaj "systemu" predykcji skoków, który pozwala łączyć zalety różnych predyktorów "zwykłych" opisywanych wcześniej. W praktyce takie systemy okazują się lepsze niż (rozpatrywane osobno) gshare czy lokalne predyktory n-bitowe.

Zwyczajowo taki system jest złożony z trzech predyktorów (w tym dwóch przewidujących czy skok nastąpi oraz jednego predyktora pomocniczego). Predyktor "pomocniczy" przy każdym zapytaniu przez jednostkę sterującą o predykcję dot. skoku sprawdza, który z predyktorów głównych sprawdzał się lepiej w poprzednich zapytaniach ( * ) i zwraca jego predykcję.

Następnie - mając dostęp do poprawnej odpowiedzi (tj. czy skok faktycznie nastąpił) - predyktor pomocniczy ocenia poprawność odpowiedzi obu predyktorów głównych i aktualizuje wewnętrzny stan wskazujący który z nich sprawuje się lepiej w ostatnim czasie (oczywiście wciąż - zupełnie niezależnie - aktualizujemy stany wewnętrzne predyktorów głównych tak jak robiliśmy to do tej pory w przypadku "zwykłych" predyktorów pojedynczych). Strukturę która obsługuje takie operacje można reprezentować wewnętrznie jako 2-bitowy rejestr. My natomiast, możemy myśleć o nim jak o automacie działającym w następujący sposób:


( * ) Zauważmy - na bazie schematu powyżej - że w ocenie skuteczności predyktorów liczy się tylko najnowsza historia ich działania. To pozwala na większą dynamikę wyboru predyktora głównego, niż np. liczenie średniej procentowej skuteczności predykcji od początku działania programu.

Predyktory turniejowe najczęściej używane są do łączenia predyktorów lokalnych i globalnych/korelujących. Popularnym wyborem dla predyktora lokalnego bywa wtedy predyktor 2-bitowy.

Jak widzimy na poniższym schemacie, predyktory turniejowe (zgodnie z intuicją) zazwyczaj sprawdzają się lepiej od pojedynczych predyktorów zwykłych będących ich częścią.

[https://people.engr.ncsu.edu/efg/521/s06/common/lectures/notes/lec17.html]

## Zadanie 5
:::success
Autor: Adam Ciężkowski
:::


<!--  -->


"The tagged hybrid version of this predictor also includes a 2-bit use field in each of the history-indexed predictors. The use field indicates whether a prediction was recently used and therefore likely to be more accurate; the use field can be periodically reset in all entries so that old predictions are cleared."

## Zadanie 6
:::success
Autor: Adam Górkiewicz
:::

[...]
Założenia:
* Inicjalne numery branchów w predyktorach odpowiadają operacjom o adresach kolejno 453, 543, 777.
* "with one misprediction" <=> weak prediction (else strong).
* Z cache'a predyktora usuwany jest branch, do którego odwołaliśmy się najdawniej.
* Podczas cache'owania nowego brancha, jest on inicjalizowany na "weakly not taken" dla każdego "last outcome", natomiast jego historia jest inicjalizowana na T, T.
* Update predyktora jest wdrażany przed następną predykcją

Predyktor korelujący (1, 2):
Predyktor lokalny (2, 2):
<!-- Predyktor korelujący (2, 2): -->
<!--  -->
<!--  -->