# Ćwiczenia 9, grupa cz. 12-14, 5. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | x | x | ==x== | x | x | | x | | |
Adam Ciężkowski | | | | | | | | | |
Jacek Długopolski | x | x | x | x | x | | | | |
Jakub Fila | ==x== | x | x | x | | | x | x | |
Krzysztof Grynkiewicz | | | | | | | | | |
Michał Hetnar | x | x | x | x | x | x | x | x | x |
Hubert Jabłoński | x | x | x | x | x | x | | | |
Antoni Kamiński | | | | | | | | | |
Paweł Karaś | X | X | X | X | X | X | | | |
Emil Kisielewicz | x | x | x | x | x | | | | |
Kacper Komenda | x | x | x | | x | x | | | |
Filip Komorowski | x | x | x | x | x | x | x | | |
Piotr Piesiak | x | x | x | x | x | ==x== | x | | |
Artur Krzyżyński | x | x | x | x | x | x | x | x | x |
Patryk Mazur | ==X== | X | X | X | | X | X | | |
Szymon Mleczko | X | X | X | | X | X | | | |
Michał Mróz | X | X | X | X | | X | | X | |
Dominik Olejarz | | | | | | | | | |
Magdalena Słonińska | X | X |==X==| X | X | X | | | |
Oleś Kulczewicz | X | X | X | | X | X | | | |
Adam Szeruda | X | X | X | X | X | X | X | X | X |
Kamil Tasarz | X | X | X | | X | X | | | |
Michał Zieliński | 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: Jakub Fila

:::

## Zadanie 2
:::success
Autor: Michał Zieliński
:::

### Treść
Rozważmy pamięć podręczną z mapowaniem bezpośrednim adresowaną bajtowo. Używamy adresów 32-bitowych o następującym formacie: $(tag, index, offset) = (addr_{31...10}, addr_{9...5}, addr_{4...0})$.
• Jaki jest rozmiar bloku w 32-bitowych słowach?
• Ile wierszy ma nasza pamięć podręczna?
• Jaki jest stosunek liczby bitów składujących dane do liczby bitów składujących metadane?
### Rozwiązanie
#### a)
Z treści wynika, że offset ma 5 bitów, więc blok ma 32 bajty, czyli $32 \cdot 8$ bitów, to jest rozmiar bloku wynosi 8 w 32-bitowych słowach.
#### b)
Mamy tyle samo wierszy, co zbiorów, którym odpowiadają konkretne wartości indexu. Wierszy jest zatem 32.
#### c)
Dane przechowywane są na $32*8$ bitach, metadane zapisane są na bitach tagu i validbit. Zatem stosunek to $\frac {32 \cdot 8}{22+1}=\frac {256}{23} \approx 11.13$

## Zadanie 3
:::success
Autor: Daniel Boguszewski
:::

Konwersja systemu dziesiętnego na dwójkowy (bład w nazwach kolumn):

Rozdzielenie tagu, indesku oraz offsetu:

Próba odczytu z pamięci konkretnych słów.

Nastąpiły 8 zastąpienia, z czego 4 były przymusowe (zimne trafienie, tutaj *mróz*, krotka pamięci oznaczona jako nieprawidłowa, pusta krotka) oraz 4 w wyniku kolizji (tutaj *konflikt*, po próbie odniesienia się do słowa, którego miejsce w pamieci podręcznej jest już zajęte).

Efektywność pamięci wynosi $4/12$, czyli około 33%.

Zawartość pamięci (TAG, ID, wartości dla zakresu OFFSET):
(0; 0; [0] [0-11111]),
(10; 100; [0]10 00100 [0-11111]),
(0; 111; [0]111 [0-11111]),
(0; 101; [0]101 [0-11111]).

[0] oznacza wypełnienie zerami.
[0-11111] oznacza zakres.

Dziesiętnie:
(0, 0, M[0-31]),
(2, 4, M[2176-2207]),
(0, 7, M[224-255]),
(0, 5, M[160-191]).

## Zadanie 4
:::success
Autor: Hubert Jabłoński
:::


Polityka wymiany LRU - Usuwamy z cache'u Least Recently Used value.

Słowo - 32b = 4B
Bloki - 2*4B = 8B = $2^3B$
Offset: 3bity
24 bloki i 3 bloki na zbiór, czyli 8 zbiorów
Index: 3b
Tag: 32-3-3=26b

