# Ćwiczenia 10, grupa cz. 10-12, 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Borys Adamiak | X | X | | X | | | | | |
Michał Chawar | X | X | X | X | X | X | X | | |
Julia Cygan | X | X | | X | | | | | |
Maciej Dengusiak | X | X | X | X | X | X | X | ==X== | |
Patryk Flama | X | X | X | ==X== | X | X | X | X | |
Szymon Fluder | X | X | X | X | X | X | X | X | |
Aleksandra Jędrzejak | X | X | X | | | | | | |
Mikołaj Karapka | ==X== | X | X | X | | X | X | X | |
Viktoriia Kashpruk | X | X | X | X | | X | X | X | |
Wiktor Małek | X | X | X | X | X | X | X | X | |
Błażej Molik | X | ==X== | X | X | | X | | X | |
Andrzej Morawski | | | | | | | | | |
Konrad Oleksy | | | | | | | | | |
Lucjan Pucelak | X | X | X | X | | | | | |
Aleksandra Sęk | | | | | | | | | |
Radosław Śliwiński | | | | | | | | | |
Piotr Traczyński | X | X | X | | | X | | | |
Katarzyna Trzos | X | X | X | X | | | | X | |
Piotr Warząchowski | X | X | ==X== | X | | X | X | X | |
Olga Zaborska | ==X== | X | X | X | | X | X | | |
:::

Poniżej można zadeklarować zadanie **5** z listy **9**

:::success
| | 9.5 |
| ----------------------:| -----|
Borys Adamiak | |
Michał Chawar | |
Julia Cygan | |
Maciej Dengusiak | |
Patryk Flama | |
Szymon Fluder | |
Aleksandra Jędrzejak | |
Mikołaj Karapka | |
Viktoriia Kashpruk | |
Wiktor Małek | |
Błażej Molik | |
Andrzej Morawski | |
Konrad Oleksy | |
Lucjan Pucelak | |
Aleksandra Sęk | |
Radosław Śliwiński | |
Piotr Traczyński | |
Katarzyna Trzos | |
Piotr Warząchowski | |
Olga Zaborska | |
:::

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

## Zadanie 1
:::success
Autor: Olga Zaborska
:::



| Adres | Tag | Indeks | Offset |
|---|-----|-------|--------|
| 832 | 10000011 | 00 | 10 |
| 835 | 10000011 | 01 | 01 |
| FFD | 11111111 | 11 | 01 |

| Adres | Trafienie? | Wartość |
|:-----:|:----------:|:-------:|
| 832 | TAK | CC |
| 835 | NIE | - |
| FFD | TAK | C0 |

## Zadanie 2
:::success
Autor: Błażej Molik
:::



Pamięć podręczna z mapowaniem bezpośrednim adresowaną bajtowo to pamięć, w której w każdym zbiorze (wierszu) znajduje się dokładnie jedna linia.

Adresy są podzielone na **tag**, **indeks** i **offset**, gdzie tag oznacza blok danych, indeks określa jego lokalizację w pamięci podręcznej, a offset wskazuje na konkretny bajt w bloku.

* Skoro offset ma 5 bitów, to rozmiar bloku wynosi: $2^5 = 32$ bajty.
* Skoro indeks ma 5 bitów to liczba wierszy pamięci podręczenej wynosi: $2^5 = 32$.
* Liczba bitów metadanych: 23 (uwzględniając valid)
Liczba bitów składających się na dane w jednym bloku to rozmiar bloku 32 bajty = 256 bitów.

Zatem stosunek wynosi: $\frac{256}{23}≈11.13$

Zależy nam na tym by ten stosunek był jak największy.
## Zadanie 3
:::success
Autor: Piotr Warząchowski
:::

### Z 3

### **Sekwencja odwołań:**

Oto sekwencja odwołań w systemie dziesiętnym i odpowiednie obliczenia dla każdego odwołania:

- 0, 4, 16, 132, 232, 160, 1024, 28, 140, 3100, 180, 2180

### **Analiza zachowania pamięci podręcznej:**

