# Ćwiczenia 8, grupa cz. 12-14, 28. kwietnia 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Daniel Boguszewski | | | | | | |
Adam Ciężkowski | | | | | | |
Jacek Długopolski | x | x | x | x | | |
Jakub Fila | | X | X | X | | |
Krzysztof Grynkiewicz | | | | | | |
Michał Hetnar | x | | | | | |
Hubert Jabłoński | x | x | x | x | x | |
Antoni Kamiński | | | | | | |
Paweł Karaś | X | X | ==X== | X | X | |
Emil Kisielewicz | | x | x | ==x== | x | |
Kacper Komenda | |==X==| X | X | X | |
Filip Komorowski | x | x | x | x | x | x |
Piotr Piesiak | x | x | x | x | x | x |
Artur Krzyżyński | | | | | | |
Patryk Mazur | | | | | | |
Szymon Mleczko | X | X | X | X | | |
Michał Mróz | | | | | | |
Dominik Olejarz | X | X | | | | |
Magdalena Słonińska | | | X | | | |
Oleś Kulczewicz | | X | X | X | | |
Adam Szeruda | X | X | X | X | X | X |
Kamil Tasarz | | | | | | |
Michał Zieliński | | X |==X==| X | X | X |
:::

**Tu można zadeklarować zad. 6. z listy 7.:**

* Adam Szeruda
* Jacek Długopolski <--- wyznaczony autor
* Piotr Piesiak

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

## Zadanie 1
:::success
Autor: Dominik Olejarz

:::

## Zadanie 2
:::success
Autor: Kacper Komenda
:::

Branch-target buffer działa na podstawie poprzedniej sytuacji, to znaczy jeśli wcześniej wzięliśmy skok to znowu weźmie, a jeśli nie to znowu nie weźmie.
W przypadku dwubitowego jest to lepiej rozwiązane, bo w sytuacji gdy prawie zawsze bierze skok, a raz zdarzy się nie wziąć, to potem znowu weźmie.
Może być zaimplementowane jako specjalne "cache" z dostępem w fazie IF lub jako para bitów przyczepiona do każdego bloku cache instrukcji.
Przy uogólnieniu mamy $2^n-1$ wartości i gdy stan to powyżej połowy, to bierzemy, a jeśli poniżej to nie bierzemy, ale zysk według badań nie jest na tyle duży, aby tak robić.

for (int i = 0;i < 10000;i++)
	if ((i / 10) % 2)
		//jakis kod
	else //jakis inny kod

for(){
	do{
		
	}while();
}



## Zadanie 3
:::success
Autor: Paweł Karaś
:::


## Motywacja

Predyktory korelujące są to predyktory, które wykorzystują decyzje podjęte na poprzednich rozgałęzieniach w kodzie.

Przykładowo rozgałęzienie $(1, 2)$ korzysta z decyzji podjętej na poprzednim rozgałęzieniu.

W ogólności rozgałęzienie $(m, n)$ jest takim rozgałęzieniem, które rozważa $m$ poprzednich decyzji predyktórów $n$-bitowych.

### Krótkie omówienie struktury
Okazuje się, że jesteśmy w ten sposób w stanie zwiększyć efektywność predyktora małym kosztem sprzętowym. Koszt ten zawierałby się w stworzeniu $m$-bitowego *shift register*, który przechowywałby ostatnie $m$ podjętych decyzji.

Wyliczanie decyzji w danym rozgałęzieniu sprowadza się do wzięcia pewnych mniejszych bitów oraz ich konkatenacji (tudzież ewaluacji funkcji *haszującej*). Wynik jest indeksem który posłuży nam do wybrania dopowiedniej wartości z *counterów*, czyli tabeli w której przechowujemy stan naszych predyktorów.

| Counters | Comment |
| -------- | ------------------ |
| 00 | Strongly not taken |
| 01 | Weakly not taken |
| 10 | Weakly taken |
| 11 | Strongly taken |
| ... | ... |


## Przykład kodu

if (a == 2) a = 0
if (b == 2) b = 0
if (a != b) ...

Kod trójkowy

