---
# System prepended metadata

title: 'Ćwiczenia 10, grupa cz. 16-18, 9 maja 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ćwiczenia 10, grupa cz. 16-18, 9 maja 2024

###### tags: `SYK24` `ć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   | 7   | 8   | 9   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Marcin Banak             |   X   |  X   |   X  |  X   | X    |  ==X==  |     |   X  |   X  |
Bartosz Borecki          |   X  |  X  |==X== |  X  |     |  X  |     |     |     | 
Karol Burczyk            |  X   |  X   |  X   |  X   |   ==X==  |   X  |     |  X   | X
Yelyzaveta Ilman         |   X   | ==X==    | X    | X    |  X    | X    |     | X    | X   |
Antoni Kamiński          |   X   |  X   |  X   | ==X==    |  X   |  X   |     |  X   |   X  |
Jan Kamyk                |==X== |  X  |  X  |  X  |     |  X  |     |  X  |     |
Bartosz Kruszewski       |   X  |  X  |  X  |  X  |  X  |  X  |  X  |  X  |  ==X==  | 
Hanna Laszkiewicz        |  X    |   X  |  X   | X    |  X   |   X  |     |   X  |    | 
Kaja Matuszewska         |      |     |     |     |     |     |     |     |     | 
Dominik Muc              |      |     |     |     |     |     |     |     |     |
Krzysztof Ostrowski      |   X   |  X   |   X  |  X   |    X |   X  |     |  ==X==   |  X   | 
Franciszek Przeliorz     |      |     |     |     |     |     |     |     |     |
Yaryna Rachkevych        |   X   |  X   |  X   |   X  |     |  X   |     |   X  |     | 
Mikołaj Kalitka          |   X   |  X   |  X  |  X   |  X   |   X  |     |  X   |  X   |
Piotr Thamm              |    X  |  X   |   X  |  X   |   X  |    X |     |     |     |
Taras Tsehenko           |     |   X  |  X   |  X   |   X  |   X  |     |  X   |     |
Wiktor Małek             |      |     |     |     |     |     |     |     |     | 
Piotr Salamon            |  X    |  X   |    X |    X |     |     |     |     |     |
:::


Poniżej można zadeklarować zadania **5**, **6** oraz **7** z listy **9**. Deklaracja musi spełniać warunek: "Jeżeli student zadeklarował zadanie 6 lub 7 to zadeklarował również zadanie 5 ". Deklaracji uczynionych na poprzednich ćwiczeniach nie trzeba powtarzać.




:::success
|                        | 9.5  | 9.6 | 9.7 |
| ----------------------:| -----| --- | --- |
Marcin Banak             |      |     |     |
Bartosz Borecki          |      |     |     | 
Karol Burczyk            |      |     |     |
Yelyzaveta Ilman         |      |     |     |
Antoni Kamiński          |      |     |     |
Jan Kamyk                |      |     |     |
Bartosz Kruszewski       |      |     |     | 
Hanna Laszkiewicz        |      |     |     | 
Kaja Matuszewska         |      |     |     | 
Dominik Muc              |      |     |     |
Krzysztof Ostrowski      |      |     |     | 
Franciszek Przeliorz     |      |     |     |
Yaryna Rachkevych        |      |     |     | 
Mikołaj Kalitka          |      |     |     |
Piotr Thamm              |      |     |     |
Taras Tsehenko           |      |     |     |
Wiktor Małek             |      |     |     | 
Piotr Salamon            |      |     |     |
:::










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





## Zadanie 1
:::success
Autor: 	Jan Kamyk		
:::