| |adres |(tag, index, offset)| hit/miss |
|--|--------------|--------------------|----------------|
|1 |000 |(0, 0, 0) | compulsory miss|
|2 |100 |(0, 0, 4) | hit |
|3 |10 000 |(0, 2, 0) | compulsory miss|
|4 |10 000 100 |(2, 0, 4) | compulsory miss|
|5 |11 101 000 |(3, 5, 0) | compulsory miss|
|6 |10 100 000 |(2, 4, 0) | compulsory miss|
|7 |10000 000 000 |(16, 0, 0) | compulsory miss|
|8 |11 100 |(0, 3, 4) | compulsory miss|
|9 |10 001 100 |(2, 1, 4) | compulsory miss|
|10|110000 011 100|(48, 3, 4) | compulsory miss|
|11|10 110 100 |(2, 6, 4) | compulsory miss|
|12|100010 000 100|(34, 0, 4) | conflict miss |

|indeks|tag |
|------|-----|
|0 |34 |
| |2 |
| |16 |
|1 |2 |
| |- |
| |- |
|2 |0 |
| |- |
| |- |
|3 |0 |
| |48 |
| |- |
|4 |2 |
| |- |
| |- |
|5 |3 |
| |- |
| |- |
|6 |2 |
| |- |
| |- |
|7 |- |
| |- |
| |- |

Słowo - 32b = 4B
Bloki - 4B = $2^2B$
Offset: 2bity
Index: 0b
Tag: 32-2-0=30b

| |adres |(tag, index, offset)| hit/miss |
|---|--------------|--------------------|----------------|
|1 |00 |(0, 0, 0) | compulsory miss|
|2 |1 00 |(1, 0, 0) | compulsory miss|
|3 |100 00 |(4, 0, 0) | compulsory miss|
|4 |100001 00 |(33, 0, 0) | compulsory miss|
|5 |111010 00 |(59, 0, 0) | compulsory miss|
|6 |101000 00 |(40, 0, 0) | compulsory miss|
|7 |100000000 00 |(256, 0, 0) | compulsory miss|
|8 |111 00 |(7, 0, 0) | compulsory miss|
|9 |100011 00 |(35, 0, 0) | conflict miss |
|10 |1100000111 00 |(775, 0, 0) | conflict miss |
|11 |101101 00 |(45, 0, 0) | conflict miss |
|12 |1000100001 00 |(545, 0, 0) | conflict miss |

|indeks|tag |
|------|-----|
|0 |35 |
| |775 |
| |45 |
| |545 |
| |59 |
| |40 |
| |256 |
| |7 |

## Zadanie 5
:::success
Autor: Kamil Tasarz
:::

Przykład:

Bloki mają po 4 bajty. Blok [00 FA FF FC] jest w pamięci głównej, nie jest ani w L1 ani w L2.
Procesor zapisuje wartość 07 do zerowego bajtu tego bloku. Następuje chybienie w L1 przy zapisie. W L1 należy zapisać bok [07 FA FF FC]. Jak to zrobić?

[07 ? ? ?]


## Zadanie 6
:::success
Autor: Piotr Piesiak
:::
dostęp do pamięci głównej - $t_{op} = 70ns$
dostęp do pamięci L1 - $t_{L_1} = 0.66ns$
dostęp do pamięci L2 - $t_{L_2} = 5.62ns$

Współczynnik chybień L1 - $c_{L_1} = 8\%$
Współczynnik chybień L2 - $c_{L_1} = 0.5\%$

Dostępy do pamięci - 36% instrukcji
Długość cyklu - 0.66ns
Średni czas dostępu do pamięci dla procesora z L1:
$(1 - c_{L_1}) \cdot t_{L_1} + c_{L_1} \cdot (t_{L_1} + t_{op}) = 0.92 \cdot 0.66ns + 0.08 \cdot 70.66ns = 6.26ns$

Średni czas dostępu do pamięci dla procesora z L1 i L2:
$(1 - c_{L_1}) \cdot t_{L_1} + c_{L_1} \cdot ( (1 - c_{L_2}) \cdot (t_{L_1} + t_{L_2}) + c_{L_2} \cdot (t_{L_1} + t_{L_2} + t_{op}))$
$0.92 \cdot 0.66ns + 0.08 \cdot (0.995 \cdot 6.28 + 0.005 \cdot 76.28ns) = 1.14ns$

