# Lista 11 (20.05.2021), grupa pwit

###### tags: `ask21` `ć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!**

Tabelka zawiera tylko osoby zapisane do grupy.

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
|Wojciech Adamiec | X | X | X | X | X | | X | |
|Kacper Bajkiewicz | X |==X==| X | X | X | | | |
|Bartłomiej Hildebrandt| X | X | X | X | X | X | | |
|Dominik Komła | X | X | X | | X | | X | |
|Aleksandra Kosińska | X | X | X | X | X | | X | |
|Oleś Kulczewicz | X | X | | | X | | X | |
|Damian Lukas | X | X | X | | X | | X | |
|Michał Mikołajczyk | X | X | X | X | X | | X | |
|Mateusz Opala | X | X | X | | X | X | X | |
|Łukasz Orawiec | X | X | | | X | X | X | |
|Szymon Pielat | X | X | X | X | X | | X | |
|Łukasz Pluta | X | X | X | | X | X | X | |
|Kamil Puchacz | X | X | X | X | X | | X | |
|Magdalena Rzepka | X | X | X | X | X | | | |
|Cezary Stajszczyk | X | X | X | X | X | | X | |
|Jakub Szajner |==X==| X | X | X | X | | X | |
|Bartosz Troszka | ==X== | X | | | X | | X | |
|Miłosz Urbanik | X | X | X | X | X | X | X | |

:::

## Zadanie 1
:::info
Autor: Bartosz Troszka
:::

Pamięć podręczna z mapowaniem bezpośrednim - pamięć podręczna taka że w każdym zbiorze $S$ znajduje się tylko jedna linia $E$ (a więc $E=1$).

offset zapisywany jest na 5 bitach. Jego maksymalna wartość to 31 ($11111_2$). Więc blok ma 32 bajty.

Aby otrzymać liczbę wierszy, musimy spojrzeć na to, jakie indeksy są możliwe do uzyskania. Wiemy że index zapisywany jest na 5 bitach, także możemy otrzymać liczby od 0 do 31 (jest ich w sumie 32). Także liczba wierszy w pamięci podręcznej będzie wynosiła 32.

Na metadane składa się tag (22 bity) oraz bit valid. Dane przechowywane są na $8*32=256$ bitach. Także stosunek metadanych do liczby wszystkich bitów wynosi

$$\frac{23}{256 + 23} = 0,0825$$
## Zadanie 2
:::info
Autor: Oleś Kulczewicz
:::

Pamięć podręczna ma organizację sekcyjno-skojarzeniową o dwuelementowych zbiorach, w której każdy zbiór ma $2$ wiersze, blok ma $4$ bajty, a szerokość szyny adresowej wynosi $12$ bitów

Skoro blok zajmuje $4$ bajty, to $B = 4 = 2^b$, zatem $b = 2$, to offset będzie na bitach $a_1, a_0$. Indeksy w naszej pamięci są z zakresu od $0$ do $3$, a więc można je przedstawić na dwóch bitach, zatem będą na bitach $a_3, a_2$. Pozostałe bity będą zarezerwowane na tag.

| $a_{11}$ | $a_{10}$ | $a_9$ | $a_8$ | $a_7$ | $a_6$ | $a_5$ | $a_4$ | $a_3$ | $a_2$ | $a_1$ | $a_0$ |
|:--------:|:--------:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:------:|:------:|
| tag | tag | tag | tag | tag | tag | tag | tag | index | index | offset | offset |

Aby sprawdzić, czy operacja na danym adresie wygeneruje trafienie lub chybienie, możemy zmienić adresy na system binarny, oraz porównać dane z tabelką.

Znacznik `83` pokrywa się w pierwszych dwóch adresach, sprawdzamy zatem wartość ostatniej cyfry w systemie szesnastkowym. W pierwszym przypadku $2_{16} = 0010_{2}$, a więc sprawdzamy pierwszy zbiór (o indeksie $0$), a następnie wybieramy blok z przesunięciem $10_{2}$, czyli B2. Otrzymujemy wartość `0xCC`. Drugi adres jest w zbiorze o indeksie $1$, jednak nie ma tam żadnej wartości, więc dostajemy chybienie. Ostatnim adresem jest `0xFFD`, jest to zbiór o indeksie $3$, znaczniku `0xFF` i przesunięciu $01_{2}$ (blok B1), a więc mamy trafienie w wartość `0xC0`.

| hex address | binary address | Trafienie? | Wartość |
|:-----------:|:----------------:|:----------:|:-------:|
| `0x832` | `1000 0011 0010` | Tak | `0xCC` |
| `0x835` | `1000 0011 0101` | Nie | $-$ |
| `0xFFD` | `1111 1111 1101` | Tak | `0xC0` |

