---
# System prepended metadata

title: 'Ćwiczenia 9, grupa śr. 10-12, 26 kwietnia 2023'
tags: [pwit, ćwiczenia, SYK23]

---

# Ćwiczenia 9, grupa śr. 10-12, 26 kwietnia 2023

###### tags: `SYK23` `ć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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk            |       |     |     |     |     |     |     |     |     | 
Mikołaj Dworszczak       |       |     |     |     |     |     |     |     |     |
Kacper Jóźwiak           |==X==  | X   | X   |   X |  X  | X   |     |     |     |
Dominik Kiełbowicz       |       |     |     |     |     |     |     |     |     |
Michał Kolasa            |       |     |     |     |     |     |     |     |     |
Konrad Kowalczyk         |   X   |  X  |  X  |  X  |  X  |  X  |     |     |     |
Oskar Kropielnicki       |   X   |  X  |  X  |  X  |     |  X  |  X  |     |     |
Anna Krysta              |   X   |  X  |  X  |  X  |  X  |  X  |  X  |     |     |
Jakub Krzyżowski         |   X   |  X  |  X  |  X  |  X  |  X  |  X  |     |     |
Oskar Kubkowski          |   X   |  X  |  X  |  X  | X   |  X  |     |     |     |
Mateusz Mazur            |   X    |  X   |  X   |  X   |     |  X   |     |     |     |
Barbara Moczulska        |   X   |  X  |  X  |  X  |  X  |  X  |     |     |     |
Kacper Sojda             |   X    |  X   |  X   |  X   |  X   |  X   |  X   |     |     |
Marta Strzelec           |    x   |  x   | x    |  x   |  x   |  x   |     |     |     |
Mikołaj Swoboda          |   X   |  X  |  X  |  X  |  X  |  X  |     |     |     |
Filip Szczepański        |  X   |  X   |  X   |  X   |  X   |  X   |     |     | X   |
Julian Włodarek          |  X   |  X   |  X   |  X   |  X   |  X   |     |     | X   |
Beata Łakoma             |   x    |  x   |   x  |   x  |  x   | x    |     |     |     |
Michał Łukasik           |   X   |  X  |  X  |  X  |     |  X  |     |     |     |
:::





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




## Zadanie 1
:::success
Autor:	Kacper Jóźwiak	
:::
Pierwsze dwie cyfry to tag. Ostatnia to indeks i offset.

  * $832_{(16)} = 100000110010_{(2)}$
  tag: 10000011
  indeks: 00
  offset: 10

  * $835_{(16)} = 100000110101_{(2)}$
  tag: 10000011
  indeks: 01
  offset: 01

  * $FFD_{(16)} = 111111111101_{(2)}$
  tag: 11111111
  indeks: 11
  offset 01

| Adres    |Trafienie?| Wartość  |
| -------- | -------- | -------- |
| 832      | Tak      |    CC    |
| 835      | Nie      |    ...   |
| FFD      | Tak      |    C0    |


## Zadanie 2
:::success
Autor:	Marta Strzelec	
:::

![](https://i.imgur.com/JhEWb68.png)

A) Wiemy, że offset ma 5 bitów, czyli łącznie liczba możliwych offsetów to $2^{5} = 32$
Blok ma rozmiar 32 bajtów.

B) Wierszy jest tyle co indexów. $2^5 = 32$

C) $\frac{32*8}{22+1} \approx 11.13$
## Zadanie 3
:::success
Autor:	Beata Łakoma	
:::

