# Ćwiczenia 12, grupa śr. 17-19, 17 maja 2023

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

:::success
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- |
| Kamila Goszcz | X | X | X | | X | | X | |
| Mateusz Materek | X | X |==X==| X | X | | X | |
:::

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

## Zadanie 1
:::success
Autor: Kamila Goszcz
:::


Rozmiar bloku B:
$2^b = 2^5 = 32$,
Oznacza to, że blok ma 32 bajty tj. osiem 32-bitowych słów

Liczba wierszy pamięci podręcznej S:
$2^s = 2^5 = 32$

Stosunek liczby bitów składających metadane do liczby wszystkich bitów:
(valid + tag) / (valid + tag + data)
$(22+1)/((22+1))+256) = 23/279$

## Zadanie 2
:::success
Autor: Kamila Goszcz
:::


Skoro blok zajmuje 4 bajty, to $B=4=2^b$, zatem b=2
Indeksy w naszej pamięci są z zakresu [0, 3], a więc można je przedstawić na 2 bitach. Pozostałe bity będą zarezerwowane na tag.

Struktura adresu: $\color{red}{01234567}\color{lightblue}{01}\color{green}{01}$

832 => tag = $83_{16}$ set = $0_{16}$ off = $2$
HIT CC

835 => tag = $83_{16}$ set = $1_{16}$ off = $1$
MISS --

FFD => tag = $FF_{16}$ set = $3_{16}$ off = $1$
HIT C0

0x4A: `tag = 00, set = 2, off = 2` -> 00A

## Zadanie 3
:::success
Autor: Mateusz Materek
:::
:::info
**Polityka wymiany** -> sposób podejmowania decyzji, który z bloków w cache'u $k$-tego poziomu zastąpić, gdy sprowadzamy blok z $k+1$-wszego poziomu.
**Ofiara** -> blok, który zostanie zastąpiony innym blokiem, sprowadzonym z pamięci podręcznej niższego poziomu.
**Conflict miss** -> pamięć podręczna jest wystarczająco duża, aby trzymać bloki, ale polityka wymiany/mapowania jest tak skonstruowana, że dwa bloki rywalizują o to samo miejsce.
**Compulsory miss** -> chybienie wywołane występowaniem pustego miejsca w pamięci podręcznej.
:::

| # | Adress | Tag | Idx | Offset | Hit? | Replace? |
|:----:|:--------:|:----:|:---:|:------:|:---------------:|:---------:|
| 1 | `0x00 0` | `00` | `0` | `0` | Compulsory miss | Y |
| 2 | `0x00 4` | `00` | `1` | `0` | Compulsory miss | Y |
| 3 | `0x01 0` | `01` | `0` | `0` | Compulsory miss | Y |
| 4 | `0x08 4` | `08` | `1` | `0` | Compulsory miss | Y |
| 5 | `0x03 C` | `03` | `3` | `0` | Compulsory miss | Y |
| 6 | `0x0E 8` | `0E` | `2` | `0` | Compulsory miss | Y |
| 7 | `0xC8 C` | `C8` | `3` | `0` | Compulsory miss | Y |
| 8 | `0x0A 0` | `0A` | `0` | `0` | Conflict miss | Y |
| 9 | `0x00 4` | `00` | `1` | `0` | Hit | N |
| 10 | `0x40 0` | `40` | `0` | `0` | Conflict miss | Y |
| 11 | `0x08 4` | `08` | `1` | `0` | Hit | N |
| 12 | `0x01 0` | `01` | `0` | `0` | Conflict miss | Y |
| 13 | `0x0E 8` | `0E` | `2` | `0` | Hit | N |
| 14 | `0x88 4` | `88` | `1` | `0` | Conflict miss | Y |
| 15 | `0xC8 C` | `C8` | `3` | `0` | Hit | N |
| 16 | `0x00 0` | `00` | `0` | `0` | Conflict miss | Y |

\# Compulsory misses: **7**
\# Conflict misses: **5**
\# Hits: **4**
Efektywność pamięci podręcznej: 4 trafienia / 16 strzałów = 25%

Zawartość pamięci podręcznej:

| Idx | 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` |

W każdym wierszu wystarczy mieć jeden bit mówiący o statusie ofiary.
(ponieważ tu mamy tylko dwa wiersze na zestaw, to wystarczy mieć jeden bit na zestaw)

## Zadanie 4
:::success
Autor: Mateusz Materek
:::
| # | Adress$_{16}$ | Tag$_2$ | Offset$_2$ | Hit? | Replace? |
|:---:|:-------------:|:--------------:|:----------:|:-----------------:|:--------:|
| 1 | `0x000` | `0000 0000 00` | `00` | Compulsory miss | Y |
| 2 | `0x004` | `0000 0000 01` | `00` | Compulsory miss | Y |
| 3 | `0x010` | `0000 0001 00` | `00` | Compulsory miss | Y |
| 4 | `0x084` | `0000 1000 01` | `00` | Compulsory miss | Y |
| 5 | `0x03C` | `0000 0011 11` | `00` | Compulsory miss | Y |
| 6 | `0x0E8` | `0000 1110 10` | `00` | Compulsory miss | Y |
| 7 | `0xC8C` | `1100 1000 11` | `00` | Compulsory miss | Y |
| 8 | `0x0A0` | `0000 1010 00` | `00` | Compulsory miss | Y |
| 9 | `0x004` | `0000 0000 01` | `00` | Hit | N |
| 10 | `0x400` | `0100 0000 00` | `00` | Conflict miss | Y |
| 11 | `0x084` | `0000 0100 01` | `00` | Hit | N |
| 12 | `0x010` | `0000 0001 00` | `00` | Hit | N |
| 13 | `0x0E8` | `0000 1110 10` | `00` | Hit | N |
| 14 | `0x884` | `1000 1000 01` | `00` | Conflict miss | Y |
| 15 | `0xC8C` | `1100 1000 11` | `00` | Hit | N |
| 16 | `0x000` | `0000 0000 00` | `00` | Conflict miss | Y |

\# Compulsory misses: **8**
\# Conflict misses: **3**
\# Hits: **5**
Efektywność pamięci podręcznej: 5 trafień / 16 strzałów = 31,25%

Zawartość pamięci podręcznej:

| LRU | Adress | Valid |
|:---:|:------:|:-----:|
| 0 | 0x000 | 1 |
| 1 | 0xC8C | 1 |
| 2 | 0x884 | 1 |
| 3 | 0x0E8 | 1 |
| 4 | 0x010 | 1 |
| 5 | 0x084 | 1 |
| 6 | 0x400 | 1 |
| 7 | 0x004 | 1 |

(większa liczba LRU = dawniej używany)
Na każdy blok pamiętamy LRU (na 3 bitach): 3*8 = 24b

## Zadanie 5
:::success
Autor: Kamila Goszcz
:::


Pamięć podręczna L1 jest podzielona na pamięć przeznaczoną dla danych **(d-cache)** oraz instrukcji **(i-cache)**. Taki podział powstał ze względu na to, że w ogólności te dwie rzeczy są od siebie różne: cache instrukcji oprócz swoich danych przechowuje również przypisy o np. miejscu rozpoczęcia kolejnej instrukcji.

Innym powodem jest zwiększenie przepustowości. Nowoczesne procesory mogą jednocześnie odczytywać dane z cache'u instrukcji oraz danych, a więc wykonują dwa odczyty i jeden zapis w cyklu.

Ponad to cache instrukcji tylko odczytuje dane, a cache danych może je zapisywać i odczytywać co pozwala uprościć budowę obwodu.


- Pamięć operacyjną (RAM): W trybie write-through, każda operacja zapisu do pamięci operacyjnej powinna być natychmiast zapisywana w pamięci fizycznej. System operacyjny musi skonfigurować tę funkcję, aby zapewnić spójność danych między pamięcią operacyjną a pamięcią fizyczną.

- Bufor dysku: Bufor dysku służy do tymczasowego przechowywania danych przed zapisaniem ich na fizyczny dysk twardy. W trybie write-through, system operacyjny musi skonfigurować bufor dysku w taki sposób, żeby każdy zapis do bufora był od razu zapisywany na dysku, aby uniknąć utraty danych w przypadku awarii systemu.

- Bufor pamięci podręcznej procesora: Pamięć podręczna procesora jest wykorzystywana do przechowywania często używanych danych, aby przyspieszyć dostęp do nich przez procesor. W trybie write-through, system operacyjny musi skonfigurować pamięć podręczną procesora w taki sposób, żeby każda operacja zapisu była od razu propagowana do pamięci podręcznej i dalej do pamięci operacyjnej i fizycznej.

## Zadanie 6
:::danger
Autor:
:::

## Zadanie 7
:::success
Autor: Mateusz Materek
:::
:::info
**CPI** -> średnia liczba cykli potrzebna do wykonania 1 instrukcji.
:::

| Pamięć | Czas dostępu [ns] | % chybień |
|:------:|:-----------------:|:---------:|
| L1 | 0,66 (1 cykl) | 8% |
| L2 | 5,62 | 0.5% |
| RAM | 70 | 0% |

- Średni czas dostępu - tylko L1:
$AT_{avg} = 0,66\text{ ns} + 8\% \cdot 70\text{ ns} = 6,26\text{ ns}$
- Średni czas dostępu - L1 i L2:
$AT_{avg} = 0,66\text{ ns} + 8\% \cdot (5,62ns + 0,005 \cdot 70\text{ ns}) = 1,14\text{ ns}$
- CPI - tylko L1:
$CPI = (64\% \cdot 0,66\text{ ns} + 36\% \cdot 6,26\text{ ns})\frac{1\text{ cykl}}{0,66\text{ ns}} = 4,05\text{ cykli}$
- CPI - L1 i L2:
$CPI = (64\% \cdot 0,66\text{ ns} + 36\% \cdot 1,14\text{ ns})\frac{1\text{ cykl}}{0,66\text{ ns}} = 1,26\text{ cykli}$

## Zadanie 8
:::danger
Autor:
:::

update(st1, line) -> st2

update("1 2 3 4", 3) -> "3 1 2 4"

"1 2 3 4" -> 13
"3 1 2 4" -> 6

update(13, 3) -> 6

update(1011b, 11b) -> 0110b

update(x1, x2, x3, x4, x5, x6) -> (y1,y2,y3,y4) 


update1(x1, x2, x3, x4, x5, x6) -> y1 
.
.
.
update4(x1, x2, x3, x4, x5, x6) -> y4