## Zadanie 3
:::info
Autor: Damian Lukas
:::

Rozważmy pamięć podręczną z poprzedniego zadania. Mamy następującą sekwencję odwołań do czterobajtowych słów pamięci o adresach zadanych liczbami w systemie szesnastkowym:

      0x000 0x004 0x010 0x084 0x03C 0x0E8 0xC8C 0x0A0 0x004 0x400 0x084 0x010 0x0E8 0x884 0xC8C 0x000

Załóż, że na początku pamięć podręczna jest pusta. Polityka wymiany to NRU (ang. Not Recently
Used).
* Podaj liczbę wierszy zastąpionych w wyniku chybienia wywołanego konfliktem (ang. conflict miss).
* Ile chybień było przymusowych (ang. compulsory miss)?
* Jaka jest efektywność pamięci podręcznej (ang. hit ratio)?
* Podaj w postaci tabelki (ale bez danych bloku) zawartość pamięci podręcznej po wykonaniu powyższych odwołań.
* Na każdy zbiór podaj kolejnego kandydata na ofiarę (ang. victim).
* Ile bitów na zbiór potrzebujesz na przechowanie informacji o tym jak wyznaczyć następną ofiarę?

| # | Adres | Tag | Set | Offset | Trafienie? | Zastąpiony? |
|:---:|:-------:|:----:|:---:|:------:|:----------:|:-----------:|
| 1 | `0x000` | `00` | `0` | `0` | Compulsory miss | Tak|
| 2 | `0x004` | `00` | `1` | `0` | Compulsory miss | Tak|
| 3 | `0x010` | `01` | `0` | `0` | Compulsory miss | Tak|
| 4 | `0x084` | `08` | `1` | `0` | Compulsory miss | Tak|
| 5 | `0x03C` | `03` | `3` | `0` | Compulsory miss | Tak|
| 6 | `0x0E8` | `0E` | `2` | `0` | Compulsory miss | Tak|
| 7 | `0xC8C` | `C8` | `3` | `0` | Compulsory miss | Tak|
| 8 | `0x0A0` | `0A` | `0` | `0` | Conflict miss | Tak|
| 9 | `0x004` | `00` | `1` | `0` | Hit | Nie|
| 10 | `0x400` | `40` | `0` | `0` | Conflict miss | Tak|
| 11 | `0x084` | `08` | `1` | `0` | Hit | Nie|
| 12 | `0x010` | `01` | `0` | `0` | Conflict miss | Tak|
| 13 | `0x0E8` | `0E` | `2` | `0` | Hit | Nie|
| 14 | `0x884` | `88` | `1` | `0` | Conflict miss | Tak|
| 15 | `0xC8C` | `C8` | `3` | `0` | Hit | Nie|
| 16 | `0x000` | `00` | `0` | `0` | Conflict miss | Tak|

Efektywność pamięci podręcznej wynosi 4/16 -> 1/4 -> 25%

Tabela zawartości pamieci podrecznej:

| Set | Tag | Victim | Valid |
|:---:|:-------:|:------:|:-------:|
| `0` | `01` | `1` | `1` |
| `0` | `00` | `0` | `1` |
| `1` | `88` | `0` | `1` |
| `1` | `08` | `1` | `1` |
| `2` | `0E` | `0` | `1` |
| `2` | `--` | `1` | `0` |
| `3` | `03` | `0` | `1` |
| `3` | `C8` | `1` | `1` |

## Zadanie 4
:::info
Autor: Aleksandra Kosińska
:::

Adresy: `0 4 10 84 3c e8 c8c a0 4 400 84 10 e8 884 c8c 0`

| # | Adres | Tag |Offset| Trafienie? | Zastąpiony? |
|:--:|:------:|:------------:|:----:|:----------:|:------------:|
| 1 | 0x000 | 0000 0000 00 | 00 | compulsary miss | tak |
| 2 | 0x004 | 0000 0000 01 | 00 | compulsary miss | tak |
| 3 | 0x010 | 0000 0001 00 | 00 | compulsory miss | tak |
| 4 | 0x084 | 0000 1000 01 | 00 | compulsory miss | tak |
| 5 | 0x03C | 0000 0011 11 | 00 | compulsory miss | tak |
| 6 | 0x0E8 | 0000 1110 10 | 00 | compulsory miss | tak |
| 7 | 0xC8C | 1100 1000 11 | 00 | compulsory miss | tak |
| 8 | 0x0A0 | 0000 1010 00 | 00 | compulsory miss | tak |
| 9 | 0x004 | 0000 0000 01 | 00 | hit | nie |
| 10 | 0x400 | 0100 0000 00 | 00 | compulsory miss | tak|
| 11 | 0x084 | 0000 1000 01 | 00 | hit | nie |
| 12 | 0x010 | 0000 0001 00 | 00 | hit | nie |
| 13 | 0x0E8 | 0000 1110 10 | 00 | hit | nie |
| 14 | 0x884 | 1000 1000 01 | 00 | compulsory miss | tak |
| 15 | 0xC8C | 1100 1000 11 | 00 | hit | nie |
| 16 | 0x000 | 0000 0000 00 | 00 | conflict miss | tak |