zakładamy, że CPI wynosi 1.0 dla instrukcji bez odczytów z pamięci (36% instrukcji to odczyty z pamięci)

$CPI_{L_1} = 0.36 \cdot \frac{6.26}{0.66} + 0.64 * 1 = 4.05$
$CPI_{L_1L_2} = 0.36 \cdot \frac{1.14}{0.66} + 0.64 * 1 = 1.26$

## Zadanie 7
:::success
Autor: Filip Komorowski
:::

### Podejście używane w praktyce
Oznaczmy bloki w zbiorze przez A, B, C, D

Wtedy niech bit B0 odpowiada za parę AB i CD, B1 za pojedyńczy blok A lub B a B2 za pojedyńczy blok C lub D.

Wtedy, gdy korzystamy z bloku ustawiamy odpowiednio bit B0 na 0 jeśli blok z (AB) lub 1 jeśli z (CD). Następnie ustawiamy odpowiedni bit B1 lub B2 na 0 lub 1, żeby określić, który blok z pary był ostatnio używany.

W momencie potrzeby nadpisania bloku wybieramy replacement następująco:
Jeśli B0 == 0 musimy wymienić blok w parze (CD) else (AB)
Jeśli blok jest w AB a B1 == 0 to wymieniamy B else A.
Jeśli blok jest w CD a B2 == 0 to wymieniamy D else C.

Dlaczego nie jest to idealne LRU?

B C D C A A -> wymienimy D, a powinniśmy idealnie B

### Reprezentacja idealna (zakładam, że mogę wykorzystać 5 bitów)

przeznaczamy po 2 bity na najdawniej i prawie najdawniej używaną liczbę i 1 bit mówiący czy pozostałe dwie są ułożone rosnącej kolejności

W ten sposób jesteśmy zawsze jednoznacznie odczytać kolejność wykonywania wszystkich 4 bloków.

Trudniejsze okazuje się aktualizowanie ustawienia przy tej reprezentacji.

Procedura będzie wyglądać różnie w zależności od aktualnie wykonywanego bloku.

* a) najświeższy -> brak zmian

* b) drugi w kolejności -> flip 5ego bitu

Dwa kolejne przypadki są trudniejsze:

* c) prawie najstarszy ->
* Tutaj musimy na miejscu prawie najstarszego zapisać prawie najświeższego. Musimy mieć zatem chwilowo dwa dodatkowe bity, które posłużą nam jako placeholder do pamiętania wartości. Zapisujemy tam prawie najstarszy blok. Wtedy odczytujemy, jaka liczba jest prawie najświeższa nadpisujemy prawie najstarszy. Porównujemy teraz poprzednią najswieższą liczbę z liczbą w placeholderze i odpowiednio ustawiamy bit.

* d) najstarszy ->
* Tutaj również potrzebujemy placeholdera. Podmieniamy najstarszego z prawie najstarszym i powtarzamy punkt c.

  clk
   |
 -| |------------
                |
  clk           or -----|
   |            |       |
   |                    |
 -| |-----------        |
 |                      |
 ------------------------
      
   .
      
   .  

Jeśli mamy 5 rejestrów z liniami wyjściowymi o1,..., o5 i liniami wejściowymi i1,...i5 to chcemy
zaprojektować funkcje logiczne:

* f_i1(o1, o2, o3, o4, o5) -- funkcja logiczna która oblicza wejście pierwszego rejestru (i1) na podstawie bitów o1,..o5
* f_i2(o1,o2,o3,o4,o5) ---
* itd aż do f_i5(...)

Jak zaprojektować f_i1:

## Zadanie 8
:::success
Autor: Michał Hetnar
:::
* 1/4 hybień połowa z tego cold missy
* 1/4 hybień same cold missy
* 1/4 hybień połowa z tego cold missy

## Zadanie 9
:::success
Autor: Artur Krzyżyński
:::

Współczynnik trafień 0.75, jednak jeżeli odwrócimy pętle to mamy 0.875
:::spoiler kod

from collections import defaultdict

MEM = 1 << 15
B = 8
S = MEM // B

cache = defaultdict(lambda: None)
miss = 0
hits = 0

for j in range(639, -1, -1):
	for i in range(479, -1, -1):
		for k in range(4):
			p = ((i * 640) + j) * 4
			s = (p // B) % S
			t = p // B // S

			if cache[s] != t:
				cache[s] = t
				miss += 1
			else:
				hits += 1

:::