# Lista 11 (20 maja 2021)

###### tags: `ask21` `ćwiczenia` `kba`

## 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 |
| --------------------:| ----- | ----- | --- | --- | --- | --- | ----- | ----- |
| Andriy Bernad | X | ==X== | X | X | X | | X | | 6
| Wojciech Bogucki | X | X | X | X | X | | X | | 6
| Michał Doros | X | X | X | X | X | X | ==X== | | 7
| Marko Golovko | | | | | | | | | 0
| Magdalena Jarecka | ==X== | X | X |~~X~~| X | | X | | 5; Z4 wykreślone
| Szymon Jędras | X | X | X | X | X | | | | 5
| Heorhii Karpenko | X | X |==X==| X | X | | | | 5
| Szymon Kosakowski | X | X | X | | X | | X | | 5
| Izabella Kozioł | | | | | | | | | 0
| Franciszek Malinka | X | X | X | X | X | X | X | ==X== | 8
| Filip Pazera | X | X | X | X | | | X | | 5
| Franciszek Pindel | X | X | X | X | X | X | X | | 7
| Kacper Puchalski | X | X | X | | X | | X | | 5
| Kacper Solecki | X | X | X | X | X | X | X | | 7
| Andrzej Tkaczyk | X | X | X | X | X | X | | | 6
| Łukasz Wasilewski | X | X | X | X | X | | X | | 6
| Vladyslav Yablonskyi | X | X | X | X | | | | | 4
| Adam Zyzik | X | X | X | X | X | | X | | 6
:::

## Zadanie 1

:::info
Autor: Władysław Yablonskyi
:::
(tag, index, offset) = (addr31...10, addr9...5, addr4...0)
* $B=2^b=2^5=32$ więc rozmiar bloku 8 slowa 32-bitowych.
* $S=2^s=2^5=32$ wiersza
$E=1$, bo mamy mapowanie bezporednie.
* Metadane = valid + tag = 23 bity
B=32 więc mamy 32 bajty = 256 bity na blok
Więc stosunek liczb bitów matadanych do liczby wszystkich bitów $\frac{23}{279}$

## Zadanie 2

:::success
Autor: Andrzej Bernad
:::

:::info
Mamy system z pamięcią operacyjną adresowaną bajtowo. Szerokość szyny adresowej wynosi 12. Pamięć podręczna ma organizację sekcyjno-skojarzeniową o dwuelementowych zbiorach, a blok ma 4 bajty. Dla podanego niżej stanu pamięci podręcznej wyznacz, które bity adresu wyznaczają: offset, indeks, znacznik. Wszystkie wartości numeryczne podano w systemie szesnastkowym.

Określ, które z poniższych operacji odczytu wygenerują trafienie albo chybienie i ew. jakie wartości wczytają:
:::

Skoro blok zajmuje 4 bajty, to $B = 4 = 2^b \Rightarrow b = 2$, to offset będzie na bitach $a_1, a_0$. Indeksy w naszej pamięci są z zakresu od 0 do 3, a więc można je przedstawić na dwóch bitach, stąd będą to bity $a_3, a_2$. Pozostałe bity będą zarezerwowane na tag.
Przedstawia to tabelka poniżej:

| $a_{11}$ | $a_{10}$ | $a_9$ | $a_8$ | $a_7$ | $a_6$ | $a_5$ | $a_4$ | $a_3$ | $a_2$ | $a_1$ | $a_0$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| t | t | t | t | t | t | t | t | i | i | o | o |

Tabelka operacji odczytu:

| Adres HEX | Adres BIN | Trafienie? | Wartość |
|:---------:|:----------------:|:----------:|:-------:|
| `0x832` | `1000 0011 0010` | Tak | `0xCC` |
| `0x835` | `1000 0011 0101` | Nie | $-$ |
| `0xFFD` | `1111 1111 1101` | Tak | `0xC0` |

## Zadanie 3

:::danger
Autor: Grzegorz Karpenko
:::

