---
# System prepended metadata

title: 'Ćwiczenia 10, grupa śr. 14-16, 8 maja 2024'
tags: [pwit, ćwiczenia, SYK24]

---

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


