# Ćwiczenia 9, grupa śr. 17-19, 11. maja 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | | | | |
Kamila Brzozowska | X |==X==| X | X | X | X | X | X | |
Adam Ciężkowski | X | X | X | X | X | ==X== | X | X | |
Natalia Czerep | X | X | X | | X | X | | | |
Jan Dalecki | X | X | X | X | X | X | X | | X |
Marko Golovko | X | X | X | X | X | X | | X | |
Adam Górkiewicz | X | X | X | X | X | X | X | ==X== | |
Piotr Gunia | X | X | X | X | X | X | X | | |
Krzysztof Jadłowski | ==X== | X | X | X | X | X | X | X | |
Magdalena Jarecka | X | X | X | | X | X | | | |
Mikołaj Jaszcza | X | X | X | X | X | X | X | | |
Monika Jędrzejkowska | | | | | | | | | |
Michał Kierul | X | X | X | | X | X | X | | |
Damian Lukas | | | | | | | | | |
Karol Ochman-Milarski | | | | | | | | | |
Piotr Piesiak | | | | | | | | | |
Damian Ratajski | | | | | | | | | |
Aleksandra Rozkrut | X | X | X |==X==| X | X | X | | |
Marcin Sarnecki | X | X | X | X | X | X | X | X | |
Maria Szlasa | X | X | X | X | | X | | | |
Mateusz Burdyna | X | X | X | | | X | | | |
Magdalena Słonińska | | | | | | | | | |
Nikola Wrona | X | X | X | X | X | X | | | |
Marcin Wróbel | X | X |==X==| X | X | X | X | X | |
:::

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

## Zadanie 1
:::success
Autor: Krzysztof Jadłowski
:::
Pierwsze dwie cyfry mówią nam o znaczniku(tagu), a trzecia o indeksie i offsecie.
## 832)
tag 83, 2-> set 00, offset 10
## 835)
tag 83, 5-> set 01, offset 01
## FFD)
tag FF, D-> set 11, offset 01

Ostatecznie

## Zadanie 2
:::success
Autor: Kamila Brzozowska
:::


Pamieć podręczna z mapowaniem bezpośrednim adresowana bajtowo - w każdym zbiorze jest zapamiętany tylko jeden wiersz


tag -> 31-10 (22 bity)
index -> 9-5 (5 bitów)
offset -> 4-0 (5 bitów)


1) Rozmiar bloku to $2^b$, gdzie b to liczba bitów przeznaczona na offset. Zatem rozmiar bloku to 32 bajty
2) Index ma 5 bitów, więc będą $2^s=2^5=32$ wiersze (0-31)
3) 23 bity zajmują matadane (valid + tag), a dane zajmują 32 bajty, zatem stosunek wynosi 8*32:23=256:23

## Zadanie 3
:::success
Autor Marcin Wróbel
:::

Zgodnie z poprzednim zadaniem
**Tag** ma **22** bity
**Index** ma **5** bitów
**Offset** ma **5** bitów

| Adres | Zapis bitowy | Tag | Index | Offset | Trafienie? |
| -----:| --------------:| ---:| -----:| ------:|:--------------- |
| 0 | 0 00000 00000 | 0 | 00000 | 00000 | compulsory miss |
| 4 | 0 00000 00100 | 0 | 00000 | 00100 | hit |
| 16 | 0 00000 10000 | 0 | 00000 | 10000 | hit |
| 132 | 0 00100 00100 | 0 | 00100 | 00100 | compulsory miss |
| 232 | 0 00111 01000 | 0 | 00111 | 01000 | compulsory miss |
| 160 | 0 00101 00000 | 0 | 00101 | 00000 | compulsory miss |
| 1024 | 1 00000 00000 | 1 | 00000 | 00000 | conflict miss |
| 28 | 0 00000 11100 | 0 | 00000 | 11100 | conflict miss |
| 140 | 0 00100 01100 | 0 | 00100 | 01100 | hit |
| 3100 | 11 00000 11100 | 11 | 00000 | 11000 | conflict miss |
| 180 | 0 00101 10100 | 0 | 00101 | 10100 | hit |
| 2180 | 10 00100 00100 | 10 | 00100 | 00100 | conflict miss |
- Jak wiele bloków zostało zastąpionych?
Nastąpiło **8** zastąpień

