# Ćwiczenia 9, grupa śr. 12-14, 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | |
Małgorzata Galińska | X | X | X | X | | | |
Maria Hreniak | X | X | X | X | | | |
Jakub Jankowski | X | X | X | X | | | |
Mikołaj Kalitka | X | X | X | X | | | |
Julia Konefał | X | X | X | X | | | |
Julia Kulczycka | ==X== | X | X | X | | | |
Cecylia Łyjak | | | | | | | |
Adam Majchrowski | X | X | X | X | | | |
Piotr Mańkowski | | | | | | | |
Piotr Salamon | | | | | | | |
Maciej Szałasz | X | ==X== | X | X | | | |
:::

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

:::danger
| | 8.6 |
| ----------------------:| -----|
Mikołaj Balwicki | |
Małgorzata Galińska | |
Maria Hreniak |==X== |
Jakub Jankowski | |
Mikołaj Kalitka | |
Julia Konefał | |
Julia Kulczycka | |
Cecylia Łyjak | |
Adam Majchrowski | X |
Piotr Mańkowski | |
Piotr Salamon | |
Maciej Szałasz | |
:::

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

## Zadanie 1
:::success
Autor: Julia Kulczycka
:::
**Bufor predykcji skoków** to mały bufor przechowujący informację o tym, czy dana instrukcja warunkowa była ostatnio wykonana czy nie. Jest bardzo prostym obwodem wykorzystywanym w sytuacjach, gdy opóźnienie wykonywania operacji jest większe od czasu wyliczenia wyniku warunku.

Taki bufor wykorzystuje fakt, że większość insatrukcji warunkowych kieruje raczej skłania się do decyzji w jednym kierunku (np. większość czasu prawda). Pozwala to na sensowne przyśpieszenie kodu. Według książki już statyczne przewidywanie jest w stanie zapewnić 75% poprawnego przewidywania.

### 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

### 2-bitowy predyktor
1-bitowy predyktor ma dosyć poważną wadę. Jeżeli instrukcja jest prawie zawsze wykonywana, to gdy chociaż raz nie zostanie wykonana, stan bufora się zmieni i otrzymamy złą predykcję, gdy kolejna wraca do pierwotnego wykonania.

Jesteśmy w stanie rozwiązać ten problem wykorzystująć predyktor 2-bitowy, który wymaga większego odchylenia niż jedno nieprawidłowe przewidzenie, do zmiany decyzji o wykonaniu instrukcji warunkowej.


Jego skuteczność jest już średnio bliższa 90%.

### Program

L1:     ...
(1)     if b goto L3
MAIN:     ...
(2)     if a goto L1
        ...
        goto MAIN
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.

W sytuacji gdy predyktor statyczny nie będzie przewidywał skoku, to podobna sytuacja zajdzie w 1, a dynamiczny poprawi swoją predykcję.

## Rozszerzenie do n-bitów
W podobny sposób możemy definiować predykatory 3-bitowe, 4-bitowe itd., które wymagają więcej nieprawidłowych przewidzeń do zmiany decyzji. Na przykład dla predykatora 3-bitowego mielibyśmy już 8 stanów - 4T i 4NT. Dodanie każdego kolejnego bitu jednak niewiele poprawia precyzję.

## Zadanie 2
:::success
Autor: Maciej Szałasz
:::
### Ogólne spostrzeżenia

Skoki warunkowe mogą wykazywać 2 rodzaje korelacji:
- Korelacja globalna: prawdziwość warunku skoku może zależeć od
prawdziwości (lub nieprawdziwości) warunków w innych skokach wykonanych
wcześniej
- Korelacja lokalna: prawdziwość warunku może zależeć od prawdziwości
warunku we wcześniejszych wykonaniach tego samego skoku

**Predykatory lokalne nie wykrywają korelacji globalnych**

### Przykład korelacji globalnej
**Korelacja:** jeżeli b1 i b2 to prawda, to b3 też da prawdę (predykator, który sprawdza tylko jeden branch na raz, tego nie wykryje).

### Przykład korelacji lokalnej:

Skrok sprawdzajacy warunek kontynuacji pętli wewnętrznej wskazuje zachowanie "“1110111011101110…”". Na opdstawie 3 poprzednich wyników skoku można przewidzieć kierunek następnego.

### Kiedy lokalny predyktor nie zadziała?

(1) if (a == x) a = y
(2) if (b == x) b = y
(3) if (a != b) ...

Mamy przypadki:
- 1 i 2 => !3
- 1 lub 2 => 3
- !1 i !2 => !3

Lokalny predyktor skoków ma losową szansę na wykonanie skoku poprawnie

### Budowa

Predyktory korelujące wykorzystują lokalne predyktory w połączeniu z rejestrem historii skoków.
Globalna historia skoków przechowywana jest w rejestrze przesuwnym, gdzie każdy bit oznacza skok lub jego brak.
Układ wylicza hash wykorzystywany jako indeks tablicy predykcji, która decyduje o wykonaniu skoku.
Zaletą tego rozwiązania jest bardzo prosta budowa.

## Zadanie 3
:::success
Autor: Adam Majchrowski
link o którym wspominałem:
https://www.youtube.com/watch?v=-T8yDJ8vTuI
:::

## Zadanie 4
:::success
Autor: Jakub Jankowski

:::

## Zadanie 5
:::danger
Autor:
:::

## Zadanie 6
:::success
Autor: Jakub Jankowski

:::

## Zadanie 7
:::danger
Autor:
:::