1. **Adres 0**:
- **`Tag = 0000 0000`**
- **`Index = 00000`**
- **`Offset = 00000`**
- Jest to pierwsze odwołanie do tego adresu, więc jest to **compulsory miss**.
2. **Adres 4**:
- **`Tag = 00000 0000`**
- **`Index = 00000`**
- **`Offset = 00100`**
- Trafienie, ponieważ blok z adresem 0 zawiera już ten adres (bloki 32-bajtowe).
3. **Adres 16**:
- **`Tag = 0000 0000`**
- **`Index = 00000`**
- **`Offset = 10000`**
- Trafienie, wciąż w tym samym bloku.
4. **Adres 132**:
- **`Tag = 0`**
- **`Index = 00100`**
- **`Offset = 00100`**
- Inny indeks, więc **compulsory miss**.
5. **Adres 232**:
- **`Tag = 0`**
- **`Index = 00111`**
- **`Offset = 01000`**
- **Compulsory miss**, gdyż to nowy indeks.
6. **Adres 160**:
- **`Tag = 0`**
- **`Index = 00101`**
- **`Offset = 00000`**
- **Compulsory miss**, nowy indeks.
7. **Adres 1024**:
- **`Tag = 0000 0001`**
- **`Index = 00000`**
- **`Offset = 00000`**
- **Conflict miss**, inny tag w tym samym indeksie.
8. **Adres 28**:
- **`Tag = 0`**
- **`Index = 00000`**
- **`Offset = 11100`**
- **Conflict miss**, ponieważ adres 1024 zajął ten indeks i zmienia sie tag.
9. **Adres 140**:
- **`Tag = 0`**
- **`Index = 00100`**
- **`Offset = 01100`**
- Trafienie, blok z adresem 132 (ten sam indeks i tag).
10. **Adres 3100**:
- **`Tag = 0000 0011`**
- **`Index = 00000`**
- **`Offset = 11100`**
- **Conflict miss**, inny tag w tym samym indeksie.
11. **Adres 180**:
- **`Tag = 0`**
- **`Index = 00101`**
- **`Offset = 10100`**
- Trafienie, blok z adresem 160 (ten sam indeks i tag).
12. **Adres 2180**:
- **`Tag = 0000 0010`**
- **`Index = 00100`**
- **`Offset = 00100`**
- **Conflict miss**, inny tag w tym samym indeksie.

### **Podsumowanie:**

Wystąpiły 4 conflict miss.

- Procent trafień:

4/12×100%=33.33%

### **Zawartość pamięci podręcznej:**

- (Tag 11, Index 00000)
- (Tag 10, Index 00100)
- (Tag 0, Index 00101)
- (Tag 0, Index 00111)

## Zadanie 4
:::success
Autor: Patryk Flama
:::


(tutaj mamy 3-drożną, więc 3 drogi na zbiór)
-> blok długości 2 słów 32 bitowych = 64 bity = $2^3$ bajtów
-> $2^3$ bajtów na blok, więc 3 bity na offset
-> 24 bloki / 3 bloki na zbiór, więc mamy 8 zbiorów = $2^3$ czyli potrzebujemy 3 bity na index
-> reszta zostaje na tag = 26 bitów

|adres RAM|tag|index|offset|miss|
|----|--------|---|---|----|
|0 |..000000|000|000|compulsory miss|
|4 |..000000|000|100|hit|
|16 |..000000|010|000|compulsory miss|
|132 |..000010|000|100|compulsory miss|
|232 |..000011|101|000|compulsory miss|
|160 |..000010|100|000|compulsory miss|
|1024|..010000|000|000|compulsory miss|
|28 |..000000|011|100|compulsory miss|
|140 |..000010|001|100|compulsory miss|
|3100|..110000|011|100|compulsory miss|
|180 |..000010|110|100|compulsory miss|
|2180|..100010|000|100|conflict miss|

10 * compulosry miss
1 * conflict miss
1 * hit
procent trafień: 1/12 $\approx$ 8%
Końcowa pamięć
|index|tag|
|-----|---|
|000|10, 10000, 100010|
|001|10|
|010|0|
|011|0, 110000|
|100|10|
|101|11|
|110|10|


-> słowo długości 32 bity = $2^2$ bajtów
-> więc mamy 2 bity na offset
-> reszta zostaje na tag = 30 bitów

|adres RAM|tag|offset|miss|
|----|------------|--|----|
|0 |..0000000000|00|compulsory miss|
|4 |..0000000001|00|compulsory miss|
|16 |..0000000100|00|compulsory miss|
|132 |..0000100001|00|compulsory miss|
|232 |..0000111010|00|compulsory miss|
|160 |..0000101000|00|compulsory miss|
|1024|..0100000000|00|compulsory miss|
|28 |..0000000111|00|compulsory miss|
|140 |..0000010001|00|capacity miss|
|3100|..1100000111|00|capacity miss|
|180 |..0000101101|00|capacity miss|
|2180|..1000100001|00|capacity miss|

8 * compulsory miss
4 * capacity miss
0 * hit
procent trafień 0%

## Zadanie 5
:::success
Autor: Szymon Fluder

