Ćwiczenia 10, grupa śr. 14-16, 8 maja 2024

# Ćwiczenia 10, grupa śr. 14-16, 8 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 | | ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- | Krzysztof Chorzempa | X | X | X | | X | X | | | | Maciej Ciepiela | X | X | X | X | | X | | | | Szymon Fica | X | X | X | X | | X | X | | | Agnieszka Grala | X | X | X | X | | X | X | | | Karolina Jędraszek | X | X | ==X== | X | | X | X | | | Katarzyna Jodłowska | X | X | X | X | | X | X | | | Dominik Kiełbowicz | X | X | X | X | X | ==X== | X | | | Michał Kolasa | X | X | X | X | ==X== | X | X | | | Rafał Krysa | X | X | X | X | | X | X | | | Miłosz Krzysiek | X | X | X | ==X== | | X | X | | | Łukasz Kulczycki | | | | | | | | | | Leon Lepkowski | X | X | X | X | | X | X | | | Hanna Makowska | X | X | X | X | | X | X | | | Jan Marek | ==X== | X | X | | X | X | | | | | Cezary Miłek | X | X | X | X | | X | | | | Anna Pierzchała | X | X | X | X | | X | | | | Alan Pietrasz | X | X | X | X | | X | ==X== | | | Kacper Ponikowski | X | X | X | X | | X | X | | | Dominik Walecko | X | X | X | X | | X | | | | Michał Włodarczak | X | ==X== | X | X | | X | X | | | ::: Poniżej można zadeklarować zadania **5** z **listy 9**: :::success | | 9.5 | | ----------------------:| -----| Krzysztof Chorzempa | | Maciej Ciepiela | | Szymon Fica | | Agnieszka Grala | | Karolina Jędraszek | | Katarzyna Jodłowska | | Dominik Kiełbowicz | | Michał Kolasa | | Rafał Krysa | | Miłosz Krzysiek | | Łukasz Kulczycki | | Leon Lepkowski | | Hanna Makowska | | Jan Marek | | Cezary Miłek | | Anna Pierzchała | | Alan Pietrasz | | Kacper Ponikowski | | Dominik Walecko | | Michał Włodarczak | | ::: :::info **Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony. ::: ## Zadanie 1 :::success Autor: Jan Marek ::: ![image](https://hackmd.io/_uploads/SJ1Uo3IfA.png) Pierwsze dwie cyfry to znacznik (tag). Ostatnia to index i offset. Bitowo -> pierwsze 8 bitów to **tag**, następne 2 to **index** oraz ostatnie 2 to **offset**. - 832~16~ = 10000011 00 10~2~ tag: 10000011 index: 00 offset: 10 - 835~16~ = 10000011 01 01~2~ tag: 10000011 index: 01 offset: 01 - FFD~16~ = 11111111 11 01~2~ tag: 11111111 index: 11 offset: 01 ![z1](https://hackmd.io/_uploads/SkKuh0LGC.png) ## Zadanie 2 :::success Autor: Michał Włodarczak ::: ![Tresc 2](https://hackmd.io/_uploads/H1FDRyKzA.png) Pamięć podręczna z mapowaniem bezpośrednim adresowana bajtowo to taka w której w każdym zbiorze jest tylko jeden line (E = 1) * Skoro na offset bloku jest poświęcone 5 bitów to rozmiar bloku wynosi **B = $2^5$ = 32 bajty** * Na indeks wiersza też jest poświęcone 5 bitów czyli wierszy będzie tyle samo **S = $2^5$ = 32** * Bitów składujących metadane będzie tyle ile jest przeznaczonych na tag + 1 bit na valid, czyli **22+1 = 23**. Bitów składujących dane będzie **32*8 = 256** $\frac{256}{23} \approx{11.13}$ ## Zadanie 3 :::success Autor: Karolina Jędraszek ::: ![Screenshot 2024-05-07 at 19.53.25](https://hackmd.io/_uploads/Syxp9JufR.png) **Zastąpienie bloku** - blok danych musi zostać przeniesiony do pamięci podręcznej, a wszystkie dostępne miejsca w tej pamięci są już zajęte, konieczne jest zastąpienie jednego z istniejących bloków. **Trafienie** (ang. hit) - żądany blok danych jest już obecny w pamięci podręcznej w momencie, gdy następuje dostęp do niego. **Chybienie** (ang. miss) - adres odczytu nie zostaje odnaleziony w pamięci podręcznej, co wymaga dostępu do wolniejszej pamięci głównej w celu pobrania danych. **Przymusowe chybienie** (ang. compulsory miss) - pierwszy raz odwołujemy się do bloku danych, więc nie jest jeszcze obecny w pamięci podręcznej. **Chybienie z konfliktem** (ang. conflict miss) - występuje wtedy, gdy dwa różne bloki mają ten sam indeks. | | adres |tag | index | offset | ? | |-| ----- | -------- | ----- | ------ | -------- | |1| 0 |0000 0000 | 00000 | 00000 | compulsory miss| |2| 4 |0000 0000 | 00000 | 00100 | trafienie | |3| 16 |0000 0000 | 00000 | 10000 | trafienie | |4| 132 |0000 0000 | 00100 | 00100 | compulsory miss | |5| 232 |0000 0000 | 00111 | 01000 | compulsory miss | |6| 160 |0000 0000 | 00101 | 00000 | compulsory miss | |7| 1024 |0000 0001 | 00000 | 00000| conflict miss |8| 28 |0000 0000 | 00000 | 11100 | conflict miss |9| 140 |0000 0000 | 00100 | 01100 | trafienie |10| 3100 |0000 0011 | 00000 | 11100 | conflict miss |11| 180 |0000 0000 | 00101 | 10100 | trafienie |12| 2180 |0000 0010 | 00100 | 00100 | conflict miss Wystąpiły 4 conflict miss. Liczba trafień = 4/12 = 33% Pamięć na końcu: (tag, index, offest) (11, 00000, ...) (10, 00100, ...) (0, 00101, ...) (0, 00111, ...) ## Zadanie 4 :::success Autor: Miłosz Krzysiek ::: ![Screenshot 2024-05-07 at 21.35.09](https://hackmd.io/_uploads/rk6qG-ufA.png) **Polityka wymiany LRU** (Least Recently Used) to strategia zarządzania pamięcią podręczną, która zakłada, że bloki, które nie były używane od najdłuższego czasu, są najbardziej prawdopodobne do zastąpienia podczas chybienia związanego z pojemnością. W skrócie, LRU zakłada, że blok danych, który był używany najdawniej, jest tym, który zostanie zastąpiony, gdy potrzebujemy miejsca na nowy blok danych. **Sekcyjno-skojarzeniowa 3-drożna, bloki długości dwóch słów, liczba bloków 24, polityka wymiany LRU** Rozmiar bloku w bajtach: 2 słowa * 4 bajty/słowo = 8 bajtów Liczba indeksów: 24 bloki / 3 bloki na drogę = 8 indeksów Liczba bitów na indeks: log2(8) = 3 bity Liczba bitów na offset: log2(8 bajtów) = 3 bity Liczba bitów na tag: 32 bity - 3 bity na indeks - 3 bity na offset = 26 bitów |adres|tag | index | offset|?| |-----|--- | ------| ----- |-| |0| 000000| 000| 000 |miss compulsory |4| 000000 |000 |100| trafienie |16| 000000 |010 |000 |miss compulsory |132| 000010 |000 |100 |miss compulsory |232| 000011 |101 |000 |miss compulsory |160| 000010 |100 |000 |miss compulsory |1024| 010000 |000 |000 |miss compulsory |28| 000000| 011| 100| miss compulsory |140| 000010 |001 |100| miss compulsory |3100| 110000 |011 |100| miss compulsory |180| 000010 |110 |100 |miss compulsory |2180| 100010 |000 |100| miss conflict Liczba trafień: 1 - 8,3% miss compulsory - 10 miss conflict - 1 Zawartość pamięci: index 0 - 10, 10000, 100010 index 1 - 10 index 10 - 0 index 11 - 0 index 100 - 10 index 101 - 11 index 110 - 10 **W pełni asocjacyjna, bloki długości słowa, liczba bloków 8, polityka wymiany LRU.** |adres|tag | offset|?| |--|---|--|-| |0| 0000000000 |00 |miss compulsory| |4| 0000000001 |00 |miss compulsory| 16| 0000000100 |00 |miss compulsory| 132| 0000100001| 00 |miss compulsory| 232| 0000111010 |00 |miss compulsory| 160| 0000101000 |00 |miss compulsory| 1024| 0100000000 |00 |miss compulsory| 28| 0000000111 |00 |miss compulsory| 140| 0000100011 |00 |miss capacity| 3100| 1100000111 |00 |miss capacity| 180| 0000101101| 00| miss capacity| 2180| 1000100001| 00| miss capacity| Liczba trafień: 0 - 0% miss compulsory - 8 miss conflict - 0 miss capacity - 4 ## Zadanie 5 :::success Autor: Michał Kolasa ::: ![](https://i.imgur.com/FT7vvyW.png) ## Zadanie 6 :::success Autor: Dominik Kiełbowicz ::: ![](https://i.imgur.com/MrPj7oF.png) dostęp do pamięci głównej = 70ns dostęp do pamięci L1 = 0.66ns dostęp do pamięci L2 = 5.62ns Współczynnik chybień L1 = 8% Współczynnik chybień L2 = 0.5% Dostępy do pamięci - 36% instrukcji Długość cyklu - 0.66ns średni czas dostępu tylko z L1: szukana wartość jest w L1: $0.92*0.66$ ns else: $0.08*70.66$ ns (dostęp do pamięci głównej + czas L1) $0.92*0.66ns + 0.08*70.66ns = 6.26ns$ średni czas dostępu z L1 i L2: w 99,5% przypadków nasza wartość będzie w L2 $0.92*0.66ns + 0.08 * (0.995*5.62ns + 0.005*(70+5.62+0.66)) = 1.14ns$ CPI = 1 CPI z L1: $0.36*6.26/0.66 + 0.64*1 = 4.05$ CPI z L1 i L2: $0.36*1.14/0.66 + 0.64*1 = 1.26$ ## Zadanie 7 :::success Autor: Alan Pietrasz ::: ![image](https://hackmd.io/_uploads/SJ0tA1tGA.png) Oznaczmy pozycje bloków w kolejności od najmłodszego do najstarszego w czasie t: $(1)_t\ (2)_t\ (3)_t\ (4)_t$ Mamy dodatkowe 5 bitów, takie, że 2 pierwsze z nich reprezentują pozycję $(1)_t$, 2 kolejne pozycję $(2)_t$, a ostatni bit jest równy 0 jeśli $(3)_t\ < \ (4)_t$ oraz 1 jeśli $(3)_t\ > \ (4)_t$ 1. Dostęp do $(1)$ Bez zmian 2. Dostęp do $(2)$ $\mathbf{(1)_{t+1}=(2)_t}$ $\mathbf{(2)_{t+1}=(1)_t}$ $(3)_{t+1}=(3)_t$ $(4)_{t+1}=(4)_t$ Dwa pierwsze bity swapujemy z kolejnymi dwoma. 3. Dostęp do $(3)$ $\mathbf{(1)_{t+1}=(3)_t}$ $\mathbf{(2)_{t+1}=(1)_t}$ $(3)_{t+1}=(2)_t$ $(4)_{t+1}=(4)_t$ Pod dwa późniejsze bity podstawiamy pozycję $(1)_t$. Można to zrobić shiftem o 2 bity. Pod dwa pierwsze bity podstawiamy pozycję $(3)_t$. Jeśli $(2)_t < (4)_t$ to 5 bit jest 0, a w przeciwnym przypadku 1. 4. Dostęp do $(4)$ $\mathbf{(1)_{t+1}=(4)_t}$ $\mathbf{(2)_{t+1}=(1)_t}$ $(3)_{t+1}=(2)_t$ $(4)_{t+1}=(3)_t$ Pod dwa późniejsze bity podstawiamy pozycję $(1)_t$. Można to zrobić shiftem o 2 bity. Pod dwa pierwsze bity podstawiamy pozycję $(4)_t$. Jeśli $(2)_t < (3)_t$ to 5 bit jest 0, a w przeciwnym przypadku 1. ## Zadanie 8 :::success Autor: Krzysztof Chorzempa ::: ```c= int x[2][128]; int i; int sum = 0; for (i = 0; i < 128; i++) { sum += x[0][i] * x[1][i]; } ``` `sizeof(int)==4` W tym zadaniu nie musimy się zajmować bitem `valid`. Zakres adresów: 0x0 (0) - 0x3F (1023), czyli binarnie do 1111111111. ### podręczna 512 bajtów, mapowanie bezpośrednie, rozmiar bloku 16 bajtów linijek (czyli jednocześnie bloków oraz zbiorów) będzie $\frac{512}{16}=32$ adres: 1 bit na tag, 5 bitów na indeks, 4 bity na offset będziemy po kolei pytać o adresy: | adres dziesiętnie | adres dwójkowo | tag | indeks | offset | | -----------------:| --------------:| ---:| ------:| ------:| | 0 | 0 | 0 | 0 | 0 | | 512 | 1 00000 0000 | 1 | 0 | 0 | | 4 | 100 | 0 | 0 | 4 | | 516 | 1 00000 0100 | 1 | 0 | 4 | | ... | ... | ... | ... | ... | Czyli za każdym razem albo jeszcze nie mamy wczytanych danych do pamięci podręcznej (*compulsory miss*), albo mamy inny tag (*conflict*). Współczynnik chybień: $100\%$. ### podręczna 1024 bajtów, mapowanie bezpośrednie, rozmiar bloku 16 bajtów linijek (czyli jednocześnie bloków oraz zbiorów) będzie $\frac{1024}{16}=64$ adres: **0 bitów na tag**, 6 bitów na indeks, 4 bity na offset będziemy po kolei pytać o adresy: | adres dziesiętnie | adres dwójkowo | ~~tag~~ | indeks | offset | | -----------------:| --------------:| -------:| ------:| ------:| | 0 | 0 | | 0 | 0 | | 512 | 100000 0000 | | 32 | 0 | | 4 | 100 | | 0 | 4 | | 516 | 100000 0100 | | 32 | 4 | ... Zarówno dla `x[0]` i `x[1]` (oddzielnie, indeksy nie będą na siebie nachodziły) będzie to wyglądało tak: | Numer kroku | Opis | Offset | | ----------- | --------------------------------------------------------------------- | ------:| | 1. | Nie ma danych w pamięci podręcznej, wczytujemy je (*compulsory miss*) | 0 | | 2. | Odczytujemy (hit) | 4 | | 3. | hit | 8 | | 4. | hit | 12 | | 5. | Znów nie ma danych (inny indeks) | 0 | | ... | ... | ... | Widać, że co czwarte zapytanie skutkuje *(compulsory) missem*, czyli $25\%$. ### podręczna 512 bajtów, dwudrożna sekcyjno-skojarzeniowa, polityka zastępowania LRU, rozmiar bloku 16 bajtów linijek będzie 32 (jak w pierwszym przypadku) zbiorów będzie 16 (po dwie linijki w zbiorze) adres: 2 bity na tag, 4 bity na indeks, 4 bity na offset Przebieg: | adres dziesiętnie | adres dwójkowo | tag | indeks | offset | uwagi | | -----------------:| --------------:| ---:| ------:| ------:| -----------------------:| | 0 | 0 | 0 | 0 | 0 | | | 512 | 10 0000 0000 | 10 | 0 | 0 | | | 4 | 100 | 0 | 0 | 4 | | | 516 | 10 0000 0100 | 10 | 0 | 4 | | | ... | ... | ... | ... | ... | | | 256 | 1 0000 0000 | 1 | 0 | 0 | LRU: zastępujemy tag 0 | | 768 | 11 0000 0000 | 11 | 0 | 0 | LRU: zastępujemy tag 10 | | ... | ... | ... | ... | ... | | Czyli w pierwszej połowie działania programu co czwarty odczyt to *compulsory miss*, reszta to *hit*. W drugiej połowie podobnie, ale co czwarty odczyt to *conflict miss*. Czyli $25\%$. #### zwiększenie rozmiaru pamięci podręcznej nic nam nie da, po prostu zamiast *conflict miss* będą *compulsory miss* #### zwiększenie rozmiaru bloku jak najbardziej da (zrobimy to kosztem indeksów), bo rzadziej będziemy musieli odpytywać pamięć (przenosić ją do podręcznej) ## Zadanie 9 :::success Autor: Michał Kolasa ::: rozmiar pamięci 32 KB rozmiar bloku 8 B mapowanie bezpośrednie write-back write-allocate sizeof(char) = 1 sizeof(int) = 4 sizeof(pixel) = 4 for (j = 639; j >= 0; j--) { for (i = 479; i >= 0; i--) { buffer[i][j].r = 0; buffer[i][j].g = 0; buffer[i][j].b = 0; buffer[i][j].a = 0; } } tag, index, offset offset = 3 index = 32768/8 = 4096 = 2^12 => 12 tag reszta ![](https://i.imgur.com/TTVwvNU.png) U nas przechodzimy przez kolumny: buffer[479][639], buffer[478][639] itd., mamy zatem: miss rate = 1, ale jeden pixel to 4 dostępy, zatem dzielimy miss rate przez 4, 1 access - miss, ładujemy do cache, kolejne 3 to hity zatem mamy miss rate 25% Wystarczy zamienić pętle miejscami, żebyśmy wykorzystywali spatial locality: wtedy wykonujemy dostępy do następujących po sobie elementów, np. buffer[479][639], buffer[479][638] - te pixele są obok siebie w pamięci, zatem po załadowaniu bloku buffer[479][639], wykonując dostęp do buffer[479][638], ten będzie już w cache mamy zatem miss rate = sizeof(pixel)/B = 1/2 i jak wyżej dzielimy przez 4, co daje nam miss rate 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.