# Ćwiczenia 9, grupa cz. 14-16, 4 maja 2023

###### tags: `SYK23` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | | |
Wojciech Bogucki | X | X | X | | X | X | | | |
Mateusz Cerulewicz | X | X | X | | | X | | | |
Mateusz Garncarczyk | ==X== | X | X | X | | X | | | |
Mateusz Golisz | X | X | X | | | X | | | |
Mateusz Kitzol | X | X | X | X | X | X | | | |
Piotr Mańkowski | | | | | | | | | |
Michał Mękarski | | | | | | | | | |
Aleksandra Nicpoń | X | X | X | X | | X | | | |
Ksawery Plis | X | ==X== | X | X | | X | | | |
Patryk Rybak | X | X | X | X | | X | X | | |
Rafał Spyra | X | X | X | X | X | X | ==X== | X | X |
Dominik Szczepaniak | X | X | X | X | X | X | X | | ==X== |
Taras Tsehenko | | | | | | | | | |
Maksymilian Wiśniewski | X | X | X | X | | ==X== | X | X | |
Martyna Wybraniec | X | X | X | X | | X | | | |
Natalia Zychowicz | | | | | | | | | |
Patryk Maciąg | X | X | X | X | X | X | X | | |
:::

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

## Zadanie 1
:::success
Autor: Mateusz Garncarczyk
:::




## Zadanie 2
:::success
Autor: Ksawery Plis
:::

**Pamięć podręczna z mapowaniem bezpośrednim adresowanym bajtowo:** pamięć podręczna taka że w każdym zbiorze $S$ znajduje się tylko jeden wiersz $E$ (a więc $E$=1).

* **Jaki jest rozmiar bloku w 32-bitowych słowach?**
Offset zapisywany jest na 5 bitach. Jego maksymalna wartość to 31 (11111$_2$). Więc blok ma 32 bajty.

* **Ile wierszy ma nasza pamięć podręczna?**
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.

* **Jaki jest stosunek liczby bitów składujących dane do liczby bitów składujących metadane?**
Na metadane składa się tag (22 bity) oraz bit valid.
Dane przechowywane są na 32 bajtach.
Także stosunek danych do metadanych wynosi $\frac{8*32}{22+1} = \frac{256}{23} \approx 11.13$
## Zadanie 3
:::success
Autor: Mateusz Cerulewicz
:::

     tag    set    offset
 0:    0    00000  00000   compulsory 
 4:    0    00000  00100   hit 
 16:   0    00000  10000   hit
 132:  0    00100  00100   compulsory 
 232:  0    00111  01000   compulsory 
 160:  0    00101  00000   compulsory 
 1024: 1    00000  00000   conflict
 28:   0    00000  11100   conflict
 140:  0    00100  01100   hit
 3100: 11   00000  11000   conflict
 180:  0    00101  10100   hit
 2180: 10   00100  00100   conflict


8 podmian (4 konflikty i 4 puste)

Liczba trafien: 4
Efektywnosc: 4/12 = 1/3

Pamiec na koncu:

(11, 00000, ...)
(10, 00100, ...)
(0, 00101, ...)
(0, 00111, ...)

## Zadanie 4
:::success
Autor: Mateusz Kitzol
:::

### a) sekcyjno-skojarzeniowa

blok: 2 * 4B = 8B = 2^3B, czyli **offset - 3 bity**
24 bloki i po 3 bloki na zbiór, czyli 8 zbiorów, czyli **index - 3 bity**

**Adres:**
tag: 26 bitów
index: 3 bity
offset: 3 bity

| Adres | Zapis bitowy | tag | index | offset | hit/miss? |
| ---------:| ---------------- | --- | ----- | ------ | --------------- |
| 0 | 0 00000 00000 | 0 | 000 | 000 | MISS compulsory |
| 4 | 0 00000 00100 | 0 | 000 | 100 | HIT |
| 16 | 0 00000 10000 | 0 | 010 | 000 | MISS compulsory |
| 132 | 0 00100 00100 | 10 | 000 | 100 | MISS compulsory |
| 232 | 0 00111 01000 | 11 | 101 | 000 | MISS compulsory |
| 160 | 0 00101 00000 | 10 | 100 | 000 | MISS compulsory |
| 1024 | 1 00000 00000 | 10000| 000 | 000 | MISS compulsory |
| 28 | 0 00000 11100 | 0 | 011 | 100 | MISS compulsory |
| 140 | 0 00100 01100 | 10 | 001 | 100 | MISS compulsory |
| 3100 | 11 00000 11100 | 110000 | 011 | 100 | MISS compulsory |
| 180 | 0 00101 10100 | 10 | 110 | 100 | MISS compulsory |
| 2180 | 10 00100 00100 | 100010 | 000 | 100 | MISS conflict |

**Liczba bloków zastąpionych:** $11$ (compulsory miss + conflict miss)
**Efektywność pamięci wewnętrznej:** $\frac{1}{12} = 8.(3)$%
**Zawartość pamięci:**

