# Ćwiczenia 9, grupa cz. 16-18, 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Marcin Banak | X | | X | | | X |
Bartosz Borecki | X | | X | | | | |
Karol Burczyk | X | | X | | |
Yelyzaveta Ilman | | | | | | | |
Antoni Kamiński | X | | X | | X | X | |
Jan Kamyk |==X== | X | X | X | | X | |
Bartosz Kruszewski | X | X | X | X | | X | |
Hanna Laszkiewicz | X | X | ==X== | X | | X | X |
Kaja Matuszewska | | | | | | | |
Dominik Muc | | | | | | | |
Krzysztof Ostrowski | | | | | | | |
Franciszek Przeliorz | X | | X | | | X | |
Yaryna Rachkevych | X | X | X | | | X | |
Mikołaj Kalitka | X | X | X | X | | X | X |
Piotr Thamm | X | X | X | X | | ==X== | |
Taras Tsehenko | X | | X | | | X | |
Wiktor Małek | | | | | | | |
Piotr Salamon | X | X | X | | | X | X |
:::

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

## Zadanie 1
:::success
Autor: Jan Kamyk
:::


Bufor predykcji skoków - struktura w architekturze procesora, która przewiduje czy wykona się skok w przypadku instrukcji warunkowej. W osobnym module trzyma adres instrukcji do której może skoczyć oraz informacje czy skoczy czy nie.

W 5-fazowym procesorze potokowym bufor jest wykorzystywany w fazie fetch i decyduje czy następna instrukcja to ta po skoku czy kolejna bez skoku.

2-bitowy predyktor skoków ma 4 stany:
Strongly taken - 11
Weakly taken - 10
Weakly not-taken - 01
Strongly not-taken - 00


W zależności w którym stanie się znajdujemy i czy skok faktycznie się wykonał lub nie przesuniemy się w lewo (jak się wykonał) albo w prawo (jak się nie wykonał).

Predyktor statyczny - jeżeli skok jest do przodu (Forward) to zakładamy że nie skoczymy, a jak skok do tyłu (Backward) to zakładamy że skoczymy

Przykład kodu:

1: A
if b goto third (1)
2: B
if a goto first (2)
C
goto second
3: D

Predyktor statyczny dla skoku oznaczonego jako (2) przewidzi wykonanie tego skoku, ponieważ jest to skok wstecz. W tym konkretnym programie jest to skok, który może zostać wykonany tylko raz. Dlatego predyktor statyczny będzie się mylił o jeden raz mniej niż liczba iteracji pętli. Natomiast predyktor z buforem popełni tylko jeden błąd (ostatni skok).


Bufor predykatora można przechowywać na dwa sposoby:

* dodatkowa pamięć instrukcji (bardziej pamięciożerne)
* osobny moduł (bardziej oszczędnie)

Uogólnienie dla n-bitów:

* Jeżeli wykonano skok zwiększ licznik o 1 , zmniejsz wpp.
* 1 w najbardziej znaczącym bicie oznacza przewidanie skoku, a
* 0 przewidywanie braku skoku.
* będziemy mieć 2^n stanów połowe na taken i drugą na not taken. Przez co możemy więcej razy źle przewidzieć.

## Zadanie 2
:::success
Autor: Piotr Salamon
Predykatory lokalne: nie biorą pod uwagę zależności między kolejnymi instrukcjami

Predykatory korelujące: są to predykatory, które zapamiętują wcześniejsze zaelżności (poprzednie skoki)

dla wartości boolowskich c i d
Kod:
    if(c){
        b = 1
    }
    if(d){
        a = 1
    }
    if(a == 1 || b == 1)
    {
        coś
    }

predykator statyczny nie będzie wiedział, że jeżeli zajdzie skosk w if'e to na pewno nie zajdzie skok w drugimi.

W predykatorach korelujących przechowujemy historię jako rejestr k-bitowy (pamiętamy czy wykonaliśmy k ostatnich skoków).
Zawsze po użyciu przesuwamy "rejestr" o jedno w lewo dodając nowy skok.

Korelujące predyktory skoków wykorzystują lokalne predyktory i rejestr historii skoków. Całość jest połączona XOR. Taki układ wylicza hash, który zostaje użyty jako indeks tablicy predykcji.

:::

## Zadanie 3
:::success
Autor: Hanna Laszkiewicz

:::

## Zadanie 4
:::success
Autor: Bartosz Kruszewski
:::


#### Tagged Hybrid Predictors

Predykatory TAGE łączy w sobie wiele predykatorów globalnych o historiach różnej długości.

#### Działanie

