# Ćwiczenia 10, grupa śr. 12-14, 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | X | X | ==X== | X | X | X | | | |
Małgorzata Galińska | X | X | X | X | | | | | |
Maria Hreniak | X | X | X | X | | | | | |
Jakub Jankowski | X | X | X | X | | X | | | |
Mikołaj Kalitka | | | | | | | | | |
Julia Konefał | X | X | X | X | ==X== | X | | | |
Julia Kulczycka | X | ==X== | X | | | X | | | |
Cecylia Łyjak | X | X | X | X | X | ==X== | | | |
Adam Majchrowski | ==X== | X | X | X | | X | | | |
Piotr Mańkowski | | | | | | | | | |
Piotr Salamon | | | | | | | | | |
Maciej Szałasz | X | X | X | | | X | | | |
:::

Poniżej można zadeklarować zadanie **5**, **6** oraz **7** z **listy 9**:

:::danger
| | 9.5 | 9.6 | 9.7 |
| ----------------------:| -----| -----| -----|
Mikołaj Balwicki | | | |
Małgorzata Galińska | | X | |
Maria Hreniak | | | |
Jakub Jankowski | | X | |
Mikołaj Kalitka | | | |
Julia Konefał | | | |
Julia Kulczycka | | | |
Cecylia Łyjak | | | |
Adam Majchrowski | | | |
Piotr Mańkowski | | | |
Piotr Salamon | | | |
Maciej Szałasz | | | |
:::

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

## Zadanie 1
:::success
Autor: Adam Majchrowski

:::

## Zadanie 2
:::success
Autor: Julia Kulczycka
:::
**Pamięć podręczna z mapowaniem bezpośrednim adresowana bajtowo** oznacza, że każdy blok danych jest przypisany do określonego miejsca w pamięci podręcznej na podstawie jego adresu bajtowego. **Oznacza to, że każdy wiersz w pamięci cache odpowiada jednemu blokowi danych**.

- Wiemy z treści, że offset ma 5-bitów, więc liczba ofsetów to $2^5 = 32$. Blok ma rozmair 32-bajtów.
- Wierszy jest jest tyle co indeksów, czyli $2^5 = 32$
- $32*8/(22+1) = 11.13$ (bity bloku/bity metadanych)

## Zadanie 3
:::success
Autor: Mikołaj Balwicki
:::
hit – trafienie (w tym secie znajduje się blok o danym tagu) [4] (33,3%)
comp – zimne chybienie (w tym secie nie ma żadnego bloku) [4]
conf – konflikt (w tym secie jest blok o innym tagu) [4]

## Zadanie 4
:::success
Autor: Maria Hreniak
:::





## Zadanie 5
:::success
Autor: Julia Konefał

:::

## Zadanie 6
:::success
Autor: Cecylia Łyjak
:::
==CPI== - "Cycles Per Instruction". Jest to miara używana do określenia średniej liczby cykli zegarowych potrzebnych do wykonania pojedynczej instrukcji przez procesor. Im niższa wartość CPI, tym efektywniej działa procesor.

Wiemy, że im większa pamięć podręczna tym dłuższy czas dostępu do niej. Załóżmy, że dostęp do pamięci głównej trwa 70ns, a dostępy do pamięci stanowią 36% wszystkich instrukcji. Rozważmy system z pamięcią podręczną o następującej strukturze: L1 – 2 KiB, współczynnik chybień 8.0%, czas dostępu 0.66ns (1 cykl procesora); L2 – 1 MiB, współczynnik chybień 0.5%, czas dostępu 5.62ns. Odpowiedz na pytania:
1) Jaki jest średni czas dostępu do pamięci dla procesora tylko z cache L1, a jaki dla procesora z L1 i L2?

L1 : 0.66ns + 0.08 * 70ns = 6.26ns
L1 + L2 : 0.66ns + 0.08(5.62ns + 0.005 * 70ns) = 1.138ns

2) Zakładając, że procesor charakteryzuje się współczynnikiem CPI (ang. cycles per instruction) równym 1.0 (bez wykonywania dostępów do pamięci), oblicz CPI dla procesora tylko z cache L1 i dla procesora
z L1 i L2.

L1 : 1 + (0.36 * 6.26) / 0.66 = 4.41
L1 + L2 : 1 + (0.36 * 1.138) / 0.66 = 1.62

(CPI bez dostępów pamięci + (procent instrukcji * średni czas wykonania) / czas 1 cyklu procesora)
&-------------------------------------------------------------------------------------------------


## Zadanie 7
:::success
Autor: Adam Majchrowski