- Jaka jest efektywność pamięci podręcznej (liczba trafień procentowo)?
$\frac{4}{12}=\textbf{33,(3)}\%$

- Zawartość pamięci podręcznej po wykonaniu powyższych odwołań:
(tag, index, ... )
(11, 0, ...)
(10, 100, ...)
(0, 101, ...)
(0, 111, ...)

## Zadanie 4
:::success
Autor: Aleksandra Rozkrut
:::


least recently used (LRU) - usuwamy z cache najdawniej używany blok

blok: 2 * 4B = 8B = 2^3B -> offset 3 bity
24 bloki i po 3 bloki na zbiór -> 8 zbiorów -> index 3 bity

|Odwołanie | tag | index | offset |hit/miss|
|---------:|-----|-------|--------|--------|
|0|0|0|0|MISS compulsory|
|4|0|0|4|HIT|
|16|0|2|0|MISS compulsory|
|132|2|0|4|MISS compulsory|
|232|3|5|0|MISS compulsory|
|160|2|4|0|MISS compulsory|
|1024|16|0|0|MISS compulsory|
|28|0|3|4|MISS compulsory|
|140|2|1|4|MISS compulsory|
|3100|48|3|4|MISS compulsory|
|180|2|6|4|MISS compulsory|
|2180|34|0|4|MISS conflict|

pamięć:
|zbiór|tag|tag|tag|
|----:|---|---|---|
|0|~~0~~ 34|2|16|
|1|2|||
|2|0|||
|3|0|48||
|4|2|||
|5|3|||
|6|2|||
|7||||

blok: 4B -> offset 2 bity
8 bloków, 1 zbiór
0 bitów na index

|Odwołanie | tag | index | offset |hit/miss|
|---------:|-----|-------|--------|--------|
|0|0|0|0|MISS compulsory|
|4|1|0|0|MISS compulsory|
|16|4|0|0|MISS compulsory|
|132|33|0|0|MISS compulsory|
|232|59|0|0|MISS compulsory|
|160|40|0|0|MISS compulsory|
|1024|256|0|0|MISS compulsory|
|28|7|0|0|MISS compulsory|
|140|35|0|0|MISS conflict|
|3100|775|0|0|MISS conflict|
|180|45|0|0|MISS conflict|
|2180|545|0|0|MISS conflict|

pamięć:
|element|tag|
|----:|---|
|0|~~0~~ 35|
|1|~~1~~ 775|
|2|~~4~~ 45|
|3|~~33~~ 545|
|4|59|
|5|40|
|6|256|
|7|7|

## Zadanie 5
:::success
Autor: Magdalena Jarecka
:::



## Zadanie 6
:::success
Autor: Adam Ciężkowski
:::


* Średni czas dostępu do pamięci:
* Cache L1:
$92\% \cdot 0.66ns + 8\% \cdot 70.66ns = 6.26ns$
* Cache L1 i L2:
$92\% \cdot 0.66ns + 8\% \cdot \left(99.5\% \cdot 6.28ns + 0.5\% \cdot 76.28ns\right) = 1.14ns$
* CPI:
* Cache L1:
$64\% \cdot 1 + 36\% \cdot \left(92\% \cdot 1 + 8\% \cdot \left\lceil \frac{70.66}{0.66}\right\rceil \right) = 4.08$
* Cache L1 i L2:
$64\% \cdot 1 + 36\% \cdot \left(92\% \cdot 1 + 8\% \cdot \left(99.5\% \cdot \left\lceil \frac{6.28}{0.66}\right\rceil + 0.5\% \cdot \left\lceil \frac{76.28}{0.66}\right\rceil\right)\right) = 1.27$

## Zadanie 7
:::success
Autor: Mikołaj Jaszcza
:::