**Compulsory miss** - zachodzi, gdy pytamy o blok po raz pierwszy (pierwszy raz go ściągamy z pamięci).
**Conflict miss** - zachodzi wtedy, gdy bloki danych należą do tego samego seta i się nadpisują nawzajem ze względu na zbyt małą pojemność setu.

Blok zostaje zastąpiony gdy dochodzi do chybienia, wtedy kontroler pamięci podręcznej musi wybrać blok, który zostanie zastąpiony nowymi danymi.

| # | Adres | Tag | Set | Offset | Krotki | Trafienie? | Zastąpiony? |
|:---:|:-------:|:----:|:---:|:------:|:------------:|:---------------:|:-----------:|
| 1 | `0x000` | `00` | `0` | `0` | `(00, 0, 0)` |compulsory miss | tak |
| 2 | `0x004` | `00` | `1` | `0` | `(00, 1, 0)` | compulsory miss | tak |
| 3 | `0x010` | `01` | `0` | `0` | `(01, 0, 0)` | compulsory miss | tak |
| 4 | `0x084` | `08` | `1` | `0` | `(08, 1, 0)` | compulsory miss | tak |
| 5 | `0x03C` | `03` | `3` | `0` | `(03, 3, 0)` | compulsory miss | tak |
| 6 | `0x0E8` | `0E` | `2` | `0` | `(0E, 1, 0)` | compulsory miss | tak |
| 7 | `0xC8C` | `C8` | `3` | `0` | `(C8, 3, 0)` | compulsory miss | tak |
| 8 | `0x0A0` | `0A` | `0` | `0` | `(0A, 0, 0)` | compulsory miss | tak |
| 9 | `0x004` | `00` | `1` | `0` | `(00, 1, 0)` | hit | nie |
| 10 | `0x400` | `40` | `0` | `0` | `(40, 0, 0)` | compulsory miss | tak |
| 11 | `0x084` | `08` | `1` | `0` | `(08, 1, 0)` | hit | nie |
| 12 | `0x010` | `01` | `0` | `0` | `(01, 0, 0)` | conflict miss | tak |
| 13 | `0x0E8` | `0E` | `2` | `0` | `(0E, 2, 0)` | hit | nie |
| 14 | `0x884` | `88` | `1` | `0` | `(88, 1, 0)` | compulsory miss | tak |
| 15 | `0xC8C` | `C8` | `3` | `0` | `(C8, 3, 0)` | hit | nie |
| 16 | `0x000` | `00` | `0` | `0` | `(00, 0, 0)` | conflict miss | tak |

| Index | tag | valid | victim |
| -------- | -------- | -------- |------- |
| 0 | 01 | 1 |0 |
| 0 | 00 | 1 |<- |
| 1 | 08 | 1 |<- |
| 1 | 88 | 1 |0 |
| 2 | 0E | 1 |0 |
| 2 | 00 | 0 |<- |
| 3 | C8 | 1 |0 |
| 3 | 03 | 1 |<- |

Ile było chybień przymusowych? odp: $12$
Hit ratio: $25%$

Na wyznaczenie potencjalnej ofiary potrzebujemy 1 bitu na zbiór, ponieważ musimy pamiętać tylko która była ostatnio użyta, a zbiór ma 2 linie. Czyli kiedy wrzucamy do zbioru blok do linii 0, ten bit ustawiamy na 1, a kiedy do pierwszej to na 0.

## Zadanie 4

:::danger
Autor: ~~Magdalena Jarecka~~
Autor: Grzegorz Karpenko
:::

:::info
Powtórz polecenia z poprzedniego zadania dla w pełni asocjacyjnej (ang. fully associative)
pamięci podręcznej posiadającej 8 bloków. Polityka wymiany to LRU (ang. Least Recently Used). Reszta
danych nie ulega zmianie.
:::


