---
# System prepended metadata

title: 'Lista 11 (20.05.2021), grupa pwit'
tags: [pwit, ask21, ćwiczenia]

---

# 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
:::
![](https://i.imgur.com/iClBXtx.png)


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:
![](https://i.imgur.com/fgg96A1.png)

Index bits na początku:
![](https://i.imgur.com/726gVEC.png)

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

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

![](https://i.imgur.com/aEn1ynO.jpg)


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

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

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



