---
# System prepended metadata

title: 'Ćwiczenia 9, grupa śr. 17-19, 11. maja 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ć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
![](https://i.imgur.com/I2yAppM.png)

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

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

Pamieć podręczna z mapowaniem bezpośrednim adresowana bajtowo - w każdym zbiorze jest zapamiętany tylko jeden wiersz
![](https://i.imgur.com/1fJTTsq.png)

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

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

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

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
:::
![](https://i.imgur.com/VYaAz7W.png)

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

![](https://i.imgur.com/3PIrZY7.png)
![](https://i.imgur.com/nUx9Hfe.png)

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

![](https://i.imgur.com/jpINaTU.png)
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
:::

![](https://i.imgur.com/sGXuxxE.jpg)
![](https://i.imgur.com/zb3gaCc.png)


![](https://i.imgur.com/floIBXL.jpg)



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

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


* Ś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ą 

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


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)"
![](https://i.imgur.com/L1PC8ym.png)


## Zadanie 8
:::success
Autor: Adam Górkiewicz
:::
![](https://i.imgur.com/myZOINS.png)
![](https://i.imgur.com/ckL1kFd.png)
![](https://i.imgur.com/3HYAsGc.png)


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


![](https://i.imgur.com/NX6HZPS.png)
![](https://i.imgur.com/04Y7goN.png)

Struktura piksela w pamięci:

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


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:

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

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.

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

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

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

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\%$.