![](https://i.imgur.com/L3j1BJU.png)


tag-22
indeks-5
offset-5 

|num| tag | indeks| offset| res |
|---| ----| ------| ------| ----|
|0 | 0 | 0 | 0 |comp-miss |
|4| 0 | 0 |00100 | hit |
|16 | 0 | 0 | 10000 | hit |
|132| 0 |00100 | 00100 | comp-miss |
|232 | 0 | 00111 | 01000 | comp-miss |
|160 | 0 | 00101 | 0 | comp-miss |
|1024 | 1 | 0 | 0 | conf-miss |
|28 | 0 | 0 | 11100 | conf-miss |
|140 | 0 | 00100 | 01100 | hit |
|3100 | 11 | 0| 11000 | conf-miss |
|180 | 0 | 00101 | 10100 | hit |
|2180 | 10 | 00100 | 00100 | conf-miss |

pamieć (pomijam indeksy gdzie nie zapisaliśmy)

|num| tag|
|--|--|
|000| 11 |
|100| 10 |
|101| 0 |
|111| 0 |

4 hity 
12 zapytań 
efektywność 4/12 ~ 33%
## Zadanie 4
:::success
Autor:	Konrad Kowalczyk	
:::
![](https://i.imgur.com/EJrHZpd.png)

**polityka wymiany LRU** - (**L**east **R**ecently **U**sed) w sytuacji chybienia, zastąpieniu ulega najdawniej użyty wiersz z danego zbioru

**1.** Blok ma długość 2 słów, tzn. 64 bity = 8 bajtów. 8 = 2<sup>3</sup>, zatem na offset przeznaczone są 3 bity. Liczba bloków to 24, a w każdym zbiorze mogą znajdować się maksymalnie 3 bloki, tzn. liczba zbiorów wynosi $\frac{24}{3}$ = 8. Podobnie 8 = 2<sup>3</sup>, zatem na indeks przeznaczone są również 3 bity. Na znacznik w takim razie przeznaczone jest 32 - 3 - 3 = 26 bitów.

| Adres | Znacznik | Indeks | Offset | Rodzaj |
| :---: | :---: | :---: | :---: | :---: |
| 0 | 00000000000000000000000000 | 000 | 000 | chybienie przymusowe |
| 4 | 00000000000000000000000000 | 000 | 100 | trafienie |
| 16 | 00000000000000000000000000 | 010 | 000 | chybienie przymusowe |
| 132 | 00000000000000000000000010 | 000 | 100 | chybienie przymusowe |
| 232 | 00000000000000000000000011 | 101 | 000 | chybienie przymusowe |
| 160 | 00000000000000000000000010 | 100 | 000 | chybienie przymusowe |
| 1024 | 00000000000000000000010000 | 000 | 000 | chybienie przymusowe |
| 28 | 00000000000000000000000000 | 011 | 100 | chybienie przymusowe |
| 140 | 00000000000000000000000010 | 001 | 100 | chybienie przymusowe |
| 3100 | 00000000000000000000110000 | 011 | 100 | chybienie przymusowe |
| 180 | 00000000000000000000000010 | 110 | 100 | chybienie przymusowe |
| 2180 | 00000000000000000000100010 | 000 | 100 | chybienie w wyniku kolizji na adresie |

a) Zastąpienie następowało po każdym chybieniu, a zatem zastąpionych zostało 11 bloków.
b) Na 12 odwołań nastąpiło 1 trafienie, czyli  $\frac{1}{12} = 0.08(3)$, zatem procentowo $8.(3)\%$.
c) Zawartość pamięci podręcznej po wykonaniu odwołań:

| Indeks | Znacznik | Dane |
| :---: | :---: | :---: |
| 000 <br /> 000 <br /> 000 | 00000000000000000000100010 <br /> 00000000000000000000000010 <br /> 00000000000000000000010000 | ... <br /> ... <br /> ... |
| 001 | 00000000000000000000000010 | ... |
| 010 | 00000000000000000000000000 | ... |
| 011 <br /> 011 | 00000000000000000000000000 <br /> 00000000000000000000110000 | ... <br /> ... |
| 100 | 00000000000000000000000010 | ... |
| 101 | 00000000000000000000000011 | ... |
| 110 | 00000000000000000000000010 | ... |

**2.** Blok ma długość 1 słowa, tzn. 32 bity = 4 bajty. 4 = 2<sup>2</sup>, zatem na offset przeznaczone są 2 bity. W pamięci podręcznej w pełni asocjacyjnej nie ma zbiorów, a zatem nie ma bitów przeznaczonych na indeks. Na znacznik w takim razie przeznaczone jest 32 - 2 = 30 bitów.

W pamięci podręcznej w pełni asocjacyjnej nie dochodzi do problemu chybienia w wyniku kolizji na adresie, ponieważ nie ma zbiorów. Zamiast tego, jeżeli przekroczymy dostępną liczbę bloków (w naszym przypadku 8) dochodzi do chybień w wyniku przekroczenia pojemności (ang. capacity miss).