W pełni asocjacyjna pamięć podręczna jest zorganizowana w pojedynczy zestaw pamięci podręcznej z wieloma wierszami. Blok pamięci może zajmować dowolną wiersz pamięci podręcznej. Organizacja pamięci podręcznej może być ujęta w ramkę jako macierz wierszy (1 * m).

| # | Adres | Tag | Offset | Trafienie? | Zastąpiony? |
|:---:|:-------:|:--------------:|:------:|:---------------:|:-----------:|
| 1 | `0x000` | `0000 0000 00` | `0` | compulsary miss | tak |
| 2 | `0x004` | `0000 0000 01` | `0` | compulsary miss | tak |
| 3 | `0x010` | `0000 0001 00` | `0` | compulsory miss | tak |
| 4 | `0x084` | `0000 1000 01` | `0` | compulsory miss | tak |
| 5 | `0x03C` | `0000 0011 11` | `0` | compulsory miss | tak |
| 6 | `0x0E8` | `0000 1110 10` | `0` | compulsory miss | tak |
| 7 | `0xC8C` | `1100 1000 11` | `0` | compulsory miss | tak |
| 8 | `0x0A0` | `0000 1010 00` | `0` | compulsory miss | tak |
| 9 | `0x004` | `0000 0000 01` | `0` | hit | nie |
| 10 | `0x400` | `0100 0000 00` | `0` | compulsory miss | tak |
| 11 | `0x084` | `0000 0100 01` | `0` | hit | nie |
| 12 | `0x010` | `0000 0001 00` | `0` | hit | nie |
| 13 | `0x0E8` | `0000 1110 10` | `0` | hit | nie |
| 14 | `0x884` | `1000 1000 01` | `0` | compulsory miss | tak |
| 15 | `0xC8C` | `1100 1000 11` | `0` | hit | nie |
| 16 | `0x000` | `0000 0000 00` | `0` | conflict miss | tak |

|Age bits| Adres | valid |
|-| --------- | -------- |
|7| 0x000 | 1 |
|6| 0xC8C | 1 |
|5| 0x884 | 1 |
|4| 0x0E8 | 1 |
|3| 0x010 | 1 |
|2| 0x084 | 1 |
|1| 0x400 | 1 |
|0| 0x004 | 1 |

Ile było chybień przymusowych? odp: 10
Hit ratio: 31,25%

Dla każdej linii musimy pamiętać "age bits" log(liczba linii).
3*8 = 24

## Zadanie 5

:::danger
Autor: Kacper Puchalski
:::

#### Pytanie 1

W przypadku używania najbardziej znaczących bitów na indeks odwołująć się do kolejnych adresów będziemy dużo pudłować. Kolejne odwołania do pamięci będa mieć ten sam indeks, a różne tagi. W związku z tym będzie trzeba wymieniać bloki/linie w pamięci. Efektywna pamięć przy tym podejściu będzie rozmiaru jednego bloku. Jeżeli użyjemy indeksu w środku adresu, będziemy na zmianę odwoływać się do kolejnych setów (obrazek). Wtedy będziemy w stanie efektywnie przetrzymywać (liczbę setów * rozmiar bloku) pamięci.

strona 606 Computer Systems A Programmer’s Perspective

#### Pytanie 2

Przy używaniu osobnych cachów dla instrukcji i danych możemy używać i-cacha jako read only. Raczej nie chcemy modyfikować czy nadpisywać instrukcji. I-cache może być więc prostszy. W czasie jednego cyklu procesor może jednocześnie odczytywać instrukcję i dane do niej. Ograniczy to też możliwość conflict missa przy odczytywaniu danych z setów dla instrukcji i na odwrót.

6.4.6, strona 613
> Processors include separate i-caches and d-caches. There are a number of reasons for this.
With two separate caches, the processor can read an instruction word and a data
word at the same time. I-caches are typically read-only, and thus simpler. The
two caches are often optimized to different access patterns and can have different
block sizes, associativities, and capacities. Also, having separate caches ensures
that data accesses do not create conflict misses with instruction accesses, and vice
versa, at the cost of a potential increase in capacity misses.