wyjaśnienie pojęć:
- write-back - kiedy coś ma być zapisane do pamięci, to jest najpierw zapisywane w cache i dopiero potem (kiedy n.p. inny proces potrzebuje danych albo w regularnych interwałach) przepisywane do RAM.
- write-allocate - jeśli chcemy zapisać coś do fragmentu pamięci, który nie jest w cache, to najpierw alokujemy miejsce na to w cache, a potem tam zapisujemy
- dirty bit - bit, który oznacza, że dane, które są w danym bloku w cache nie zostały przeniesione do RAM (a zostały zmodyfikowane).

Jest założenie, że L1 nie może się bezpośrednio komunikować z pamiecią RAM. Ogranicza to nas w ten sposób, że aby coś załadować do L1, trzeba to najpierw załadować do L2.

// nie ma w L1 danego bloku B

// zrobienie miejsca w L1 na zapisanie bloku B
if (L1 pełne){
    wybierz (i usun) victim block V (z L1)
    if (dirty bit zapalony w V){
        if (L2 pełne){
            wybierz victim blok V_2 (z L2)
            if (dirty bit zapalony w V_2){
                zapisz V_2 do RAM
            }
            ustaw bit valid V_2 w L2 na 0
        }
        zapisz V w L2
    }
    ustaw bit valid V w L1 na 0
}

// zapisywanie B w L1
if (B jest w L2){
    ustaw bit valid bloku B w L2 na 0
}else{
    sprowadź B do L2
}

zapisz zmiany w bloku B w L1
ustaw dirty bit B na 1

:::

## Zadanie 6
:::success
Autor: Wiktor Małek

*Dla procesora z L1*
$0.08 \cdot 70ns + 0.92 \cdot 0.66ns = 5.6+0.6072=6.2072ns$

*Dla procesora z L1 i L2*
$0.92 \cdot 0.66ns + (0.08 \cdot 0.995 \cdot 5.62ns) + (0.08 \cdot 0.005 \cdot 70ns)=1.0826ns$

*CPI dla procesora z L1*
$6.2072ns \approx 9.4$ cykle procesora
$0.64 + 0.36 \cdot 9.4 = 4.024$ CPI

*CPI dla procesora z L1 i L2*
$1.0826ns \approx 1.6$ cykli procesora
$0.64 + 0.36 \cdot 1.6 = 1.216$ CPI
:::

## Zadanie 7
:::success
Autor: Michał Chawar
:::


$log_2(4!) = log_2(24) \approx 5$
Mamy 5 bitów na zbiór, aby pamiętać historię dostępu do bloków.

Dla czasu $t$ oznaczmy indeksy bloków od najbardziej ostatnio używanego do najdawniej używanego przez $$B_1^t, B_2^t, B_3^t, B_4^t$$ Każdy z tych indeksów jest dwubitowy (bo bloki są cztery). W czasie $t$ ostatnio dostępu udzielono do bloku $B_1^t$, a najdawniej do bloku $B_4^t$.

Podzielmy nasze $5$ bitów $(a_4a_3a_2a_1a_0)$ na trzy grupy - pierwsze dwa bity to $B_1^t$, kolejne dwa to $B_2^t$, a ostatni bit reprezentuje wartość $B_3^t > B_4^t$. Zauważmy, że z tej reprezentacji możemy jednoznacznie odczytać ciąg $(B_1^t, B_2^t, B_3^t, B_4^t)$ w dowolnym czasie $t$. Wystarczy ją więc odpowiednio aktualizować przy żądaniach dostępu. Wtedy kandydatem do usunięcia ze zbioru w czasie $t$ będzie zbiór o indeksie $B_4^t$.

1. Dostęp do $B_1^t$
Nic nie zmieniamy

$B_1^{t+1} = B_1^t$
$B_2^{t+1} = B_2^t$
$B_3^{t+1} = B_3^t$
$B_4^{t+1} = B_4^t$

$(a_4a_3\ a_2a_1\ a_0) \rightarrow (a_4a_3\ a_2a_1\ a_0)$

2. Dostęp do $B_2^t$

$B_1^{t+1} = B_{\color{red}{2}}^t$
$B_2^{t+1} = B_{\color{red}{1}}^t$
$B_3^{t+1} = B_3^t$
$B_4^{t+1} = B_4^t$

$(a_4a_3\ a_2a_1\ a_0) \rightarrow (a_2a_1\ a_4a_3\ a_0)$

3. Dostęp do $B_3^t$

