# Ćwiczenia 7, grupa śr. 10-12, 12 kwietnia 2023

###### tags: `SYK23` `ć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 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk | x | x | x | x | | x | | |
Mikołaj Dworszczak | | | | | | | | |
Kacper Jóźwiak | | | X | X | | | | |
Dominik Kiełbowicz | | | | | | | | |
Michał Kolasa | | | | | | | | |
Konrad Kowalczyk | | | | | | | | |
Oskar Kropielnicki | X | X | X | X | | | | |
Anna Krysta | X | X | X | X | | X | X | X |
Jakub Krzyżowski | X | | | | | | | |
Oskar Kubkowski | X | | | | | | | |
Mateusz Mazur | X | | X | | | | | |
Barbara Moczulska | X | X | X | X | | | | |
Kacper Sojda | X | | X | X | | | | |
Marta Strzelec | x | | | | | | | |
Mikołaj Swoboda | X | X | X | | | | | |
Filip Szczepański | | | | | | | | |
Julian Włodarek | | | | | | | | |
Beata Łakoma | X | X | X | X | | | | |
Michał Łukasik | X | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Mikołaj Swoboda
:::
Bufor predykcji skoków to mała pamięć indeksowana dolnymi bitami adresu instrukcji skoku. Sprawdzamy jego zawartość w fazie *instruction fetch*. Decyduje ona o tym, jakie instrukcje będziemy dalej sprowadzać w potoku, przynajmniej zanim faktycznie obliczymy warunek.

Bufor jednobitowy przechowuje informację o tym, czy dany skok został ostatnio wykonany -- jeśli tak, to przewidujemy, że zostanie wykonany ponownie. W buforze dwubitowym komórka ma cztery stany, interpretowane jak na poniższym diagramie.

          11                    10                    01                    00


L1:     ...            (* pobiera i wypisuje dane *)
(1)     if b goto End  (* sprawdza, czy należy zakończyć pracę *)
        ...
        t0 := 0        (* oblicza długość stringa i wraca do góry *)
LBody:  t1 := s[t0]
(2)     if t1 = 0 goto L1 
        t0 := t0 + 1 
        goto LBody
End:    ...

Predyktor statyczny będzie zawsze przewidywać skok (2), ponieważ jest to skok w górę, jednak występuje on wyłącznie przy wyjściu z pętli. Można przypuścić, że program będzie operował na łańcuchach o długości średnio większej niż 1, stąd większość skoków zostanie źle przewidzianych. Przy predyktorze z dwubitowym buforem skok (2) zostanie błędnie przewidziany tylko przy napotkaniu zera -- będziemy cały czas spodziewać się, że skok się nie wykona. Przy skoku (1) oba predyktory zachowają się tak samo, to znaczy przewidzą go błędnie dopiero przy zakończeniu programu.

Bity potrzebne do funkcjonowania predyktora dwubitowego można przechowywać przy bloku w pamięci podręcznej instrukcji, pobierając je razem z nią, lub jako osobną małą pamięć, do której zagląda się w fazie IF.

To uogólnia się do predyktora *n*-bitowego następująco:
* jeśli nie wykonano skoku, dekrementuj licznik;
* jeśli wykonano skok, inkrementuj licznik;
* jedynka w najwyższym bicie oznacza „wykonać skok”, zero -- „nie wykonywać”.

## Zadanie 2
:::success
Autor: Beata Łakoma
:::


Motywacja:
W wielu sytuacjach wykonanie skoku jest zależne od tego czy w poprzednie skoki zostały wykonane. Lokalny predyktor nie jest wstanie uchwycić tego zachowania ponieważ opiera się na pojedynczej gałęzi.

kod:

ogólna struktura:
(m,n) - predyktor korzystając z historii ostatnich m branchy wybiera z 2^m n-bitowych predyktorów. Predyktor 2-bitowy to (0,2).
gshare:

xor aktualnego skoku i ostatnich branchy indeksuje 2-bitowe predyktory w tablicy. Historia branchy jest trzymana jako branch-shift registry by oszeczędzić na pamieci.
## Zadanie 3
:::success
Autor: Mateusz Biłyk
:::
Predyktory turniejowe to predyktory, które łączą globalne i lokalne predyktory. Można te predyktory połączyć dwu bitowym selektorem to znaczy jeżeli dwa razy źle zgadniemy pod rzad to zmieniamy predyktor z globalnego na lokalny i na odwrót. Zauważmy, że podczas błędnej predykcji musimy zmienić selektor oraz lokalny lub globalny predyktor.
## Zadanie 4
:::success
Autor: Kacper Sojda
:::

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

## Zadanie 6
:::success
Autor: Mateusz Biłyk
:::
Tak można go przekształcić w taki sposób, że będzie wymagał nawet tylko jednego sumatora RCA. Musimy mieć rejestry, aby móc przechowywać kolejne bity naszych liczb a oraz b. Na początku dostajemy "PC" czyli numer cyklu jaki się właśnie wykonuje. Dzięki temu wiemy jakie bity liczby a oraz b mamy pobrać z rejestrów na przykład jeżeli RCA jest k bitowy a numer cyklu to n to musimy pobrać bity o numerach $nk,nk+1,...,nk+k-1$. Następnie obliczamy ich sumę sumatorem RCA, produkujemy cztery bity wyniku, a carry-out podłączamy z wyjścia RCA do wejścia, aby mógł przydać się w następnym cyklu.

## Zadanie 7
:::success
Autor: Anna Krysta
:::

## Zadanie 8
:::success
Autor: Anna Krysta
:::