# Ćwiczenia 11, grupa śr. 14-16, 15 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!**

**UWAGA: Zgodnie z zapowiedzią, dzisiaj deklarujecie zadania 1 -- 5**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Krzysztof Chorzempa | X | | X | | | | | | |
Maciej Ciepiela | X | X | X | | | | | | |
Szymon Fica | X | X | X | | | | | | |
Agnieszka Grala | X | X | X | | | | | | |
Karolina Jędraszek | X | X | X | | | | | | |
Katarzyna Jodłowska | X | X | X | | | | | | |
Dominik Kiełbowicz | X | X | X | X | X | | | | |
Michał Kolasa | X | X | X | ==X== | X | | | | |
Rafał Krysa | X | X | X | X | X | | | | |
Miłosz Krzysiek | X | X | X | X | | | | | |
Łukasz Kulczycki | | | | | | | | | |
Leon Lepkowski | X | X | X | X | | | | | |
Hanna Makowska | ==X== | X | X | X | | | | | |
Jan Marek | X | X | ==X== | | X | | | | |
Cezary Miłek | X | X | X | | | | | | |
Anna Pierzchała | X | X | | | | | | | |
Alan Pietrasz | X | X | X | | | | | | |
Kacper Ponikowski | X | X | X | X | | | | | |
Dominik Walecko | X | X | | | | | | | |
Michał Włodarczak | X | ==X== | X | X | | | | | |
:::

Poniżej można zadeklarować zadania **8** i **9** z **listy 10** oraz zadanie **5** z listy **9**:

:::danger
| | 10.8 | 10.9 | 9.5 |
| ----------------------:| -----| -----| -----|
Krzysztof Chorzempa | X | | |
Maciej Ciepiela | | | |
Szymon Fica | | | |
Agnieszka Grala | | | |
Karolina Jędraszek | | | |
Katarzyna Jodłowska | | | |
Dominik Kiełbowicz | X | X | |
Michał Kolasa | X | X | |
Rafał Krysa | | | X |
Miłosz Krzysiek | | | |
Łukasz Kulczycki | | | |
Leon Lepkowski | | | |
Hanna Makowska | | | |
Jan Marek | | | |
Cezary Miłek | | | |
Anna Pierzchała | | | |
Alan Pietrasz | | | |
Kacper Ponikowski | | | |
Dominik Walecko | | | |
Michał Włodarczak | | | |
:::

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

## Zadanie 1
:::success
Autor: Dominik Walecko ​​
:::

Iterując się po tablicy, nastarsze bity zmieniają się rzadziej niż bity środkowe. Co za tym idzie, przy alternatywnym sposobie dane częściej będą trafiać do tych samych zbiorów niż przy sposobie bazowym.

Przeszkadza nam to pod tym względem, że przez to właśnie częściej będziemy musieli nadpisywać dane, które dopiero co zapisaliśmy, a więc takie, które chcielibyśmy mieć jeszcze w cache.

## Zadanie 2
:::success
Autor:​Kacper Ponikowski ​
:::
Zakładam 6 bitowe adresy
* Mapowanie bezpośrednie

| TT | SS | BB | Hit?|
| -- | -- | -- | --- |
| 00 | 00 | 00 | comp-miss|
| 00 | 10 | 00 | comp-miss|
| 01 | 10 | 00 | conflict |
| 00 | 00 | 00 | HIT |

* Dwudrożna

| TTT | S | BB | Hit? |
| --- | - | -- | ---- |
| 000 | 0 | 00 | comp-miss |
| 001 | 0 | 00 | comp-miss |
| 011 | 0 | 00 | conflict |
| 000 | 0 | 00 | conflict |

## Zadanie 3
:::success
Autor:​​Michał Włodarczak
:::

## Zadanie 4
:::success
Autor:​​Leon Lepkowski
:::

Adres = $4669 = 0001 001000111101_2$
Tag = 1
Błąd strony
| Valid? | Tag | LRU | PPN|
|--------|-----|-----|----|
| 1 | 1 | 3 | 13 |
| 1 | 7 | 0 | 4 |
| 1 | 3 | 1 | 6 |
| 0 | 4 | 2 | 9 |

Uznaję że im niższe LRU tym starsze.

Adres = $2227 = 0000 100010110011$
Tag = 0
Trafienie w tablicę stron
| Valid? | Tag | LRU | PPN|
|--------|-----|-----|----|
| 1 | 1 | 2 | 13 |
| 1 | 0 | 3 | 5 |
| 1 | 3 | 0 | 6 |
| 0 | 4 | 1 | 9 |

Adres = $13916 = 0011 011001011100$
Tag = 3
Trafienie w TLB
| Valid? | Tag | LRU | PPN|
|--------|-----|-----|----|
| 1 | 1 | 2 | 13 |
| 1 | 0 | 3 | 5 |
| 1 | 3 | 0 | 6 |
| 0 | 4 | 1 | 9 |

Adres = $34587 = 1000 011100011011$
Tag = 8
Błąd strony
| Valid? | Tag | LRU | PPN|
|--------|-----|-----|----|
| 1 | 1 | 1 | 13 |
| 1 | 0 | 2 | 5 |
| 1 | 8 | 3 | 14 |
| 0 | 4 | 0 | 9 |