IF a != 2 GOTO L1
ADD a, a, 0
L1:
IF b != 2 GOTO L2
ADD b, b, 0
L2:
IF a == b GOTO L3

Zauważmy, że decyzja do podjęcia w ostatnim rozgałęzieniu jest powiązana z powyższymi rozgałęzieniami. Oczywiście jeśli zajdzie `a == 2` oraz `b == 2`, to w tym wypadku nie może zajść `a != b`.

Zwykły 2-bitowy predyktor kodu **nie spełni** ostatniego warunku `a != b` jeśli spełnione były wcześniej dwa powyższe warunki.

## Predyktor `gshare`

W predyktorze gshare index jest ewaluowany poprzez użycie *exclusive or* na adresie aktualnego rozgałęzienia oraz $n$ najwcześniejszych podjętych decyzji (gdzie $n$ to długość adresu).

*Hash* który otrzymamy jest następnie wykorzystany do indeksowania prognozy w naszym 2-bitowym *counterze*.


## Zadanie 4
:::success
Autor: Emil Kisielewicz
:::

Predyktory turniejowe to sposób połączenia ze sobą predyktorów globalnych i lokalnych przy pomocy tablicy *selektora*:


Selektor jest indeksowany adresem instrukcji skoku. Wpis w selektorze do dwubitowy predyktor, który na normalnej zasadzie dwubitowego predyktora decyduje, czy skorzystać z predyktora globalnego czy lokalnego, żeby wywnioskować ostateczną predykcję.

## Zadanie 5
:::success
Autor: Filip Komorowski
:::



Jak wyliczane są tagi:


## Zadanie 6
:::success
Autor: Adam Szeruda
:::

> For this exercise, consider a (1,2) correlating
predictor that can track four branches (requiring 16 bits) versus a (1,2) local pre-
dictor that can track two branches using the same amount of memory. For the fol-
lowing branch outcomes, provide each prediction, the table entry used to make the
prediction, any updates to the table as a result of the prediction, and the final mis-
prediction rate of each predictor. Assume that all branches up to this point have
been taken. Initialize each predictor to the following:

Correlating predictor

| Entry | Branch | Last outcome | Prediction |
| ----- | ------ | ------------ | ------------------------- |
| 0 | 0 | T | T with one misprediction |
| 1 | 0 | NT | NT |
| 2 | 1 | T | NT |
| 3 | 1 | NT | T |
| 4 | 2 | T | T |
| 5 | 2 | NT | T |
| 6 | 3 | T | NT with one misprediction |
| 7 | 3 | NT | NT |

Local predictor

| Entry | Branch | Last 2 outcomes (right is most recent) | Prediction |
| ----- | ------ | -------------------------------------- | ------------------------ |
| 0 | 0 | T,T | T with one misprediction |
| 1 | 0 | T,NT | NT |
| 2 | 0 | NT,T | NT |
| 3 | 0 | NT,NT | T |
| 4 | 1 | T,T | T |
| 5 | 1 | T,NT | T with one misprediction |
| 6 | 1 | NT,T | NT |
| 7 | 1 | NT,NT | NT |

| Branch PC (word address) | Outcome | CP | Update | LP | Update |
| ------------------------ | ------- | ----- | -------- | ----- | -------- |
| 454 (2) | T | 4: T | T → T | 0: T | T1 → T |
| 543 (3) | NT | 6: NT | NT1 → NT | 4: T | T → T1 |
| 777 (1) | NT | 3: T | T → T1 | 5: T | T1 → NT1 |
| 543 (3) | NT | 7: NT | NT → NT | 7: NT | NT → NT |
| 777 (1) | NT | 3: T | T1 → NT1 | 7: NT | NT → NT |
| 454 (2) | T | 5: T | T → T | 3: T | T → T |
| 777 (1) | NT | 2: NT | NT → NT | 6: NT | NT → NT |
| 454 (2) | T | 5: T | T → T | 1: NT | NT → NT1 |
| 543 (3) | T | 6: NT | NT → NT1 | 6: NT | NT → NT1 |

CP misprediction rate: 3/9
LP misprediction rate: 4/9