|index|tag |
|------|-----|
|0 |100010 |
| |10 |
| |10000 |
|1 |10 |
| |- |
| |- |
|10 |0 |
| |- |
| |- |
|11 |0 |
| |110000 |
| |- |
|100 |10 |
| |- |
| |- |
|101 |11 |
| |- |
| |- |
|110 |10 |
| |- |
| |- |
|111 |- |
| |- |
| |- |

### b) w pełni asocjacyjna

Słowo: 32b = 4B, czyli blok: 4B = $2^2B$

**Adres:**
offset: 2 bity
index: 0 bitów
tag: 32-2-0 = 30 bitów

| Adres | Zapis bitowy | tag | offset | hit/miss? |
| -----:| -------------- | ------ | ------ | --------------- |
| 0 | 000000000 00 | 0 | 0 | MISS compulsory |
| 4 | 000000001 00 | 1 | 0 | MISS compulsory |
| 16 | 000000100 00 | 100 | 0 | MISS compulsory |
| 132 | 000100001 00 | 100001 | 0 | MISS compulsory |
| 232 | 000111010 00 | 111010 | 0 | MISS compulsory |
| 160 | 000101000 00 | 101000 | 0 | MISS compulsory |
| 1024 | 100000000 00 | 100000000 | 0 | MISS compulsory |
| 28 | 000000111 00 | 111 | 0 | MISS compulsory |
| 140 | 000100011 00 | 100011 | 0 | MISS conflict |
| 3100 | 1100000111 00 | 1100000111 | 0 | MISS conflict |
| 180 | 000101101 00 | 101101 | 0 | MISS conflict |
| 2180 | 1000100001 00 | 1000100001 | 0 | MISS conflict |

**Liczba bloków zastąpionych:** $12$ (compulsory miss + conflict miss)
**Efektywność pamięci wewnętrznej:** $\frac{0}{12} = 0$%
**Zawartość pamięci:**

|index|tag |
|------|-----|
|0 |100011 |
| |1100000111 |
| |101101 |
| |1000100001 |
| |111011 |
| |101000 |
| |100000000 |
| |111 |

## Zadanie 5
:::success
Autor: Patryk Maciąg
:::


## Zadanie 6
:::success
Autor: Maksymilian Wiśniewski
:::


## Zadanie 7
:::success
Autor: Patryk Rybak
:::


Sufit z logarytmu o podstawie 2 z 4! to 5. Mamy więc 5 bitów do wykorzystania. Set może mieć najwyżej 4 bloki. Dzięki temu zapisanie numeru bloku zajmie 2 bity (numeracja od 0 do 3).

Wykorzystanie 5 bitów:

- 2 pierwsze bity zapisują numer bloku, który jest najstarszy
- 2 kolejne bity zapisują numer drugiego najstarszego bloku

W tym momencie zostaje jeden bit do wykorzystania, który nie wystarcza na zapisanie liczby od 0 do 3.

- ostatni bit informuje czy prawie najmłodszy blok i najmłodszy będące uporządkowane pod względem wieku, czy są też uporządkowane leksykograficznie

Jak wyznaczyć kandydata do usunięcia ze zbioru?
Wystarczy spojrzeć na dwa pierwszy bity naszej struktury.

Jak aktualizować informacje zawarte w dodatkowych bitach przy wykonywaniu dostępów do elementów zbioru?

1. Jeżeli wykonamy dostęp do najmłodszego bloku, nic się nie zmieni. Nie musimy aktualizować struktury, ponieważ status wieku pozostaje ten sam i porządek leksykograficzny względem najłodszego i prawienajmłodszego bloku również się nie zmienia.

2. Jeżeli wykonamy dostęp do prawie najłodszego bloku, wystarczy zanegować piąty bit struktury.

3. Jeżeli wykonamy dostęp do prawie najstarszego bloku, należy rozpoznać, z pomocą struktury, prawie najmłodszy blok (odrzucamy bloki z czterech pierwszych bitów, wtedy o wyborze decyduje już tylok piąty bit), zapisać go na miejsce prawie najstarszego (trzeci i czwarty bit),
następnie porównać leksykograficznie blok, do którego nastąpiło odwołanie ze "starym" najmłodszym blokiem. Skoro "stary" najmłodszy blok staje się tak na prawdę prawie najmłodszym to jeżeli leksykograficznie pierwszy okaże się blok z odwołania, należy piąty bit struktury ustawić na 1.

4. Jeżeli wykonamy dostęp do najstarszego bloku, należy zaminić miejscami wartości zapisane na dwóch pierwszych i dwóch kolejnych bitach struktury i wykonac działania w taki sposób, jakbyśmy wykonali dostęp do prawie najstarszego bloku.

## Zadanie 8
:::success
Autor: Rafał Spyra
:::
1.
cache: 2^9B
offset: log2(rozmiar\ bloku) = log_2(16) = 4
liczba bloków: log2(rozmiar cache / rozmiar bloku) = log_2(2^9 / 2^4) = 5
tag: reszta

| Tag | Index | Offset |
|-|-|-|
|1 | 5 | 4 |

