---
# System prepended metadata

title: 'Ćwiczenia 9, grupa cz. 14-16, 5. maja 2022'
tags: [SYK21, pwit, ćwiczenia]

---

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

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

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

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

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

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

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




## Zadanie 5
:::success
Autor: Mateusz Suszek
:::
![](https://i.imgur.com/7CK1qfB.jpg)



## Zadanie 6
:::success
Autor: Adam Jarząbek
:::
![](https://i.imgur.com/thoFFdg.png)

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

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


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

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


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


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


Hit_rate = 0.75

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