4! to 24, logarytm (jego sufit) to 5. Mamy więc dostępne 5 bitów do reprezentacji kolejności/relacji 4 liczb. Sposób tej reprezentacji może wyglądać w sposób określony następująco - w odpowiedniej kolejności pamiętamy:
1) liczbę 2-bitową reprezentującą najdawniej używaną sekcję - w przypadku potrzeby zwolnienia jednej sekcji w pamięci cache usuniemy właśnie tą sekcję
2) liczbę 2-bitową reprezentującą prawie najdawniej używaną sekcję (druga od końca)

2 bity na reprezentacje obu z tych liczb są wystarczające (użyjemy więc łącznie 4 bity), bo liczby są ze zbioru 0,1,2,3

Wykorzystaliśmy już 4 bity z 5 dostępnych, znamy już dokładną pozycję dwóch liczb. Pozostaje więc nam do dyspozycji 1 bit:

3) wykorzystamy go aby reprezentować, czy "najnowsza" i "prawie najnowsza" (pod względem ostatniego użycia) linie są uporządkowane zgodnie z porządkiem leksykograficznym.

Skoro wiemy już, jak skorzystać z naszej reprezentacji, aby uzyskać najdawniej używaną sekcję - wystarczy że ustalimy w jaki sposób nasza struktura danych powinna być aktualizowana. Oczywiście za pomocą prostych układów kombinacyjnych możemy mieć łatwy dostęp do liczby na dowolnej pozycji - będę używał tej obserwacji w dalszej części rozwiązania.

Aby to zrobić rozpatrzę 4 przypadki (ponieważ potencjalna aktualizacja jest równoważna z użyciem jednej z 4 linii pamięci).

A) jeżeli użyjemy linię która była najbardziej niedawno użyta - nie zmieniamy nic w strukturze, zgodnie z intuicją
B) jeżeli użyjemy linię przedostatnio używaną - wystarczy zmienić wartość "piątego" z opisywanych bitów. Wiemy że zawsze kolejność leksykograficzna dot. dwóch najnowszych linii się zmieni (tj. 0 -> 1, 1-> 0), więc wystarczy zxor'ować piąty bit z wartością "1"
C) jeżeli użyliśmy linię prawie najdawniej używaną


Wystarczy więc odczytać 3 wartości, wartość prawie najnowszego przypisujemy do prawie najstarszego (łatwe - zapisujemy wprost 2 bity), odczytujemy pozostałe 2 wartości ( w tym przypadku 0 i 2) - zapisujemy informację o ich relacji leksykograficznej

D) jeżeli używamy linii najdawniej używanej
Wystarczy zamienić kolejność najdawniej i prawie najdawniej używanej linii, a następnie powtórzenie operacji opisanych w podpunkcie "C)"

## Zadanie 8
:::success
Autor: Adam Górkiewicz
:::

## Zadanie 9
:::success
Autor: Jan Dalecki
:::


Struktura piksela w pamięci:


Obliczamy adres początku piksela w pamięci:

Base addres = $(i\cdot640 + j)\cdot 4$

Wartości rgba po kolei:

{r, g, b, a} = Base addres + {0, 1, 2, 3}

index = ({r, g, b, a} >> 3)&4095

Tag = {r, g, b, a} >> 15

Offset = {r, g, b, a} % 8

W jednej lini (8 bajtów) możemy zapisać 2 piksele:


Zauważmy, że para pikseli buffer[i][j], buffer[i][j+1], gdzie j jest parzyste, ma dokładnie ten sam index oraz tag

Pętla wewnętrzna przechodzi przez zapisaną w pamięci tablicę wykonując skoki o dokładnie $4\cdot 640$ bajtów.


Kolejna iteracja pętli zewnętrznej przesuwa nas o 1 piksel zapisany w pamięci w lewo.


W jednej pętli zewnętrznej odwołamy się do tego samego indeksu kilka razy.

Stąd będziemy mieli 1 miss oraz 3 razy hit na jeden piksel. Zatem hitrate = $\frac{3}{4} \rightarrow75\%$.