---
# System prepended metadata

title: 'Ćwiczenia 9, grupa śr. 12-14, 24 kwietnia 2024'
tags: [pwit, ćwiczenia, SYK24]

---

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


![image](https://hackmd.io/_uploads/By-yblSb0.png)

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

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

## Zadanie 3
:::success
Autor: Adam Majchrowski
![image](https://hackmd.io/_uploads/H1sCaUIZR.png)
![image](https://hackmd.io/_uploads/ryJe088-A.png)
![image](https://hackmd.io/_uploads/BkuGAIUbR.png)
link o którym wspominałem:
https://www.youtube.com/watch?v=-T8yDJ8vTuI
:::

## Zadanie 4
:::success
Autor: Jakub Jankowski
![image](https://hackmd.io/_uploads/S1wpT8Lb0.png)

:::

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

## Zadanie 6
:::success
Autor: Jakub Jankowski	
![image](https://hackmd.io/_uploads/SJV6-0_f0.png)
![image](https://hackmd.io/_uploads/Sy7AbCuzR.png)
![image](https://hackmd.io/_uploads/SkOyG0_fA.png)

:::

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