| Var | Address | Tag | Index | Offset | Result | Notes |
| - | -| -| -| -| - | - |
| x[0][0] | 0 | 0..00 | 00000 | 0000 | compulsory miss |
| x[1][0] | 512 | 0..01 | 00000 | 0000 | conflict miss | nadpisuje x[0][0] |
| x[0][1] | 4 | 0..00 | 00000 | 0100 | conflict miss | nadpisuje x[1][0] |
| x[1][1] | 516 | 0..01 | 00000 | 0100 | conflict miss | nadpisuje x[0][1] |

100% bo każde chybia

2.
cache: 2^10B
offset: log2(rozmiar\ bloku) = log2(16) = 4
liczba bloków: log2(2^10 / 2^4) = 6
tag: reszta
| Tag | Index | Offset |
|-|-|-|
| 0 | 6 | 4 |

| Var | Address | Index | Offset | Result | Notes |
| - | -| -| -| - | - |
| x[0][0] | 0 | 000000 | 0000 | compulsory miss |
| x[1][0] | 512 | 100000 | 0000 | compulsory miss |
| x[0][1] | 4 | 000000 | 0100 | hit | wpis x[0][0] |
| x[1][1] | 516 | 100000 | 0100 | hit | wpis x[1][0] |
| x[0][2] | 8 | 000000 | 1000 | hit | wpis x[0][0] |
| x[1][2] | 520 | 100000 | 1000 | hit | wpis x[1][0] |
| x[0][3] | 12 | 000000 | 1100 | hit | wpis x[0][0] |
| x[1][2] | 524 | 100000 | 1100 | hit | wpis x[1][0] |
| x[0][4] | 16 | 000001 | 0000 | compulsory miss |
| x[1][4] | 528 | 100001 | 0000 | compulsory miss |

Wx[i][$\frac{j}{4}$] compulsory miss, następne 3 (x[i][j + {1,2,3}]) hit. 25%

3.
cache: 2^9B
offset: 4
liczba bloków: log2(rozmiar cache / (rozmiar bloku * liczba bloków na sekcje )) = log2(2^9 / (2^4 * 2)) = log(2^4) = 4
tag: reszta

| Tag | Index | Offset |
|-|-|-|
| 2 | 4 | 4 |

| Var | Address | Tag | Index | Offset | Result | Notes|
| - | -| -| -| -| - | - |
| x[0][0] | 0 | 0..000 | 0000 | 0000 | compulsory |
| x[1][0] | 512 | 0..010 | 0000 | 0000 | compulsory | i=0 wolny tag |
| x[0][1] | 4 | 0..000 | 0000 | 0100 | hit | wpis x[0][0] |
| x[1][1] | 516 | 0..010 | 0000 | 0100 | hit | wpis x[1][0] |
| x[0][2] | 8 | 0..000 | 0000 | 1000 | hit | wpis x[0][0] |
| x[1][2] | 520 | 0..010 | 0000 | 1000 | hit | wpis x[1][0] |
| x[0][3] | 12 | 0..000 | 0000 | 1100 | hit | wpis x[0][0] |
| x[1][3] | 520 | 0..010 | 0000 | 1100 | hit | wpis x[1][0] |
| x[0][4] | 16 | 0..000 | 0001 | 0000 | compulsory |
| x[1][4] | 524 | 0..010 | 0001 | 0000 | compulsory | i=1 wolny tag |

Analogicznie do B. 25%. Jeśli zwiększymy rozmiar bloku (offset) to zmiejszy się liczba chybień

## Zadanie 9
:::success
Autor: Dominik Szczepaniak
:::


Rozmiar cache = 2^15 (32 kB)
Offset = log2(rozmiar bloku) = log2(8) = 3
Index (liczba bloków) = log2(rozmiar cache / rozmiar bloku) = log2(2^15 / 2^3) = log2(2^12) = 12
Tag = 32-3-12 = 17

from collections import defaultdict
cache_testing = defaultdict(lambda: 0)
MEMORY_SIZE = 1<<15
BLOCK_SIZE = 1<<3
SET_SIZE = 1<<12
miss = 0
total = 0

for j in range(639, -1, -1):
	for i in range(479, -1, -1):
		for pixel in range(4):
			mem_space = ((i * 640) + j) * 4 #miejsce w tablicy dla buffer[i][j] 
#(kolejne kolumny zaczynaja sie co caly wiersz miejsc, wiec co 640, 
#stad i*640, pozniej musimy dodac miejsce w ktorej kolumnie jestesmy (+j), 
#a nastepnie *4, gdyz pixel ma 4 chary - 4*1 = 4)
			mem_space_to_binary = bin(mem_space) #postac 0b{liczba binarna}
			mem_space_to_binary = mem_space_to_binary[2:]
			while(len(mem_space_to_binary) != 32):
				mem_space_to_binary = "0" + mem_space_to_binary
			index = mem_space_to_binary[17:28] #index to bit od 18 do 29 (-1 bo od 0 iterujemy)
			cache_index = int(index, 2)
			tag = int(mem_space_to_binary[0:16], 2) #tag ma 17 bitow (pierwsze)
			if cache_testing[cache_index] != tag:
				cache_testing[cache_index] = tag
				miss += 1
			total+=1
				
print(miss/total)

Wynik: 0.25
Więc mamy 25% chybień, czyli 75% trafień