---
# System prepended metadata

title: 'Ćwiczenia 8, grupa cz. 12-14, 28. kwietnia 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ć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
![](https://i.imgur.com/QOG1TJY.jpg)

:::

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

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

```
for(){
	do{
		
	}while();
}
```
![](https://i.imgur.com/83kbxfq.png)

![](https://i.imgur.com/55zDRif.png)
![](https://i.imgur.com/jVnXcuQ.png)
![](https://i.imgur.com/qyFryGJ.png)


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

![](https://i.imgur.com/pfvLBeK.png)

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


![](https://i.imgur.com/6WmCmxl.png)


## Przykład kodu

```js
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*.

![](https://i.imgur.com/eUfy3bf.png)



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

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

![](https://i.imgur.com/noJKJoq.png)


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

![](https://i.imgur.com/73nzoJ3.png)

![](https://i.imgur.com/E0HuGhd.png)

Jak wyliczane są tagi:

![](https://i.imgur.com/H4uOZYx.png)


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