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


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


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

**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³, 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³, 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², 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
:::

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

Wersja poprawiona:


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

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

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

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.

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;
}