---
# System prepended metadata

title: 'Ćwiczenia 10, grupa cz. 10-12, 9 maja 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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 		
:::

![image](https://hackmd.io/_uploads/BJAeitF-0.png)

![image](https://hackmd.io/_uploads/B1hog5YZ0.png)

| 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		
:::

![obraz](https://hackmd.io/_uploads/H1D-wdKfA.png)

![obraz](https://hackmd.io/_uploads/SJXJDZqfR.png)

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		
:::
![image](https://hackmd.io/_uploads/BkRpcwKG0.png)
![image](https://hackmd.io/_uploads/rylgjwFGR.png)

![image](https://hackmd.io/_uploads/SkL2luYGA.png)

![image](https://hackmd.io/_uploads/HkaspPYMR.png)
(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|

![image](https://hackmd.io/_uploads/rkI97McGA.png)

-> 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
![image](https://hackmd.io/_uploads/SkO9KuXMA.png)

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	
![zad_6_polecenie](https://hackmd.io/_uploads/SJt-OWqMA.jpg)

*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		
:::

![image](https://hackmd.io/_uploads/rkwSH-cGC.png)

$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

![image](https://hackmd.io/_uploads/ry2CPZczC.png)

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 	
![image](https://hackmd.io/_uploads/BkeBkpmfA.png)

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$
```python=
"""
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)}")
```
:::