## Zadanie 6

:::success
Autor: Franciszek Pindel
:::

> Rozważamy system z dwupoziomową pamięcią podręczną z **polityką zapisu**: **write-back** i **write-allocate**. Jeśli blok o określonym adresie znajduje się na poziomie $L_i$ to znajduje się również na wszystkich poziomach j > i (ang. inclusive caches). Przy pomocy schematu blokowego przedstaw algorytm obsługi zapisu słowa maszynowego do pamięci. Pierwszym elementem diagramu ma być predykat „Czy słowo jest w L1?”. Pamiętaj o bicie **dirty** i o tym, że pamięć podręczna może być całkowicie wypełniona! Zakładamy, że pamięć podręczna pierwszego poziomu nie może komunikować się bezpośrednio z pamięcią operacyjną. Wiemy też, że pamięć L2 jest dużo większa niż L1.

* **polityka zapisu** - sposób postępowania w trakcie zapisu danych do pamięci podręcznej zarówno w sytuacji trafienia jak i chybienia
* **wrtie back** - jeżeli dana wartość została odnaleziona w pamięci podręcznej, to zostaje ona zmodyfikowana, ale wszystkie jej wystąpienia na niższych poziomach pozostają niezmodyfikowane. Dopero w momencie zastępiania danego bloku jego nadpisana wartość zostaje zmieniona na niższym poziomie
* **write allocate** - wartość zostaje odnaleziona i umieszczona w pamięci podręcznej

digraph {
    start [label="START"]
    end   [label="END"]
    isinL1 [label="Czy słowo jest w L1?" shape=diamond]
    isblockfree [label="Czy jest wolny blok do wczytania?" shape=diamond]
    chosevictim [label="Wybierz ofiarę" shape=box]
    isdirty [label="Czy ofiara ma zapalony bit dirty?" shape=diamond]
    loadfromL2 [label="wczytaj blok z szukanym słowem z L2 do L1" shape=box]
    savevictim [label="zapisz ofiarę do L2" shape=box]
    modify [label="zmodyfikuj wartość słowa" shape=box]
    dirty [label="zapal bit dirty" shape=box]
    
    start->isinL1
    isinL1->modify [label="tak"]
    isinL1->isblockfree [label="nie"]
    isblockfree->chosevictim [label="nie"]
    isblockfree->loadfromL2 [label="tak"]
    chosevictim->isdirty
    isdirty->savevictim [label="tak"]
    isdirty->loadfromL2 [label="nie"]
    savevictim->loadfromL2
    loadfromL2->modify
    modify->dirty
    dirty->end
}

W przypadku gdby L2 nie zawiera szukanego słowa, cały algorytm wykounuje się analogicznie pomiędzy L2 i DRAM

> Zastanów się: Jakie problemy sprawiło by założenie, że pamięć podręczna przechowuje blok o określonym adresie dokładnie na co najwyżej jednym poziomie Li (ang.exclusive caches)?

W sytuacji gdy słowo z poziomu L1 musiałoby zostać zapisane do poziomu L2, w L2 mogłoby go tam nie być ani nie być dla niego miejsca co oznaczałoby szukanie ofiary na poziomie L2, która musiałaby zostać zapisana na poziomie L3 itd, czyli mogłoby to zmniejszyć wydajność operacji odczytu

## Zadanie 7

:::success
Autor: Michał Doros
:::

**CPI** - średnia liczba cykli potrzebna na wykonanie 1 instrukcji

CPI (poza dotępami do pamięci) = 1.0
Dostępy do pamięci stanowią 36% wszystkich instrukcji.

| Pamięć | Czas dostępu [ns] | wsp. chybień |
| ------ | ----------------- | ------------ |
| L1 | 0.66 | 8% |
| L2 | 5.62 | 0.5% |
| MAIN | 70 | 0% |

- Jaki jest średni czas dostepu do pamięci dla procesora tylko z pamięcią podręczną L1?