![L10_tresc_tabelka](https://hackmd.io/_uploads/By0zpIqfA.png)

Dla przykłądów:
* 832~16~ => 1000 0011 0010~2~:
    * 1000 0011~2~: 83~10~ => znacznik
    * 00~2~: 0~10~ => indeks
    * 10~2~: 2~10~ => offset
    * wartość: CC~16~ = 204~10~
* 835~16~ => 1000 0011 0101~2~:
    * 1000 0011~2~: 83~10~ => znacznik
    * 01~2~: 1~10~ => indeks
    * 01~2~: 2~10~ => offset
    * wartość: MISS
* FFD~16~ => 1111 1111 1101~2~:
    * 1111 1111~2~ = 255 => znacznik
    * 11~2~ = 3~10~ => index
    * 01~2~ = 1~10~ => offset 
    * wartość: C0~16~ = 192~10~


## Zadanie 2
:::success
Autor: 	Yelyzaveta Ilman
![treść](https://hackmd.io/_uploads/Bkq4A8cGA.png)


W pamięci podręcznej z mapowaniem bezpośrednim, **każdy** blok pamięci głównej jest przypisywany do dokładnie **jednego** wiersza w pamięci podręcznej.
Wybór konkretnego wiersza w pamięci podręcznej jest dokonywany na podstawie **adresu** pamięci głównej.

![cache read](https://hackmd.io/_uploads/BJ6BAI5MR.png)

Adres pamięci głównej jest dzielony na **trzy** części:
* tag:  blok danych 
* indeks wiersza: lokalizacja - $5$ bitów
* offset: bajty (konkretna lokalizacja) - $5$ bitów

Więc:
> Rozmiar bloku w 32-bitowych słowach:
> 
 $B=2^b$ $= 2^5 = 32$ bajty 
 
> Liczba wierszy:
> 
$S=2^s$ $= 2^5 = 32$ 

> Stosunek $\frac{dane}{metadane}$
* *metadane - "dane o danych"*
*Bity_metadane* = bity_tag + bity_valid $= (32-10) + 1 = 23$
*Bity_dane* $= 32*8 = 256$
Więc: $\frac{dane}{metadane}$ = $\frac{256}{23}$
:::

## Zadanie 3
:::success
Autor: 		Bartosz Borecki
0	 0000000000000000000000	00000	00000	compulsory miss
4	 0000000000000000000000	00000	00100	hit
16	 0000000000000000000000	00000	10000	hit
132	 0000000000000000000000	00100	00100	compulsory miss
232	 0000000000000000000000	00111	01000	compulsory miss
160	 0000000000000000000000	00101	00000	compulsory miss
1024 0000000000000000000001	00000	00000	conflict miss
28	 0000000000000000000000	00000	11100	conflict miss
140	 0000000000000000000000	00100	01100	hit
3100 0000000000000000000011	00000	11100	conflict miss
180	 0000000000000000000000	00101	10100	hit
2180 0000000000000000000010	00100	00100	conflict miss

4*100%/12 = 33.(3)%

(0000000000000000000011, 00000)
(0000000000000000000010, 00100)
(0000000000000000000000, 00101)
(0000000000000000000000, 00111)
:::

## Zadanie 4
:::success
Autor: 	Antoni Kamiński		
:::

> Powtórz poprzednie zadanie dla następujących organizacji pamięci podręcznej:

* sekcyjno-skojarzeniowa 3-drożna, bloki długości dwóch słów, liczba bloków 24, **polityka wymiany LRU**

mamy 8 setów (sekcji), w każdym po 3 wiersze, w każdym bloku po 2 słowa, czyli 8 bajtów

adresy są postaci:
... t t t t t t | i i i | o o o

0 -> 0...0 -> (0, 0, 0) -> comp. miss
4 -> 0...0|100 -> (0, 0, 4) -> hit
16 -> 0...|010|000 -> (0, 2, 0) -> comp. miss
132 -> 0...010|000|100 -> (2, 0, 4) -> comp. miss
232 -> 0...011|101|000 -> (3, 5, 0) -> comp. miss
160 -> 0...010|100|000 -> (2, 4, 0) -> comp. miss
1024 -> 0...010000|000|000 -> (16, 0, 0) -> comp. miss
28 -> 0...|011|100 -> (0, 3, 4) -> comp. miss
140 -> 0...010|001|100 -> (2, 1, 4) -> comp. miss
3100 -> 0...0110000|011|100 -> (48, 3, 4) -> comp. miss
180 -> 0...010|110|100 -> (2, 6, 4) -> comp. miss
2180 -> 0...0100010|000|100 -> (34, 0, 4) -> conf. miss + replace

stan pamięci na końcu:
|[set]|valid bit|tag|bytes|
|-|---------|---|-----|
0:|1|34|...|
| |1|2|...|
| |1|16|...|
1:|1|2|...|
| | | |   |
| | | |   |
2:|1|0|...|
| | | |   |
| | | |   |
3:|1|0|...|
| |1|48|...|
| | | |   |
4:|1|2|...|
| | | |   |
| | | |   |
5:|1|3|...|
| | | |   |
| | | |   |
6:|1|2|...|
| | | |   |
| | | |   |
7:| | |   |
| | | |   |
| | | |   |
8:| | |   |
| | | |   |
| | | |   |
* w pełni asocjacyjna, bloki długości słowa, liczba bloków 8, polityka wymiany LRU.

tylko jeden set (sekcja), blok ma rozmiar słowa czyli 4 bajty, mamy 8 wierszy

adresy są postaci:
... t t t t t t t t t t | o o

0 -> 0...0 -> (0, 0) -> comp. miss
4 -> 0...01|00 -> (1, 0) -> comp. miss
16 -> 0...0100|00 -> (4, 0) -> comp. miss
132 -> 0...0100001|00 -> (33, 0) -> comp. miss
232 -> 0...0111010|00 -> (58, 0) -> comp. miss
160 -> 0...0101000|00 -> (40, 0) -> comp. miss
1024 -> 0...0100000000|00 -> (256, 0) -> comp. miss
28 -> 0...0111|00 -> (7, 0) -> comp. miss
140 -> 0...0100011|00 -> (35, 0) -> conf. miss + replace
3100 -> 0...01100000111|00 -> (775, 0) -> conf. miss + replace
180 -> 0...0101101|00 -> (45, 0) -> conf. miss + replace
2180 -> 0...01000100001|00 -> (545, 0) -> conf. miss + replace

## Zadanie 5
:::success
Autor: 	Karol Burczyk		
:::

![image](https://hackmd.io/_uploads/HJ1iqD9zA.png)


* write-back - dane są zapisywane najpierw do pamięci cache, a dopiero później w odstępach czasu do RAM'u, jeżeli inny proces nie potrzebuje tego fragmentu pamięci
* write-allocate - jeżeli zapisujemy dane we fragmencie pamięci, który nie jest cache'u, to przed zapisaniem alokujemy dla tyhc danych miejsce
* dirty bit - informuje nas, że dane zostały zmodyfikowane, a jeszcze nie przeniesione 

![image](https://hackmd.io/_uploads/HJGy1P9MC.png)


## Zadanie 6
:::success
Autor: 	Marcin Banak		
:::
### Pamięci
- L1
    - Szybkość dostępu:     **0.66ns** 
    - współczynnik chybień: **0.08**
- L2
    - Szybkość dostępu:     **5.6ns**
    - współczynnik chybień: **0.005**
- główna
    - Szybkość dostępu:     **70ns**

Średni czas liczymy mając na uwadze to, że będziemy zaglądać do pamięci od najmniejszej do największej (L1 -> L2 -> główna), bo tak jest najszybciej. W ten sposób zwyczajnie dodajemy do siebie średnie czasy przemnażając je przez prawdopodobieństwo (współczynniki chybień), że nie znaleźliśmy niczego w poprzednich pamięciach.

CPI (cycles per instruction) liczymy mnożąc stosunkową ilość dostępów do pamięci przez ilość cykli wyliczoną ze średniego czasu dostępu do pamięci. Końcowo dodajemy stosunkową ilość pozostałych instrukcji razy 1 (założyliśmy, że CPI procesora jest równe 1.0).
### Procesor tylko z L1

Średni czas dostępu:

$0.66ns + 70ns * 0.08 \approx 6.26ns \approx 9.5cykle$

CPI:

$0.36 * 9.5 + (1 - 0.36) * 1 \approx 4$

### Procesor tylko z L1 i L2

Średni czas dostępu:

$0.66ns + 5.6ns * 0.08 + 70ns * 0.08 * 0.005 = 0.66ns + 0.448ns + 0.028ns = 1.136ns \approx 1.7cykle$

CPI:

$0.36 * 1.7 + (1 - 0.36) * 1 \approx 1.25$


## Zadanie 7
:::success
Autor: Bartosz Kruszewski	 		
:::

#### Co chcemy osiągnąć?

Naszym celem jest realizacja za pomocą struktury o $log_2(4!)$ bitach polityki LRU. Zadanie sprowadza się do przechowywania w strukturze informacji o kolejności bloków, względem czasu modyfikacji.

#### Struktura

$log_2(4!) \approx 5$
Musimy oznaczyć 4 bloki.

Podzielmy nasze $5$ bitów na trzy częśći:

- 2 bity na numer najstarszego bloku
- 2 bity na numer drugiego najstarszego bloku
- 1 bit mówiący, czy najbardziej lewy z pozostałych bloków (najnowszy lub drugi najnowszy) jest najnowszy

Taka reprezentacja pozwala uzyskać jednoznaczne przedstawienie kolejności bloków.

#### Realizacja zastąpienia

Wybór bloku do zastąpienia realizujemy, patrząc na dwa pierwsze bity (numer najstarszego bloku).

Strukturę aktualizujemy następująco:

1. Przepisujemy bity 3 i 4 do 1 i 2
2. Sprawdzamy, który z pozostałych bloków był drugi najmłodszy (patrzymy na ostatni bit struktury) i wpisujemy jego numer do bitów 3 i 4
3. Jeżeli poprzednio najstarszy blok, którego dokonaliśmy zastąpienia jest przed poprzednio najmłodszym blokiem (jest to ostatni pozostały blok) to na ostatni bit wpisujemy 1, wpp 0


## Zadanie 8
:::success
Autor: 	Krzysztof Ostrowski		
:::

![image](https://hackmd.io/_uploads/ByV1PWFzR.png)


Tablica x ma $4*256=1012$ bajtów

### a)
Skoro pamięć podręczna ma 512 bajtów a rozmiar bloku 16 bajtów oraz mapowanie bezpośrednie (1 blok na 1 zbiór) to mamy **32 zbiory**

![image](https://hackmd.io/_uploads/BkrfkfFf0.png)

najpierw bierzemy x[0][0], `na rysunku 1`,
następnie bierzemy x[1][0], `na rysunku 2`

jak widać, wykonamy 2 missy, ponieważ ten set będzie już zajęty.

Podsumowując: wykonamy 8 missów do pierwszego seta (4 razy powtórzy się sytuacja z rysunku), następnie 8 missów do drugiego seta, itd...

łącznie 100% miss (50% conflict).

### b) 
Tym razem pamięć podręczna ma 1024  bajty, więc mamy **64 zbiory**

Dzięki temu element 128 dostanie się do innego seta (set 33) niż 0 (set 0).

W danym secie raz wczytamy 4 bloki (compulsory miss), następnie 3 razy pobierzemy wartość (hit)

Stąd wykonamy tylko 25% miss.

### c)

Przez to, że pamięć jest dwudrożna i używa polityki LRU, będziemy posiadać **32 zbiory**, ale po 2 zestawy. 

Sytuacja analogiczna co w podpunkcie b)

Zwiększenie pamięci nie zmniejszy liczby missów, ponieważ generowany jest tylko compulsory miss. Zwiekszenie rozmiaru bloku zmniejszy współczynnik chybień, ponieważ większe bloki będą ładowane do pamięci podręcznej, więc rzadziej pojawiał się będzie compulsory miss.

## Zadanie 9
:::success
Autor: 	Mikołaj Kalitka		
:::

Mapowanie bezpośrednie oznacza, że każdy zbiór ma jeden blok.
Blok ma wielkość 8 bajtów, więc może pomieścić 8 zmiennych char, czyli dwie struct pixel.
Rozmiar pamieci to 32KB, natomiast rozmiat tablicy buffer to 480 * 640 * 4 = 1 228 800 bajtów.

Blok może efektywnie zadziałać dla 8 wartości char będących obok siebie.
W każdej iteracji pętli mamy 4 modyfikacje wartości, natomiast kolejne iteracje są mocno oddalone od siebie, ponieważ wewnętrzna pętla jest po i zamiast po j. 32KB pamięci pomieszczą 480 * 8 = 3840 bajtów, więc co drugą iterację mamy 4 trafienia.
Łącznie na każde dwie iteracje mamy 1 compulsory miss (lub conflict miss jeżeli pamięć zapełni się) oraz 7 trafień.

Stąd miss rate: 1/8 = 12.5%.