| Adres | Znacznik | Offset | Rodzaj |
| :---: | :---: | :---: | :---: |
| 0 | 000000000000000000000000000000 | 00 | chybienie przymusowe |
| 4 | 000000000000000000000000000001 | 00 | chybienie przymusowe |
| 16 | 000000000000000000000000000100 | 00 | chybienie przymusowe |
| 132 | 000000000000000000000000100001 | 00 | chybienie przymusowe |
| 232 | 000000000000000000000000111010 | 00 | chybienie przymusowe |
| 160 | 000000000000000000000000101000 | 00 | chybienie przymusowe |
| 1024 | 000000000000000000000100000000 | 00 | chybienie przymusowe |
| 28 | 000000000000000000000000000111 | 00 | chybienie przymusowe |
| 140 | 000000000000000000000000100011 | 00 | chybienie w wyniku przekroczenia pojemności |
| 3100 | 000000000000000000001100000111 | 00 | chybienie w wyniku przekroczenia pojemności |
| 180 | 000000000000000000000000101101 | 00 | chybienie w wyniku przekroczenia pojemności |
| 2180 | 000000000000000000001000100001 | 00 | chybienie w wyniku przekroczenia pojemności |

a) Zastąpienie następowało po każdym chybieniu, a zatem zastąpionych zostało 12 bloków.
b) Na 12 odwołań nie nastąpiło żadne trafienie, czyli  $\frac{0}{12} = 0$, zatem procentowo $0\%$.
c) Zawartość pamięci podręcznej po wykonaniu odwołań:

| Znacznik | Dane |
| :---: | :---: |
| 000000000000000000000000100011 <br /> 000000000000000000001100000111 <br /> 000000000000000000000000101101 <br /> 000000000000000000001000100001 <br />  000000000000000000000000111010 <br /> 000000000000000000000000101000 <br /> 000000000000000000000100000000 <br /> 000000000000000000000000000111 | ... <br /> ... <br /> ... <br /> ... <br /> ... <br /> ... <br /> ... <br /> ... |


## Zadanie 5
:::success
Autor:	Barbara Moczulska	
:::
![](https://i.imgur.com/rouJ9We.png)

**write-back** - odroczenie zapisu do pamięci do czasu wymiany linii) Każda linia pamięci podręcznej potrzebuje dirty bit (ustawianego, jeśli dane zostały zapisane)

**write-allocate** - możliwe że po zapisie będzie niedługo odczyt dlatego ładujemy do pamięci podręcznej i dopiero wtedy modyfikujemy

**bit dirty** - czy zawartość bloku została zmodyfikowana od ostatniego wczytania z pamięci

Chybienie przy zapisie do L1:
![](https://i.imgur.com/f0WYHqU.jpg)


Wersja poprawiona:

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


## Zadanie 6
:::success
Autor:	Mikołaj Swoboda	
:::
$$
AMAT = t_\text{hit} + p_\text{miss}\cdot t_\text{avg miss} \\
AMAT_1 = 0{,}66 + 0{,}08 \cdot 70 = 6{,}26 \\
AMAT_2 = 0{,}66 + 0{,}08 \cdot (5{,}62 + 0{,}005 \cdot 70) = 1{,}1376 \\
CPI = 0{,}64 + 0{,}36 \cdot AMAT \cdot \frac{1}{0{,}66} \\
CPI_1 \approx 4{,}05 \\
CPI_2 \approx 1{,}26  
$$

$$
AMAT = (1 - p_\text{miss}) * t_\text{hit} + p_\text{miss} * (t_\text{hit} + t_\text{avg miss}) \\
$$


## Zadanie 7
:::success
Autor:	Jakub Krzyżowski	
:::
![](https://i.imgur.com/Wm6WawX.png)

Założenie: $log_2(4!) = 5$
Na 2 bitach możemy zapisać liczby 0, 1, 2, 3 - pozycje danego bloku
Pierwsze 2 bity - pozycja najstarszego bloku
Kolejne 2 - pozycja prawie najstarszego bloku
Ostatni bit - 1 jeśli najmłodszy blok znajduje się wcześniej w kolejności, niż ten prawie najmłodszy

Kandydatem do usunięcia będzie blok na którego pozycję wskazują 2 pierwsze bity

Aktualizacja informacji (przed dostępem do bloku - kolejność według 'starości' A B C D):
1) Dostęp do najmłodszego bloku: nic nie musimy robić (A B C D)
2) Dostęp do prawie najmłodszego bloku: zanegować ostatni bit (A B D C)
3) Dostęp do prawie najstarszego bloku: zapisać pozycję prawie najmłodszego bloku w miejscu prawie najstarszego, najmłodszy blok staje się prawie najmłodszym, prawie najstarszy blok staje się najmłodszym, porównać pozycję prawie najmłodszego i najmłodszego i zapisać odpowiednio w 5-tym bicie (A C D B)
4) Dostęp do najstarszego bloku: shift o 2 bity w lewo pierwszych 4 bitów, na 3 i 4 bicie zapisać pozycję bloku C, porównać pozycję bloków A i D i zapisać odpowiednio w 5-tym bicie (B C D A)

