---
# System prepended metadata

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

---

# Ćwiczenia 8, grupa cz. 14-16, 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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Kamil Banaś              |       |     |     |     |     |     | 
Mateusz Burdyna          |       |     |     |     |     |     |
Dariusz Ciesielski       |       |    |     |     |     |     |
Dawid Dudek              |==X== | X   | X   |  X  | X   |     |
Mikołaj Dworszczak       |       |     |     |     |     |     |
Przemysław Grochal       |   X   |  X  |  X  |  X  |  X  |     |
Adam Jarząbek            |   X    |   X  |  ==X==   |  X   |     |     |
Anna Karykowska          |   X   |  X  |  X  |  X  |     |     |
Oleś Kulczewicz          |       |     |     |     |     |     |
Pola Marciniak           |       |     |     |     |     |     |
Mikołaj Mroziuk          |       |     |     |     |     |     |
Marcelina Oset           |   X   |  X  |  X  |     |     |     |
Natalia Piasta           |       |     |     |     |     |     |
Krzysztof Piekarczyk     |   X    |  X   |  X   |  X   |     |     |
Marcin Płaza             |       |     |     |     |     |     |
Paweł Richert            |       |     |     |     |     |     |
Rafał Starypan           |   X    |  X   |  X   |  X   |     |     |
Dawid Strojek            |       |  X  |  X  |  X  |  X  |     |
Mateusz Suszek           |       |     |     |     |     |     |
Wojciech Śniady          |       |     |     |  ==X==  |  X   |     | 
Volha Tsekalo            |       |     |     | X    |     |     |
Yana Vashkevich          |       |     |     |     |     |     |
Konrad Woźniak           |       |     |     |  X  |     |     |
Natalia Czerep           |       |     |     |     |     |     |
Joanna Stachowicz        |       |     |     |     |     |     |
:::





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




## Zadanie 1
:::success
Autor: Dawid Dudek
:::


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


Potrzebujemy rozdzielić **execution** od jego **completion**
Aby to uzyskać dodajemy fazę **commit**. Na tej fazie będziemy kontrolować kolejność. 

Reoder buffer będzie nam trzymał wyniki pomiędzy **completion** a **commit**

Idea:
1. Pobieramy instrukcje sekwencyjnie
2. Wykonujemy out of order
3. Commitujemy sekwencyjnie

https://taoxie.sdsu.edu/cs572/Lec22.pdf


## Zadanie 2
:::success
Autor: Krzysztof Piekarczyk

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


Branch-target buffer opiera się na wyniku poprzedniej sytuacji, jeśli został wykonany skok, to ponownie go wykonamy, w przeciwnym wypadku nie.

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


Predyktor 2-bitowy przewiduje skok na podstawie swojego stanu. Wykorzystujemy tu obserwację, że jeżeli prawie zawsze był wykonywany skok, to prawdopodobnie też zostanie wykonany skok, ale jeżeli nie, to niewiele się zmieni i predyktor będzie przewidywał, że dalej będziemy skakać. Dopiero przy dostatecznie dużej liczbie pomyłek predyktor będzie inaczej przewidywał.
Może to zostać zaimplementowane jako 2 bity podczepione do bloku instrukcji.

Łatwo to roszerzyć na n-bitów i gdy stan tych n-bitów będzie powyżej połowy to przewidujemy skok, a jak nie to nie.

for (int i = 1; i < 17, i++)
    if (i < 8)
        //sth
    else
        //sth

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

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


:::

## Zadanie 3
:::success
Autor: Adam Jarząbek
:::
Predykatory 2 - bitowe używają jedynie ostatnich informacji o zachowaniu pojedynczej gałęzi. Czasami chcielibyśmy skorzystać z informacji o zachowaniu innych gałęzi.

Przykład programu, dla którego predykator korelujący daje lepsze wyniki:

```
if (aa==2)
    aa=0;
if (bb==2)
    bb=0;
if (aa!=bb) {...
```

W tym przykładzie widać, że wzięcie trzeciej gałęzi zależy od tego, czy dwie poprzednie zostały wzięte.

W ogólności predykator korelujący (m, n) używa informacji o zachowaniu $m$ gałęzi i wybiera jeden z $2^m$ predykatorów, z którego każdy jest $n$ - bitowym predykatorem pojedynczej gałęzi.

## Zadanie 4
:::success
Autor: Wojciech Śniady
:::
![](https://i.imgur.com/XtALt2f.png)
![](https://i.imgur.com/bTP5a67.png)


## Zadanie 5
:::success
Autor: Dawid Strojek
:::

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

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

T0 to nasza bazowa tablica predyktorów bez tagów.

T1, T2, ..., Tn to tablice predyktorów z tagami i 2-bitowym polem "u" (który mówi czy predykcja była użyta niedawno), gdzie do Ti dostajemy się za pomocą hasha korzystającego z historii i ostatnich gałęzi oraz PC.

Predyktory w tablicach mogą być 2-bitowe, w praktyce 3-bitowe sprawdzają się lepiej.

Ostateczna predykcja, to predykcja o najdłuższej historii, która także dopasowała się do taga.

## Zadanie 6
:::success
Autor: Krzysztof Piekarczyk
:::
![](https://i.imgur.com/4KRDwyb.png)



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



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



CP_missrate = 3/9
LP_missrate = 4/9

PS. Przepraszam za mały obrazek, ale nie wiem jak go bardziej powiększyć, jakby ktoś potrzebował, to mogę podesłać oryginał.