---
# System prepended metadata

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

---

# Ćwiczenia 9, grupa cz. 10-12, 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   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Borys Adamiak            |   X   |     |  X   |  X   |     |  X   |     | 
Michał Chawar            |  X    |  X   |  X   |     |     |  X   |  X   |
Julia Cygan              |  X   |  X  |  X  |  X  |     |==X==|     | 
Maciej Dengusiak         |  X   |     |  X  |  X  |     |  X  |     |
Patryk Flama             |      |     |     |     |     |     |     | 
Szymon Fluder            |   X  |  X  |  X  |  X  |     |  X   |     | 
Aleksandra Jędrzejak     |   X   |  X   |  X   |     |     |     |     |
Mikołaj Karapka          |  ==X==    |  X   |  X   | X    |     |  X   |     |
Viktoriia Kashpruk       |  X   |  X   |  X   |   X  |     |  X   | X
Wiktor Małek             |   X   |  X   |  X   |  X   |     |  X   |  X   |
Błażej Molik             |  X   |  X  |  X  |  X  |     |  X  |     | 
Andrzej Morawski         |      |     |     |     |     |     |     | 
Konrad Oleksy            |      |     |     |     |     |     |     | 
Lucjan Pucelak           |  X    |  X   |  ==X==   |  X   |     |  X   |  X   |
Aleksandra Sęk           |      |     |     |     |     |     |     | 
Radosław Śliwiński       |      |     |     |     |     |     |     | 
Piotr Traczyński         |  X    |  X   |  X   |  ==X==   |     |  X   |  X   | 
Katarzyna Trzos          |  X    |     |   X  |  X   |     |  X   |     |
Piotr Warząchowski       |      |     |     |     |     |     |     |
Olga Zaborska            |      |     |     |     |     |     |     | 
:::




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



