# SYK8
## Zadanie 1

Możemy dodać reorder buffera jako kolejną strukturę: `reorder buffer`
Każdy rejestr w `register file` rozszerzamy o miejsce na adres instrukcji z `reorder buffera` piszącej do niego

Teraz po wykonaniu obliczeń zamiast przekazywać wynik do
`reservation stations` i `register file`

przekazujemy wynik do `reservation stations` i
`reorder buffera` (patrzymy który rejestr ma tag odpowiadający odpowiadający wykonanemu obliczeniu i dodajemy go do reorder buffera, bez zmieniania wartości w register file)

Gdy teraz zlecamy jakąś instrukcję do wykonania, sprawdzamy, nie tylko, czy znajduje się w `register file`, ale także czy jest obliczona w reorder bufferze.
Wyniki kolejnych instrukcji są wdrażane zgodnie z kolejnością kolejki FIFO w `reorder bufferze`

## Coś, nie wiem do czego się odnoszącego, więc nie usuwam


## Zadanie 2

Branch-Target Buffer przechowuje informacje o tym, czy pobierana instrukcja jest skokiem oraz o instrukcji do której należy wykonać skok. Adres kolejnej instrukcji jest wysyłany jeszcze przed zdekodowaniem aktualnej, dlatego przy każdej instrukcji wykonywane jest zapytanie do buffera.
Jeśli instrukcja jest skokiem, to adres kolejnej instrukcji jest od razu wysyłany, aby w kolejnym cyklu rozpocząć jej Fetch.





W przypadku predyktora statycznego (np. always-taken lub always-not-taken) dojdzie do tysięcy błędnych decyzji w instrukcji if. Predyktor 2-bitowy podejmie tylko 8 błędnych decyzji, po zakończeniu każdego przedziału $[0, 1000) [1000, 2000] ...$

Bity predyktora 2-bitowego można zapamiętać razem z pamięcią instrukcji w tablicy zawierającej instrukcje.

Uogólniony predyktor $n$ bitowy będzie przechowywać $2^n$ stanów.

## Zadanie 3

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

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]