---
# System prepended metadata

title: 'Ćwiczenia 9, grupa cz. 16-18, 25 kwietnia 2024'
tags: [pwit, ćwiczenia, SYK24]

---

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

![z1tresc](https://hackmd.io/_uploads/SyKKdJOW0.png)

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

![z1 predyktor](https://hackmd.io/_uploads/HkhIvk_-C.png)


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).

![z1 tabelka](https://hackmd.io/_uploads/H1Iuwy_-A.png)

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.

![image](https://hackmd.io/_uploads/SJ4hdRDWC.png)
:::

## Zadanie 3
:::success
Autor: 	Hanna Laszkiewicz	
![obraz](https://hackmd.io/_uploads/r1mWmeObA.png)
![obraz](https://hackmd.io/_uploads/Sk1KwyOZR.png)
![obraz](https://hackmd.io/_uploads/By6YPkd-R.png)

:::

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

![4.1](https://hackmd.io/_uploads/BJioPk_W0.jpg)


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

![image](https://hackmd.io/_uploads/Sy98ZrfQC.png)
![image](https://hackmd.io/_uploads/BkboWNMXC.png)

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

![image](https://hackmd.io/_uploads/Sy98ZrfQC.png)
![image](https://hackmd.io/_uploads/H1sSWrfmA.png)

| 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	
![Zrzut ekranu 2024-04-25 o 14.31.23](https://hackmd.io/_uploads/HyYmTav-C.png)

## 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
![image](https://hackmd.io/_uploads/ryHvzyOWR.png)


## Procesor z BTB

![image](https://hackmd.io/_uploads/BkInXydWR.png)

![image](https://hackmd.io/_uploads/B1EeSyu-A.png)
**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

![image](https://hackmd.io/_uploads/Bkdxu1O-A.png)


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

:::

## Zadanie 7
:::success
Autor: 	Hanna Laszkiewicz
![obraz](https://hackmd.io/_uploads/r1XhDku-C.png)
![obraz](https://hackmd.io/_uploads/S1A2DJO-C.png)
![obraz](https://hackmd.io/_uploads/rkCk_kd-A.png)
![obraz](https://hackmd.io/_uploads/B1EZ_1ubC.png)
:::