## Zadanie 1
:::success
Autor: Mikołaj Karapka		
:::
![image](https://hackmd.io/_uploads/SkUNQcP-R.png)


### Bufor predykcji skoków
Bufor predykcji skoków posiada informację czy dana instrukcja warunkowa została wykonana czy też nie.

Jest sprawdzany w fazie **Fetch**, co przekłada się na szybsze wykonanie instrukcji programu występującej bezpośrednio po instrukcji **goto**. 

### Bufor 1-bitowy
- **Not taken** (0)
- **Taken** (1)

### Bufor 2-bitowy
![image](https://hackmd.io/_uploads/BkPRVzvZ0.png)

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

### Zasada działania
W obu przypadkach jeśli skok zostanie wykonany to zwiększamy wartość licznika o $1$, a gdy nie został wykonany to zmniejszamy $1$. 

Predyktor **1-bitowy** myli się przed wyjściem z pętli i po ponownym wejściu do niej, jeśli został już wykonany skok.

Natomiast predyktor **2-bitowy** myli **tylko raz**. Tę róznice jeszcze bardziej widać kiedy mamy zgnieżdżone pętle. 

### Przykład programu 
```
(1) x = n
L1: ...

L2:
  (2)  if(x == 0){
          goto L3
       } else {
            x--
            goto L2
       }
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**.

### Uogólnienie dla n-bitów
Jeżeli wykonano skok
- zwiększ licznik o $1$,
 
wpp. 
- zmniejsz o $1$

$1$ w najbardziej znaczącym bicie oznacza przewidanie skoku, a $0$ przewidywanie braku skoku. Liczba stanów będzie równa $2^n$.

## Zadanie 2
:::success
Autor: 	Wiktor Małek	
:::

![zad_2_m_n_predictor](https://hackmd.io/_uploads/rk4L75vWR.jpg)
  
predyktor $(m, n)$ to predyktor korelujący, który pamięta historię $m$ ostatnich instrukcji skoku, z których każda ma $n$-bitowy predyktor.

![zad_2_gshare](https://hackmd.io/_uploads/Hyivm9PbR.jpg)

W powyższym przykładzie w branch history mamy zapisane dla ostatnich m=10 branchy czy się dany branch wykonał czy nie, dla każdej kombinacji (jest ich 2^m) mamy osobny predyktor dwubitowy(n=2) w kolumnie po prawej.

jest to predyktor, który do indeksowania Branch target buffera używa xora z adresu instrukcji i bitów historii skoków;


## Zadanie 3
:::success
Autor: 	Lucjan Pucelak	 	
:::
![Screenshot 2024-04-25 at 10.23.19](https://hackmd.io/_uploads/H1BzQ5vbA.png)

Globalny predyktor - jest zależny od historii skoków dla całego programu
Lokalny predyktor - jest zależny od skoków konkretnych instrukcji
Turniejowy predyktor - używa kilku predyktorów, zwykle globalnego predyktora i lokalnego predyktora, oraz selektora do wybierania pomiędzy nimi.

![Screenshot 2024-04-25 at 10.23.28](https://hackmd.io/_uploads/H1umm9wbR.png)

Selektor - działa jak 2-bitowy predyktor, gdy dwukrotnie z rzędu wystąpi błędna prognoza to następnym razem wybierzemy inny predyktor. 
Jeżeli wystąpi błędna prognoza to musimy zmienić zarówno tabelę selektora, jak i predyktor, który dokonał nieprawidłowej prognozy.

## Zadanie 4
:::success
Autor: 	Piotr Traczyński	
:::

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

Struktura predyktora TAGE wygląda w taki sposób, że mamy kilka tablic predyktorów.
Pierwsza tablica jest lokalna i indeksowana numerem instrukcji.
Następne tablice korzystają z historii skoków - każda z coraz dłuższej.

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

Każda z tych tablic jest indeksowana tag-iem, który jest kilkoma ostatnimi bitami xor-a adresu i historii (tak jak w gshare). Przez to, że pamiętamy tylko kilka ostatnich bitów (4 - 8) na tag każda z tablic nie jest zbyt duża. 
W każdym z predyktorów sprawdzamy czy mamy wpis z tagiem pasującym do otrzymanego taga i wybieramy ten pasujący z najdłuższą historią - jeśli żaden nie pasuje to korzystamy z lokalnego predyktora.

## Zadanie 5
:::danger
Autor: 	do zadeklarowania następnym razem!
:::

## Zadanie 6
:::success
Autor: 	Julia Cygan	
:::
![image](https://hackmd.io/_uploads/B1-iF2LZA.png)
![Screenshot 2024-04-23 at 20.49.21](https://hackmd.io/_uploads/BkL17tS-R.png)
### Opis:
- Misprediction Penalty: Kara czasowa, która występuje, gdy przewidywany skok okazuje się błędny, wynosi cztery cykle.
- Buffer Miss Penalty: Kara czasowa za niepowodzenie w trafieniu do bufora celów skoków (odwołanie się do nie istniejącej wartości w buforze), wynosi trzy cykle.
- Hit Rate: Odsetek trafień do bufora celów skoków, wynosi 90% (90% skoków warunkowych jest trafionych w buforze).
- Accuracy: Dokładność przewidywania skoków, wynosi 90% (90% przewidywanych skoków jest prawidłowych).
- Branch Frequency: Częstotliwość występowania skoków, wynosi 15% (15% instrukcji to skoki warunkowe).
- Fixed Branch Penalty: Stała kara czasowa za skok, bez względu na jego wynik, wynosi dwa cykle.

### Dla procesora bez bufora:
- Średnia kara za przewidywanie skoku
  `branch frequency * branch penalty = 0,15 * 2 = 0,3`
- Średnia kara za brak trafienia w buforze  = 0 , ze względu na brak bufora do trafień 

### Dla procesora z buforem 

- Średnia kara za brak trafienia w buforze 
  `(Branch Frequency) * (1 - Hit Rate) * Buffer Miss Penalty =
  0.15 * (1 - 0.9) * 3 = 0.045`
- Średnia kara za złe przewidywanie skoku 
  `(Branch Frequency) * Hit Rate * (1 - Accuracy) * Misprediction Penalty =` 
  `0.15 * 0,9 * (1 - 0,9) * 4 = 0,054`
  
Całkowita kara = 0,045 + 0,054 = 0,099

### O ile szybszy jest procesor z buforem względem procesora bez bufora?

Niech `Res` - stosunek procesora z buforem celów skoków w do procesora bez bufora skoków 

`CPI` - procesor bez bufora skoków

`CPI = 1 + 0,3 = 1,3`

`CPI_BTB` - procesor z buforem skoków
`CPI_BTB = 1 + 0,099 = 1,099`

`S = CPI / CPI_BTB = 1,3 / 1,099 = 1,1829`

Zatem procesor z buforem celów skoków jest około 18% szybszy niż procesor bez bufora skoków.


## Zadanie 7
:::success
Autor: 	Michał Chawar	
:::

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

**a.** Zauważmy, że skoro w przypadku instrukcji bezwarunkowej otrzymujemy od razu następną instrukcję po skoku i nie musimy dopiero obliczać adresu, aby w następnym cyklu ją pobrać. Równie dobrze można założyć, że wszystkie bezwarunkowe instrukcje skoku w programie są usunięte, a w ich miejsce przesuwają się docelowe instrukcje po skoku. Stąd otrzymujemy bonus (ujemną karę) w wysokości $1$ cyklu.

**b.** Mamy $1-0,9 = 10\%$ instrukcji skoku (bezwarunkowego), które nie trafiają do bufora celów skoku, i nakładają karę w wysokości $2$ cykli. Stąd na jedną instrukcję w programie przypada $10\% \cdot 5\% \cdot 2 = 0,01$ cyklu kary.

Z drugiej strony, $90\%$ instrukcji skoku (bezwarunkowego) trafia do bufora celów skoku i nakłada bonus w wysokości $1$ cyklu (karę w wysokości $-1$ cyklu), więc mamy $90\% \cdot 5\% \cdot 1 = 0,045$ cyklu bonusu na jedną instrukcję w programie.

Ostatecznie więc przypada $0,045 - 0,01 = 0,035$ cyklu bonusu na instrukcję.

Gdyby procesor nie stosował tej techniki, otrzymalibyśmy tylko pierwszą karę za nietrafianie do bufora, a więc na instrukcję przypadałoby $0,01$ cyklu kary. Porównując szybkości (dla jednego cyklu na wykonanie każdej instrukcji)

$$\frac{1 - 0,035}{1 + 0,01} = \frac{0,965}{1,01} \approx 0,955445$$

otrzymujemy ok. $4,5\%$ przyspieszenia.

Aby odpowiedzieć na ostatnie pytanie, uzależnimy ten stosunek od zmiennej reprezentującej *hit rate*. Oznaczmy ten przez $H$ (oczywiście $0 \leqslant H \leqslant 1$). Mamy więc przyspieszenie $S$ w wielkości

$$S = 1 - \frac{1 + [(1 - H) \cdot 0,05 \cdot 2] - [H \cdot 0,05 \cdot 1]}{1 + [(1 - H) \cdot 0,05 \cdot 2]}=$$$$= 1 - \frac{1 + 0,1 - 0,1H - 0,05H}{1 + 0,1 - 0,1H} = 1 - \frac{1,1 - 0,15H}{1,1 - 0,1H} =$$$$= 1 - \frac{1,1 - 0,1H - 0,05H}{1,1 - 0,1H} = 1 - 1 + \frac{0,05H}{1,1 - 0,1H} =$$$$= \frac{0,05H}{1,1 - 0,1H}$$  

Okazuje się, że przyspieszenie takie wystąpi zawsze (dopiero dla $H=0$ nie ma przyspieszenia). Ustalmy więc, że interesujące nas przyspieszenie to przynajmniej $1\%$.

$$S \geqslant 0,01 \Leftrightarrow \frac{0,05H}{1,1 - 0,1H} \geqslant 0,01$$$$0,05H \geqslant 0,011 - 0,001H$$$$0,051H \geqslant 0,011$$$$H \geqslant 0,2156862... \approx 22\%$$