| Age | Znacznik | Tag | Valid |
|:---:|:--------:|:-----:|:---:|
| 4 | 0x400 | 0100 0000 00 | 1 |
| 5 | 0x004 | 0000 0000 01 | 1 |
| 2 | 0x010 | 0000 0001 00 | 1 |
| 3 | 0x084 | 0000 1000 01 | 1 |
| 0 | 0x884 | 1000 1000 01 | 1 |
| 1 | 0x0E8 | 0000 1110 10 | 1 |
| 7 | 0xC8C | 1100 1000 11 | 1 |
| 6 | 0x0A0 | 0000 1010 00 | 1 |

## Zadanie 5
:::info
Autor: Kacper Bajkiewicz
:::

Index bits w środku:

Index bits na początku:


1. Umożliwia to rozsianie danych z jednego zbioru po pamięci, przez co ograniczamy ryzyko konfliktu, poprawia się wydajność i mniejsza szansa jest na to, że przypadkiem nadpiszemy dane (bo bliskie indeksy będą w różnych zbiorach)

https://en.wikipedia.org/wiki/Harvard_architecture

https://stackoverflow.com/questions/55752699/what-does-a-split-cache-means-and-how-is-it-usefulif-it-is

https://softwareengineering.stackexchange.com/questions/44731/why-are-there-separate-l1-caches-for-data-and-instructions

2. Rozdzielenie tych zbiorów pozwoli na zrównoleglenie operacji dostępu do pamięci i optymalizację typów tych danych. Do tego instruction cache będzie mógł znajdować się bliżej jednostki instrukcji a data cache będzie mógł znajdować się bliżej jednostki pamięci, co zredukuje czasy przepływu informacji. Do tego informacje o instrukcjach są trochę inne niż dane, mogą mieć informacje np. o następnej instrukcji. Instruction cache zajmuje się tylko poleceniami odczytu w przeciwieństwie do data cache który obsługuje też operacje zapisu.

## Zadanie 6
:::info
Autor: Łukasz Orawiec
:::

**Write-back** -- po tym jak wartość słowa w pamięci podręcznej zostanie zmodyfikowana, propagacja tej zmiany do niższego poziomu w hierarchii pamięci jest odraczana do momentu konieczności usunięcia słowa z pamięci podręcznej.

**Write-allocate** -- w przypadku chybienia odpowiedni blok jest wczytywany z niższego poziomu i aktualizowana jest jego wartość.

<br/>


## Zadanie 7
:::info
Autor: Miłosz Urbanik
:::


- Średni czas dostępu do pamięci przez procesor z pamięcią podręczną L1

$t_{avgL1}= (1 - missRate_{L1})\cdot t_{L1} + missRate_{L1} \cdot (t_{L1} + t_{mobo}) = \\ = (1 - 0.08) \cdot 0.66 + 0.08 \cdot (0.66 + 70) = 6.26ns$

- Średni czas dostępu do pamięci przez procesor z pamięcią podręczną L1 i L2

$$
t_{avgL1+L2} = (1 - missRate_{L1})\cdot t_{L1} + missRate_{L1} \cdot (1 - missRate_{L2}) \cdot (t_{L1} + t_{L2}) + missRate_{L1} \cdot missRate_{L2} \cdot (t_{L1} + t_{L2} + t_{mobo}) =\\ = (1 - 0.08) \cdot 0.66 + 0.08 \cdot (1 - 0.005) \cdot (0.66 + 5.62) + 0.08 \cdot 0.005 \cdot (0.66 + 5.62 + 70) = 1.14ms
$$

- $CPI$ (clocks per instruction) - średnia liczba cykli zegarowych potrzebnych na wykonanie jednej instrukcji

Suma po różnych rodzajach instrukcji (co do liczby cykli potrzebnych na ich wykonanie)

$$
CPI = {\sum noInstructions \cdot cyclesPerInstructionType \over totalNumOfInstructions }
$$

$CPI_{L1} = 0.64 \cdot 1 + 0.36 \cdot (6.22 /0.66) = 4.03 cycles/instruction$

$CPI_{L2 + L1} = 0.64 \cdot 1 + 0.36 \cdot (1.14 / 0.66) = 1.26cycles/instruction$

## Zadanie 8
:::info
Autor:
:::