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

# Ć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%.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.