# Ćwiczenia 9, grupa cz. 14-16, 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | | |
Mateusz Burdyna | | | | | | | | | |
Dariusz Ciesielski | | | | | | | | | |
Dawid Dudek | X | X | X | X | X | X | | | |
Mikołaj Dworszczak | | | | | | | | | |
Przemysław Grochal | X | X | X | X | X | X | | X | |
Adam Jarząbek | X | X | X | X | X | ==X== | | | |
Anna Karykowska | X | X | X | X | X | X | | | |
Oleś Kulczewicz | | | | | | | | | |
Pola Marciniak | X | X | X | X | X | X | X |==X==| |
Mikołaj Mroziuk | | | | | | | | | |
Marcelina Oset | X | X | X | | | | | | |
Natalia Piasta | X | ==X== | X | X | X | X | | X | |
Krzysztof Piekarczyk | X | X | X | X | | X | | | |
Marcin Płaza | X | ==X== | X | X | X | X | X | X | |
Paweł Richert | ==X== | X | X | X | | X | | X | |
Rafał Starypan | X | X | ==X== | X | X | X | X | | |
Dawid Strojek | | | | | | | | | |
Mateusz Suszek | X | X | X | X | X | ==X== | X | X | |
Wojciech Śniady | X | X | X | X | X | X | X | | |
Volha Tsekalo | ==X== | X | X | X | | X | X | | |
Yana Vashkevich | ==X== | X | X | X | | X | X | | |
Konrad Woźniak | X | X | X | X | | X | X | | |
Natalia Czerep | | | | | | | | | |
Joanna Stachowicz | X | X | X | | | X | | | |
:::

**Tu można dodeklarować zad. 6. z listy 8.:**
*
*
*

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

## Zadanie 1
:::success
Autor: Yana Vashkevich
:::

Pierwsze dwie cyfry adresu są $tagiem$, ostatnia cyfra to $indeks + offset$

832 -> 83-tag, 2=0010, gdzie 00-set oraz 10-offset
835 -> 83-tag, 5=0101, gdzie 01-set oraz 01-offset
FFD -> FF-tag, D=1101, gdzie 11-set oraz 01-offset

| Adres |Trafienie?| Wartość |
| -------- | -------- | -------- |
| 832 | tak | CC |
| 835 | nie | - |
| FFD | tak | C0 |

## Zadanie 2
:::success
Autor: Marcin Płaza
:::


- b = 5, więc blok ma rozmiar 2^5 bajtów
- s = 5, więc mamy 2^5 wierszy
- mamy 32 bajty po 8 bitów danych do tego tag i valid,
czyli 2^8 / (22 + 1)

## Zadanie 3
:::success
Autor: Rafał Starypan
:::


| Tag | Index | Offset |
| --- | ----- | ------ |
| 22 | 5 | 5 |

| Address | Tag | Index | Offset | Result | Notes |
| ------- | --- | ----- | ------ | ---------- | -------------------------------- |
| 0 | 0 | 00000 | 00000 | compulsory |
| 4 | 0 | 00000 | 00100 | hit | (z wpisu 0) |
| 16 | 0 | 00000 | 10000 | hit | (z wpisu 0) |
| 132 | 0 | 00100 | 00100 | compulsory |
| 232 | 0 | 00111 | 01000 | compulsory |
| 160 | 0 | 00101 | 00000 | compulsory |
| 1024 | 1 | 00000 | 00000 | conflict | zastąpi poprzedni wpis w i=0 |
| 28 | 0 | 00000 | 11100 | conflict | j/w |
| 140 | 0 | 00100 | 01100 | hit | (z wpisu 132) |
| 3100 | 11 | 00000 | 11000 | conflict | zastąpi wpis o i=0 |
| 180 | 0 | 00101 | 10100 | hit | (z wpisu 160) |
| 2180 | 10 | 00100 | 00100 | conflict | zastąpi poprzedni wpis o i=00100 |

Efektywność: 4/12

Zawartość pamięci:
| Index | Tag |
| ----- | --- |
| 0 | 11 |
| 100 | 10 |
| 101 | 0 |
| 111 | 0 |

## Zadanie 4
:::success
Autor: Konrad Woźniak
:::


## Zadanie 5
:::success
Autor: Mateusz Suszek
:::

## Zadanie 6
:::success
Autor: Adam Jarząbek
:::

Średni czas dostępu do pamięci tylko z L1:

$0.66 ns + 0.08 \cdot 70ns = 6.26ns \approx 9.48$ cykli

Średni czas dostępu do pamięci z L1 i L2:
$0.66ns + 0.08\cdot 5.62ns + 0.08 \cdot 0.0005 \cdot 70ns = 1.138 ns \approx 1.72$ cykli

CPI tylko z pamięcią L1:
$1 - 0.36 = 0.64$ - współczynnik instrukcji nie odwołujących się do pamięci
$1\cdot 0.64 + 0.36 \cdot 9.48 \approx 4.05$ CPI

CPI z pamięciami L1 i L2:
$1\cdot 0.64 + 0.36 \cdot 1.72 \approx 1.26$ CPI

## Zadanie 7
:::success
Autor: Volha Tsekalo
:::
4! - tyle jest permutacji ciągu 4-elementowego.
Załóżmy, że ciag sie sklada z 4 linii: 1, 2, 3, 4.
Pomysł: bierzemy ceiling($log_2(4!)$)=5 bitów. Pierwsze dwa bity określają pozycję 1, drugie dwa pozycję dwójki, następny bit jest pozycją linii 3., ostatnie wolne miejsce to pozycja linii 4.
Przykład:
$1234$ == 00 00 0
$1243$ == 00 00 1
$4321$ == 11 10 1
Jak chcemy usunąc najstarszą linię, dodajmy 1 do każdej cześci, reprezentującej pozycję linii (ignorujemy overflow).
$1234$: 4 jest najstarsza, jest kandydatem do usunięcia. Dodajemy jedynki:
00 00 0 -> 01 01 1, czyli mamy $4123$.
Największą pozycją dla jedynki jest 11(mamy 4 miejsca do dyspozycji), dla dwójki - 10 (wybieramy spośród 3 miejsc), dla trójki - 1(wybieramy spośród 2 miejsc).

## Zadanie 8
:::success
Autor: Pola Marciniak
:::


## Zadanie 9
:::success
Autor: Krzysztof Piekarczyk
:::




Hit_rate = 0.75

Jeżeli zamienimy pętle, to hit_rate = 0.875