---
# System prepended metadata

title: 'Ćwiczenia 12, grupa śr. 17-19, 17 maja 2023'
tags: [pwit, ćwiczenia, ASK23]

---

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

![](https://hackmd.io/_uploads/ryufhuiSh.png)
![](https://i.imgur.com/ESQPMwC.png)
![](https://i.imgur.com/xt4dKZO.png)


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	
:::

![](https://hackmd.io/_uploads/HyLi1tjH2.png)
![](https://i.imgur.com/VQspsS0.png)

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

![](https://hackmd.io/_uploads/rJE0F9oS3.png)
![](https://i.imgur.com/kPA05GO.png)

![](https://hackmd.io/_uploads/H1cx95iBh.png)
![](https://i.imgur.com/nKh4s6f.png)
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.

![](https://hackmd.io/_uploads/HJ0v9qsSn.png)
![](https://hackmd.io/_uploads/SkV-3jiHh.png)

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