$0.66ns + 0.08 \cdot 70ns = 6.26ns$

- Jaki jest średni czas dostepu do pamięci dla procesora z L1 i L2?

$0.66ns + 0.08(5.62ns + 0.005 \cdot 70ns) = 1.1376ns$

- Procesor wykonuje wszystkie instrukcje, łącznie z dostępami do pamięci danych. Oblicz jego CPI kiedy posiada tylko pamięć podręczną L1.

$CPI = (0.64 \cdot 0.66ns + 0.36 \cdot 6.26ns)\frac{1cykl}{0.66ns} = 4.05 cykli$

- Procesor wykonuje wszystkie instrukcje, łącznie z dostępami do pamięci danych. Oblicz jego CPI z L1 i L2.

$CPI = (0.64 \cdot 0.66ns + 0.36 \cdot 1.137ns)\frac{1cykl}{0.66ns} = 1.26 cyklu$

## Zadanie 8

:::success
Autor: Franciszek Malinka
:::

Stan jest 8-bitową liczbą, którą dzielimy na cztery 2-bitowe segmenty. Każdy segment odpowiada za "wiek" innego wiersza. Ja przyjąłem, że dwa najstarsze bity odpowiadają za wiek 3 wiersza, a dwa najmłodsze za wiek "zerowego". Wiek to liczba od 0 do 3, 3 oznacza "most recently used", 0 oznacza "least recently used". Zatem stan koduje permutację liczb od 0 do 3.

/* victim(s) powinien zwrócić nr wiersza, którego wiek jest równy 0.
 * Rozmazujemy bity tych wierszy, których wiek jest niezerowy,
 * wtedy ~s będzie miał 11 tylko na pozycji wiersza, ktory jest LRU.
 */
uint8_t victim(uint8_t s) {
  s |= ((s & 0x55) << 1) | (s & 0xaa >> 1);
  s = ~s;
  return ((s >> 0) & 0) | ((s >> 2) & 1) | ((s >> 4) & 2) | ((s >> 6) & 3);
}

uint8_t update(uint8_t s, uint8_t v) {
  /* możnaby robić victim po prostu, dla czytelności używam jako funkcji */
  int8_t p0 = victim(s);
  int8_t p1 = victim(s ^ 0b01010101);
  int8_t p2 = victim(s ^ 0b10101010);
  int8_t p3 = victim(s ^ 0b11111111);
  /* 
   * p0 do p3 to pozycje w s wierszy z wiekiem kolejno 0, 1, 2, 3. 
   */

  /* age to wiek tego wiersza który chcemy teraz zupdatować */
  uint8_t age = (3 << (v << 1)) & s;

  /* Zmieni się wiek wszystkich wierszy, które były młodsze od wieku wiersza
   * który w tym momencie 'dotykamy', tj. jeśli chcemy zupdatować wiersz o wieku 1,
   * to powinniśmy ustawić jego wiek na 3, a wiek wierszy które wcześniej miały wiek 2 oraz 3
   * zmniejszyć o 1 
   */

  /* jesli age < X, to chcemy od pozycji wiersza ktory ma wiek X odjac 1.
   * sprawdzenie czy age < X to po prostu sprawdzenie czy ostatni bit w age-X jest zapalony i rozmazanie go
   * jesli (age-X < 0), to (age-X) >> 7 zapali wszystkie bity i zrobimy odpowiedniego xora na pozycji 
   * wiersza, ktory ma wiek X */
  s ^= ((char)(age - 1) >> 7) & (1 << (p1 << 1));     /* 1 ^ 1 = 0 */
  s ^= ((char)(age - 2) >> 7) & (3 << (p2 << 1));     /* 2 ^ 3 = 1 */
  s ^= ((char)(age - 3) >> 7) & (1 << (p3 << 1));     /* 3 ^ 1 = 2 */
  
  /* Aktualizujemy wiek wiersza aktualnego wiersza */
  s |= (3 << (v << 1));
  return s;
}