Adres = $48870 = 1011 111011100110$
Tag = 11
Trafienie w tablicę stron
| Valid? | Tag | LRU | PPN|
|--------|-----|-----|----|
| 1 | 1 | 0 | 13 |
| 1 | 0 | 1 | 5 |
| 1 | 8 | 2 | 14 |
| 1 | 11 | 3 | 12 |

Adres = $12608 = 0011 000101000000$
Tag = 3
Trafienie w tablicę stron
| Valid? | Tag | LRU | PPN|
|--------|-----|-----|----|
| 1 | 3 | 3 | 6 |
| 1 | 0 | 0 | 5 |
| 1 | 8 | 1 | 14 |
| 1 | 11 | 2 | 12 |

Adres = $49225 = 1100 000001001001$
Tag = 12
Błąd strony

## Zadanie 5
:::success
Autor:​​Jan Marek
:::


a) Tablica stron jednopoziomowa

32-bitowe adresy wirtualne, czyli 2^32 adresów wirtualnych
Rozmiar strony: 4 KiB = 2^12 B
Rozmiar wpisu tablicy stron: 4 B

Ilość stron = liczba możliwych adresów wirt. / rozmiar strony:

2^32 B / 2^12 B = 2^20 <- ilość stron

Wynik mnożymy razy rozmiar wpisu w tablicy stron:

2^20 * 2^2 B = 2^22 B = 4 MiB <- rozmiar tablicy stron

b) Tablica stron dwupoziomowa, gdzie katalog tablicy stron ma 1024 wpisy


1 GiB = 2^30 B

Rozmiar tablicy stron pierwszego poziomu = 2^10 * 2^2 B = 2^12 B

Będziemy potrzebować 2^30 B / 2^12 B = 2^18 stron

A więc musimy mieć 2^18 wpisów w tablicy drugiego poziomu.

Każdy wpis zajmuje 2^2 B.

Więc minimalny rozmiar tablicy drugiego poziomu wynosi 2^18 * 2^2 B = 2^20 B

---

Minimalny rozmiar tablicy dwupoziomowej jest równy:
rozmiar tablicy pierwszego poziomu + rozmiar tablicy drugiego poziomu = 2^12 B + 2^20 B = ok. 1MiB

Maksymalny rozmair zostanie osiągnięty w przypadku wykorzystania całej przestrzeni adresowej 2^32

Mamy wtedy 2^32 / 2^12 = 2^20 stron czyli tyle też będzie łącznie wpisów w tablicach drugiego poziomu.

Maksymalny rozmiar tablicy dwupoziomowej jest równy:
rozmiar tablicy pierwszego poziomu + rozmiary tablic drugiego poziomu = 2^12 B + 2^20 B * 2^2 B = ok. 4MiB

## Zadanie 6
:::success
Autor:​​Rafał Krysa
:::

Wariant pesymistyczny:
Wszystkie strony mają taki sam TLBI. Dla pięciu i więcej stron mają miejsce ciągłe conflict missy.
Maksymalny rozmiar: 4 strony, 16 KiB.
Wariant optymistyczny:
TLB całkowicie się zapełni zanim natrafimy na piątą stronę w tym samym zbiorze.
64 strony, 64\*4Kib = 256 KiB
Huge pages:
Wariant pesymistyczny:
Wszystkie strony mają taki sam TLBI
4 strony, 4\*4MiB = 16 MiB
Wariant optymistyczny:
64 strony, 64\*4MiB = 256 MiB

## Zadanie 7
:::success
Autor: Dominik Walecko ​​
:::


Zaletą jest oszczędność pamięciowa.

## Zadanie 8
:::success
Autor:​​ Dominik Kiełbowicz
:::


indeksowana fizycznie - używamy indeksu z adresu fizycznego (PA)
znakowana fizycznie - używamy tagu z adresu fizycznego

indeksowana wirtualnie - używamy indeksu z adresu wirtualnego

Gdy w architekturze rozmiar VPO równy jest rozmiarowi PPO, możemy wykorzystać tę informację do równoległego wykonania następujących 2 czynności:

obliczenia CI oraz CO i pobraniania odpowiegniego setu z cache
przetłumaczenia VPN na PPN

Dzięki temu będziemy po wykonaniu powyższych zadań będziemy musieli tylko porównać
CT = PPN z tagami w secie

## Zadanie 9
:::success
Autor:​Michał Kolasa ​
:::


cechy HPT (hash page table):
- zawiera jeden wpis dla każdej strony w pamięci głównej
- pojedynczy wpis zawiera zarówno PPN i VPN
- wpis jest adresowany hashem
- pod jednym hashem (PTE) może być do ośmiu wpisów

proces otrzymywania PPN z VPN:
- przepuszczamy VPN przez funkcję hashującą
- szukamy odpowieniego hasha w HPT
- jeśli pod danym hashem mamy jeden wpis bierzemy z niego PPN
- jeśli pod danym hashem jest więcej wpisów liniowo szukamy tego z takim samym VPN
- jeśli żaden wpis nie ma odpowiedniego VPN, może nastąpić ponownie wyszukiwanie po innym hashu

zalety:
- mało odwołań do pamięci
- przy aktualizacji modyfikujemy jeden wpis
- wydajność czasowa

wady:
- trzeba przeznaczyć dużo pamięci