Działa za pomocą hashowania jak gshare, z tą różnicą, że adresy hashowania mogą być krótkie i nie być w 100% dokładne. Predykator stara się dopasować hashowanie do wartości z predykatorów globalnych, natomiast jeżeli jest to niemożliwe to korzysta z predykatora domyślnego.

#### Efektywność

Predykatory TAGE mają bardzo wysoką efektywność, porównując je z innymi predykatorami uwzględniając wielkości pamięci rzędu ponad 32KB. Ich wadą jest długi okres nasycania, podczas którego nie osiągają pełnych możliwości. Predykator najpierw wykonuje przewidywania z duża ilością błędów, które w miare uzupełniania historii występują coraz rzadziej.

## Zadanie 5
:::success
Autor: Antoni Kamiński
:::

predyktor korelujący
- jest (1,2) tzn. dla jednego zapamiętanego skoku ma do wyboru $2^{1} = 2$ predyktory z których każdy jest 2-bitowy
- pamięta 4 skoki (łącznie 16 bitów)


| branch address % 4 | entry | outcome | prediction | result | update |
| --- | --- | --- | --- | --- | --- |
| 454 % 4 = 2 | 4 | T | T | hit | -- |
| 543 % 4 = 3 | 6 | NT | NT' | hit | ->NT |
| 777 % 4 = 1 | 2 | NT | NT | hit | -- |
| 543 % 4 = 3 | 7 | NT | NT | hit | -- |
| 777 % 4 = 1 | 3 | NT | T | miss | ->T' |
| 454 % 4 = 2 | 4 | T | T | hit | -- |
| 777 % 4 = 1 | 3 | NT | T | miss | ->NT |
| 454 % 4 = 2 | 4 | T | T | hit | -- |
| 543 % 4 = 3 | 7 | T | NT | miss | ->NT' |

predyktor lokalny
- pamięta dwa skoki, na każdy po 8 bitów (czyli po 4 wpisy w tabeli predykcji, bo każdy 2-bitowy)


| branch address % 2 | entry | outcome | prediction | result | update |
| --- | --- | --- | --- | --- | --- |
| 454 % 2 = 0 | 0 | T | T' | hit | ->T |
| 543 % 2 = 1 | 4 | NT | T | miss | ->T' |
| 777 % 2 = 1 | 5 | NT | NT | hit | -- |
| 543 % 2 = 1 | 7 | NT | T | miss | ->T' |
| 777 % 2 = 1 | 7 | NT | T | miss | ->NT |
| 454 % 2 = 0 | 0 | T | T | hit | -- |
| 777 % 2 = 1 | 7 | NT | NT | hit | -- |
| 454 % 2 = 0 | 0 | T | T | hit | -- |
| 543 % 2 = 1 | 5 | T | T' | hit | ->T |

:::spoiler (local pred. last 2 outcomes)
Local predictor's last 2 outcomes
0 T T -> T T
1 T NT -> NT NT
2 NT T
3 NT _ -> NT NT -> NT NT
4 T T -> T NT
5 T NT -> NT T
6 NT T
7 NT NT
:::

## Zadanie 6
:::success
Autor: Piotr Thamm

## Wyjaśnienie definicji z polecenia
1. **Misprediction penalty**: Kara za błędne przewidzenie skoku. Z polecenia wiemy, że w tym wypadku wynosi **4 cykle**.
2. **Buffer miss penalty**: kara za pudło w buforze, dotyczy ona sytuacji, gdy procesor próbuje przewidzieć wynik skoku warunkowego, ale informacje o tym skoku nie znajdują się w branch-target buffer (BTB). W takim przypadku mówimy o pudle (miss). Z polecenia wiemy, że w tym przypadku wynosi **3 cykle**.
3. **Hit rate:** To częstotliwość trafień (czyli znalezienia poprawnego adresu skoku) w BTB. Z polecenia wiemy, że w tym przypadku wynosi **90%**.
4. **Accuracy**: To dokładność z jaką poprawnie przewidujemy skoki. Z polecenia wiemy, że wynosi ona **90%**.
5. **Branch frequency**: To częstotliwość występowania skoków warunkowych. Z polecenia wiemy, że jest to **15%**.
6. **Fixed branch penalty**: To stała kara czasowa za skok, bez BTB. Z polecenia wiemy, że wynosi **2 cykle**.

## Procesor bez BTB

## Procesor z BTB


**Rzeczywista kara, to suma tych dwóch przypadków**:
$0,045 + 0,054 = 0,099$

## Różnica w szybkości tych dwóch procesorów


**Zatem, procesor z BTB jest około 18% szybszy niż procesor bez.**

:::

## Zadanie 7
:::success
Autor: Hanna Laszkiewicz
:::