:::

## Zadanie 8
:::success
Autor: Mikołaj Balwicki
:::
Int ma 4 bajty, a x jest tablicą zawierającą w sobie 2 tablice 1-wymiarowe długości 128 intów.

Zatem x[k][i] jest równoznacznie odwołaniu się do komórek pamięci z zakresu od (k\*128+i)\*4 do (k\*128+i)\*4 + 3. Binarnie 2 ostatnie bity określają pozycję bajtu w incie, 7 poprzednich – pozycję inta w tablicy 1-wymiarowej długości 128, a pierwszy – pozycję tablicy 1-wymiarowej w tablicy x.

Przykład - x[1][13] odwołuje się do adresów 0x234, 0x235, 0x236, 0x237 (dziesiętnie 564, 565, 566, 567)


Mamy 16 bajtów w bloku (za offset odpowiadają 4 ostatnie bity adresu), czyli do jednego bloku trafiają bajty 4 kolejnych intów w tablicy. Innymi słowy, jeden blok przechowuje wartości { x[k][a\*4], x[k][a\*4+1], x[k][a\*4+2], x[k][a\*4+3] }, gdzie a należy do {0, 31}.

Rozmiar pamięci wynosi 512 bajtów, a rozmiar jednego bloku 16. Zatem mamy 32 bloki w naszej pamięci, po jednym w każdym zbiorze (bezpośrednie mapowanie).
Skoro mamy 32 zbiory, to informacja o zbiorze zapisywana jest na 5 bitach adresu. Jak łatwo zaobserwować, jest to informacja kodująca a (patrz wyżej).

Zatem tag zawiera jedynie informacje o położeniu całej tablicy 1-wymiarowej w pamięci, czyli maksymalnie tylko jeden z jego bitów będzie się różnił przy różnych odczytach.


Z powyższych dwóch informacji można wywnioskować, że cold miss wystąpi przy pierwszym wczytaniu wartości z przedziału x[k][a\*4], x[k][a\*4+3], a conflict miss – przy wczytaniu wartości o drugim indeksie z tego samego przedziału [a\*4, a\*4+3] ale różnym pierwszym indeksie.

Jak można zauważyć w programie, odczytywane są naprzemiennie wartości o tym samym drugim indeksie z dwóch różnych tablic. Zatem każdy odczyt pamięci zakończy się chybieniem.

(2) Jeśli rozszerzymy rozmiar pamięci do 1024 bajtów, będziemy mogli w niej pomieścić 64 bloki. Wówczas informacja o indeksie zbioru będzie kodowana na 6 bitach adresu, czyli obejmować będzie zarówno kodowanie a, jak i kodowanie k. Wtedy w zbiorze o danym indeksie może wylądować tylko jeden blok, więc nigdy nie dojdzie do conflict missów. Do cold missu dojdzie przy pierwszym wczytaniu zadanej kombinacji k i a. Ponieważ wewnątrz danej tablicy wartości wczytywać będziemy po kolei, dojdzie do tego gdy i będzie podzielne przez 4, czyli w ¼ przypadków.

(3) Jeśli zamiast tego uczynimy pamięć 2-drożną, będzie w stanie pomieścić 16 zbiorów po 2 bloki. Niech nasze a = 16\*b+c, gdzie b należy do {0, 1} a c do {0, 15}.

Skoro mamy 16 zbiorów, informacja o zbiorze będzie kodowana na 4 bitach adresu. Będą to bity odpowiedzialne za kodowanie c. Wtedy tag zawiera informacje o k i b (czyli o k i pierwszym bicie a).


Przy kolejnych odczytach k będzie naprzemiennie przyjmowało wartości z zakresu {0, 1}, jednak b będzie pozostawać niezmienne tak długo jak pierwszy bit drugiego indeksu pozostanie niezmienny.

Więc przechowując w jednym zbiorze dwa bloki nie dojdzie do conflict missu dopóki wartość b się nie zmieni, a do tego dojdzie gdy i = 64. Wówczas zaraz po sobie zostaną zastąpione oba bloki, czyli dojdzie do dwóch conflict missów pod rząd. Innymi słowy conflict missem zakończy się 1/128 odczytów.

Do cold missu dojdzie w tej samej sytuacji co w poprzednim przypadku, czyli gdy i mod 4 = 0. To ten sam moment w którym dojdzie do conflict missu, więc możemy zamiast tego powiedzieć że dojdzie do (jakiegoś) chybienia w ¼ przypadków.

## Zadanie 9
:::danger
Autor: do zadeklarowania na następnych ćwiczeniach
:::