$B_1^{t+1} = B_{\color{red}{3}}^t$
$B_2^{t+1} = B_{\color{red}{1}}^t$
$B_3^{t+1} = B_{\color{red}{2}}^t$
$B_4^{t+1} = B_4^t$

$(a_4a_3\ a_2a_1\ a_0) \rightarrow (c_1c_0\ a_4a_3\ e_0)$,
gdzie $B_3^t \equiv (c_1c_0)$ i $e_0 \equiv B_3^{t+1} > B_4^{t+1}$

4. Dostęp do $B_4^t$

$B_1^{t+1} = B_{\color{red}{4}}^t$
$B_2^{t+1} = B_{\color{red}{1}}^t$
$B_3^{t+1} = B_{\color{red}{2}}^t$
$B_4^{t+1} = B_{\color{red}{3}}^t$

$(a_4a_3\ a_2a_1\ a_0) \rightarrow (d_1d_0\ a_4a_3\ e_0)$,
gdzie $B_4^t \equiv (d_1d_0)$ i $e_0 \equiv B_3^{t+1} > B_4^{t+1}$

## Zadanie 8
:::success
Autor: Maciej Dengusiak


x[2][128] - 1024 bajty

a) Liczba zbiorów: 512/16 = 32

Kolejne odwolania do pamieci:
- [0, 1, 2, 3] trafi do zbioru nr 1 - `MISS compulsory`
- [128, 129, 130, 131] trafi do zbioru nr 1 - `MISS conflict`
- ponownie [0, 1, 2, 3] trafi do zbioru nr 1 - `MISS conflict`
...
- [4, 5, 6, 7] trafi do zbioru nr 2 - `MISS compulsory`
...

Mamy stąd 100% miss

b) Liczba zbiorów: 1024/16 = 64

Tutaj skoro liczba zbiorów to 64 to mamy dodatkowy bit informacji w *s*.

Dzięki temu nie nakładają nam się 0 z 128, bo:
- movq 0: [0, 1, 2, 3] trafi do set nr 1
- movq 128: [128, ... 131] trafi do set nr 33
- movq 1: odczytujemy wartosc zapisana w set1, tak smao z 129, 2, 130, 3, 131
- kolejno tak samo postąpimy dla [4, 5, 6, 7] oraz [132, ..., 135]

Stąd mamy 25% miss

c) Tu sytuacja jest analogiczna do b)

- movq 0: [0, 1, 2, 3] trafi do set nr 1 na miejsce nr 1
- movq 128: [128, ..., 131] trafi do set nr 1 na miejsce nr 2,
- movq 1: wyciagamy z set 1 z nr 1

Stad rowniez mamy 25% miss

1) Zwiększenie pamięci nie zmniejszy liczby missów ponieważ te missy wiaza sie z wczytaniem bloku do pustego miejsca w pamieci
2) Zwiekszenie rozmiaru bloku natomiast spowoduje zmniejszenie współczynnika chybień.
Współczynnik chybien dla bloku dlugosci x wynosiłby: 1/x.

:::

## Zadanie 9
:::success
Autor: Szymon Fluder

1. 32KB pamięci; rozmiar bloku to 8 bajtów; mapowanie bezpośrednie => 4096 zbiorów
2. 307200 pikseli
3. pętla idzie po kolumnach (od prawego końca ekranu), od dołu do góry
4. jedna kolumna ma $480 \cdot 4B = 1920B$

"""
32KiB cache, rozmiar bloku 8 bajtów => 4096 zbiorów
8 bajtów na blok => offset ma 3 bity [2..0]
12 bitów na index => bity [14..3]
reszta bitów na tag
"""

CACHE = [-1] * 4096
HITS = 0
MISSES = 0

def main():
    global HITS
    global MISSES
    global CACHE
    for j in range(639, -1, -1):
        for i in range(479, -1, -1):
            index_mask = 0xFFF
            tag_mask = ~0x0
            struct_address = 4 * (480 * i + j)

            # symulacja dostępów do kolejnych bajtów structa
            for offset in range(4): 
                index = ((struct_address + offset) >> 3) & index_mask
                tag = ((struct_address + offset) >> 15) & tag_mask
                if CACHE[index] == tag:
                    HITS += 1
                else:
                    CACHE[index] = tag
                    MISSES += 1


def bin_print(x: int):
    for i in range(31, -1, -1):
        if (x >> i) & 1:
            print('1 ', end='')
        else:
            print('0 ', end='')
    print('')


if __name__ == '__main__':
    main()
    print(f"trafienia: {HITS}")
    print(f"hybienia: {MISSES}")
    print(f"wsp. trafień: {HITS/(4 * 640*480)}")

:::