## Zadanie 8
:::success
Autor: Anna Krysta	
:::
![](https://hackmd.io/_uploads/HktEBAOV2.jpg)

W trzech tych przypadkach współczynnik chybień będzie równy 25%. W pierwszym przypadku, gdy blok będzie po raz pierwszy inicjalizowany, wtedy będzie chybienie. Natomiast dla trzech pozostałych miejsc z tego bloku będzie następowało trafienie. Tak samo jest z drugim i trzecim przypadkiem. Czyli na cztery odwołania do pamięci, trzy z nich to będzie chybienie, stąd 25% chybień. Jeżeli chodzi o możliwość polepszenia tych statystyk, to być może pomogłoby zwiększenie rozmiaru bloku.


Punkt 1.

Rozkład adresu na składniki:

?? bitów tagu | 5 bitów na numer zbioru | 4 bity na offset


`x[0][0]` znajduje się pod adresem `0`: tag:0, zbiór:0, offset: 0
`x[1][0]` znajduje się pod adresem `512`: 1|00000|0000`

obydwa te adresy trafiają do jednego setu. Odniesienie do x[1][0] powoduje `conflict miss`


x[0][0] x[1][0] x[0][1] x[1][1] .... //100% missów
~~x[0][0] x[1][0] x[1][1] x[0][1]
~~ schemat odwołania do pamięci zależny od decyzji kompilatora (tego nie rozważamy)

100%


Punkt 2. 25%
Punkt 3. 25%

## Zadanie 9

:::success
Autor:	Julian Włodarek	
:::
![](https://i.imgur.com/mPz8GOs.png)

Jeden pixel zajmuje w pamięci 4B, bo jest równy 4*sizeof(char).
W bloku o wielkości 8B mieszczą się 2 pixele, buffer[i][j] oraz buffer[i][j+1], dla j parzystych oraz dowolnych i, to znaczy, że mają taki sam index i tag.
![](https://i.imgur.com/OXXUDpG.png)

Zauważmy, że nasz program posiada słabą lokalność przestrzenną, bo w kolejnych wykonaniach pętli wewnętrznej for odwołuje się najpierw do buffer[i][j], a następnie do buffer[i-1][j].

Pamięć podręczna ma wielkość 32KB. Wielkość bloku to 8B, a ilość zbiorów (set) to 32KB / 8B = 4096.

Pierwsze odwołanie do pamięci będzie skutkować missem, a 3 kolejne hitem, więc współczynnik trafień to 75%.

Gdybyśmy zamienili miejscami pętle to mielibyśmy lepszą lokalność przestrzenną i mielibyśmy 1 miss na 7 hitów więc 87,5%.

```
#include <iostream>

void bad_cache_test(){
    int cache_size = 1 << 15; //32KB
    int blok_size = 1 << 3; // 8B
    int sets = 1 << 12; // sets = cashe_size/blok_size

    int cache[sets];
    for (int i = 0; i < sets; i++)
        cache[i] = -1;

    int hit = 0, miss = 0;

    for (int j = 639; j >= 0 ; j--)
        for (int i = 479; i >= 0 ; i--) {
            int addres = ((i * 640) + j) * 4;
            int index = (addres >> 3) & ((1<<12) - 1);
            int tag = (addres >> 3) >> 12;
            for (int k = 0; k < 4; k++) {
                if(cache[index] == tag)
                    hit++;
                else
                    miss++;
                cache[index] = tag;
            }
        }

    printf("%.2f%%\n", 100 * (float)hit/(float)(hit+miss));
}

void good_cache_test(){
    int cache_size = 1 << 15; //32KB
    int blok_size = 1 << 3; // 8B
    int sets = 1 << 12; // sets = cashe_size/blok_size

    int cache[sets];
    for (int i = 0; i < sets; i++)
        cache[i] = -1;

    int hit = 0, miss = 0;

    for (int i = 479; i >= 0 ; i--)
        for (int j = 639; j >= 0 ; j--){
            int addres = ((i * 640) + j) * 4;
            int index = (addres >> 3) & ((1<<12) - 1);
            int tag = (addres >> 3) >> 12;
            for (int k = 0; k < 4; k++) {
                if(cache[index] == tag)
                    hit++;
                else
                    miss++;
                cache[index] = tag;
            }
        }

    printf("%.2f%%\n", 100 * (float)hit/(float)(hit+miss));
}

int main() {
    bad_cache_test();
    good_cache_test();
    return 0;
}

```
