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

## Zadanie 1

:::success
Autor: Kacper Solecki
:::

- plater - wirujący dysk pokryty nośnikiem magnetycznym, przechowujący dane
- głowica - ruchomy element dysku, który odczytuje dane z platera, zatrzymując się nad wybraną ścieżką
- ścieżka - pas w kształcie pierścienia na platerze, na którym zapisane są dane
- sektor - spójny odcinek na ścieżce, sektory oddzielone sa przerwami, pamięć czytana jest sektorami


- czas wyszukiwania - czas potrzebny na poruszenie głowicy w opowiednie miejsce nad platerem (nad odpowiednią ścieżkę)

$T_{avg\_seek} = \sum_{i=1}^{4\cdot 10^5} \sum_{j=1}^{4\cdot 10^5} \bigg( \frac{|i-j|}{5\cdot 10^4}ms \bigg) \cdot (4\cdot 10^5)^{-2} \approx 2\frac{2}{3}ms$

- czas opóźnienia obrotowego - czas, w którym głowica czeka z odczytem/zapisem danych aż plater obróci się tak, by odpowiedni sektor był pod nią

$T_{avg\_rotate} = \frac{1}{7200}\frac{min}{rot} \cdot \frac{1}{2} rot \cdot 60 \frac{s}{min} = \frac{1}{240}s$

- czas transferu - czas odczytu/zapisu danych z sektora przez głowicę

$T_{avg\_transfer} = \frac{1}{7200}\frac{min}{rot} \cdot \frac{1}{2500}\frac{rot}{sector} \cdot 6 \cdot 10^7\frac{μs}{min} = \frac{10}{3}μs$

- łączny czas:
$T_{avg\_sum} = T_{avg\_seek} + T_{avg\_rotate} + T_{avg\_transfer} \approx 0.0068367s$

> [name=Szymon Jędras] Szukając sposobu na obliczenie $T_{avg\_seek}$ natrafiłem na ten dokument:
> https://pages.cs.wisc.edu/~remzi/OSFEP/file-disks.pdf

## Zadanie 2

:::success
Autor: Magdalena Jarecka
:::

:::info
Rozważmy dysk z poprzedniej epoki o następujących parametrach: 360 obrotów na minutę,
512 bajtów na sektor, 96 sektorów na ścieżkę, 110 ścieżek na powierzchnię. Dysk sygnalizuje dostępność
danych zgłaszając przerwanie na każdy przeczytany bajt, a wykonanie procedury przerwania zajmuje 2.5µs.
Następnie do systemu dodajemy kontroler DMA, więc przerwanie będzie generowane tylko raz po wczytaniu
sektora do pamięci. Ile czasu zostanie procesorowi na pozostałe czynności w trakcie czytania n sektorów
(a) bez użycia (b) przy użyciu kontrolera DMA? Należy zignorować czas wyszukiwania ścieżki i sektora.
:::
Czas potrzebny na sciągnięcie 1 sektora
$T_{\text{avg transfer}} = \frac{60}{\text{RPM}} \cdot \frac{1}{\text{avg # sectors/track}} \cdot \frac{1000 \text{ms}}{1 \text{min}} = \frac{60}{360} \cdot \frac{1}{96} \cdot \underbrace{1000}_{\text{milisek.}} = 1.736ms$

A)
Łączny czas przerwań na sektor wyniesie:
$512 \cdot 2.5\mu s = 0.00128 s = 1.28 ms$

$n * (1,736ms - 1,28ms) = 0,456ms * n$

Z kontrolerem DMA mamy tylko jedno przerwanie na sektor.
B)
$n * (1,736ms - 0,0025ms) = 1,7335ms * n$

**Przerwanie** - sygnał powodujący zmianę przepływu sterowania, niezależnie od aktualnie wykonywanego programu.

**Kontroler DMA** - DMA to technika w której sprzęt komputerowy podłączony do płyty głównej może korzystać z RAM pomijając przy tym CPU. Aby to wykorzystać procesor musi zaprogramować kontroler DMA do wykonania odpowiedniego transferu danych a następnie na czas przesyłania danych zwolnić magistralę systemową.

## Zadanie 3

:::success
Autor: Michał Doros
:::
Magistrala - część umożliwiająca przesyłanie danych między różnymi częściami komputera
Przepustowość - liczba danych która może być przesłana w ciągu sekundy, alternatywnie ilość transakcji
Cykl magistrali - cykl podczas którego następuje przesłanie danych przez magistralę, wykonywany w czasie 1 lub kilku taktów zegaru procesora
Podkradanie cykli - technika w której DMA zajmuje magistralę wysyłając sygnał BR(bus request) tylko na jeden cykl, a następnie oddaje ją procesorowi wysyłając BG(bus grant) dzięki czemu nie wstrzymuje pracy procesora na dłużej

**a)** wykonanie instrukcji wymaga 2 cykli magistrali, nic nam nie przeszkadza więc wykonamy 5 milionów instrukcji/s
**b)**
przepustowość szyny - 32bity * $10^7$/s = 40MB/s
prędkość odczytu - 5MB/s
więc 12,5% cykli szyny zostanie wykorzystane przez DMA
procesor zawsze wykorzystuje 1. cykl i 40% czasu 2. cykl, zatem wykorzystuje 70% cykli magistrali
zatem 12,5% * 70% = 8,75% czasu DMA zatrzyma procesor
odp: 5 000 000 * 0.9125 = 4 562 500

## Zadanie 4

:::danger
Autor: Szymon Kosakowski
:::

- pamieć podręczna (cache)-przechowuje bloki pamięci z poziomu niżej w hierarchii pamięci (większej i wolniejszej pamięci). Jej celem jest umożliwienie dotarcia szybciej do danych, które prawdopodobnie będą ponownie odczytywane.
- blok pamięci-dane są trzymane w blokach
- hierarchia pamięci - pamięć komputera jest uszeregowana od najszybszej (rejestry procesora) przez kolejne pamięci podręczne do największej i najwolniejszej (dysk twardy). Każda pamięć w hierarchii jest cachem dla tej z poziomu niżej.

| poziom pamięci|procent trafeń |czas dostępu (liczba cykli)|średnia liczba trafeń na 100 dostępów|
|----|----|---|--|
|L1|90%|4|90|
|L2|95%|12|9,5|
|L3|98%|40|0,49|
|DRAM|100%|200|0,01|

Obliczanie średniej liczby trafień na 100 dostępów:

- na poziomie L1 średnia ilość trafień na 100 dostępów to $100 * 90\% = 90$
- do L2 przejdą te dostępy, które nie trafiły w L1 - pozostałe $10$, więc średnia ilość trafień to $10 * 95\% = 9,5$
- L3: $0.5 * 98\% = 0.49$
- DRAM: pozostałe $0.01$

Czas średni mamy wtedy, gdy trafiamy zgodnie z prawdopodobieństwem:
$$t_{śr_c}=\frac{4*90+16*9,5+56*0,49+0,01*256}{100}=5.5$$

dla procesora i7-6700 z częstotliwością $2.5GHz$, czas jednego cyklu to $0.4ns$

$t_{śr_{ns}} = 0.4ns * 5.5 = 2.2ns$

pesymistycznie $4+12+40+200 = 256$ cykli
$t_{pes} = 256*0.4ns = 102.4ns$

> [name=Szymon Jędras] (a) średni czas dostępu:
`0.9*4 + 0.1*0.95*16 + 0.1*0.05*0.98*56 + 0.1*0.05*0.02*256 = 3.6 + 1.6 + 0.2744 + 0.0256 = 5.5 cykli`
`5.52 * 1s/2'500'000'000 = 2.2ns`
## Zadanie 5

:::info
Autor: Kacper Puchalski
:::
pamięc dynamiczna (DRAM) - pamięć przechowywująca każdy bit danych w jednym kondensatorze. Ze względu na ciągle rozładowywujący się kondensator pamięć jest ulotna i wymaga odświeżania
wybór wiersza- adres wiersza podawany jest jako kilka mniejszych lini adresowych. Taki adres musi być przed odczytem zdemultipleksowany (? demultiplexed). Demultiplekser z N liniami adresowymi będzie miał $2^N$ możliwych wyjściowych adresów
wybór kolumny- Tak samo jak wybór wiersza

* Co musi się stać przed zleceniem wyboru wiersza?
Prechargować wiersz (i bitlajny) do wartości w połowie pomiędzy najniższym a najwyższym możliwym napięciem
* Wyjaśnij zasadę działania wzmacniaczy odczytu (ang. sense amplifiers).
Niski ładunek sprawia że dane prosto z komórki nie nadają się do bezpośredniego odczytu. Trzeba więc "otworzyć" wiersz. Wzmacniacze zamieniają małą różnicę w napięciu pomiędzy bitlajnami odpowiednio na 0 lub 1
* Czemu otwarty wiersz musi zostać wczytany do bufora przed zleceniem wyboru kolumny?
Bufor jest pamięcią statyczną, po odczytaniu czegoś z DRAMu to coś znika, kondesator się rozładowywuje. Musimy więc to załadować do bufora
* Co musi się wydarzyć w trakcie zamykania wiersza?
Ponowne naładowanie kondensatorów w wybranym wierszu

* Czemu pamięć dynamiczna musi być odświeżana w przeciwieństwie do pamięci statycznej?
W kondesatorach znajduje się elektrony, które pomimo wysokiej oporności tranzystora i tak wyciekają. Trzeba je więc odświeżać aby nie tracić informacji
* W jaki sposób przeprowadzane jest odświeżanie całej pamięci?

Odświeżanie musi się odbywać co ok. 64ms. Podczas odświeżania nie ma dostępu do odświeżanej pamięci, więc całość jest odświeżana częściami, aby nie utracić dostępu całkowicie. To właśnie czas potrzebny na pełne rozładowanie i naładowanie kondestatora ogranicza prędkość DRAMu.
Odświeżenie jest tak naprawdę operacją zczytania danych, gdzie wynik jest wyrzucany. Zczytanie danych defaultowo odświeża kondesator, ponieważ przy zczytywaniu on się rozładowywuje, trzeba go z powrotem naładować.

## Zadanie 6

:::success
Autor: Franciszek Malinka
:::

**Synchroniczna pamięć DRAM** - pamięć DRAM, która działa względnie z pewnym licznikiem czasu (zegarem), tj. wszyskie operacje wykonywane są sekwencyjnie względem zegara.

Protokuł odczytywania słów pamięci:

Kontroler pamięci komunikuje się z DRAM przy pomocy kilku linii:
- RAS (Row Address Selection),
- CAS (Column Address Selection),
- Address (przesyła numery wierszy/kolumn z których będziemy czytać),
- DQ (Data Queue)

Schemat protokołu odczytywania pamięci RAM:
1. Obniżamy sygnał RAS i w tym samym momencie na szynie Address przesyłamy numer wiersza, z którego będziemy czytać
2. Po czasie $t_{RCD}$ obniżamy sygnał CAS i w tym samym momencie na szynie Address przesyłamy numer kolumny. Czas $t_{RCD}$ (RAS-to-CAS Dealy) to liczba cykli zegara, które musimy odczekać zanim wyślemy numer kolumny. Wynika to z tego, że musimy najpierw naładować bitline'y i przygotować wzmacniacze sygnału.
3. Po czasie $T_{CL}$ (CAS Latency) dane są gotowe do odczytu i przesyłane przez szynę DQ. Kontroler pamięci może poprosić o przesłanie większej liczby słów, 2, 4 lub 8.
4. Jeśli chcemy odczytywać następne kolumny, możemy po prostu ponownie opuścić sygnał CAS, wysłać numer kolumny i wrócić do kroku 3.

Jeżeli teraz chcemy odczytać następny wiersz, to na końcu kroku 3 wykonujemy:

5. Nie ma dedykowanej linii która ma informować o potrzebie deaktywacji aktualnego wiersza, dlatego można np. w tym samym momencie obniżyć sygnał RAS oraz WE (Write Enable). Po czasie $T_{RP}$ (Row Precharge Time), potrzebnym do deaktywacji aktualnego wiersza, możemy przystąpić do wyboru nowego wiersza, jak w kroku 1. Okazuje się, że przesyłanie danych w kroku 3. może dziać się w tym samym czasie co precharge, dzięki czemu realny czas oczekiwania na dostęp do następnego wiersza może być mniejszy.

The time it takes for a row access command to discharge and
restore data from the row of DRAM cells is known as
the Row Access Strobe latency or $T_{RAS}$. Po ludzku - od momentu rozładowywania danego wiersza do momentu rozpoczęcia prechargowania bitline'ów musimy odczekać $T_{RAS}$ cykli.

## Zadanie 7

:::success
Autor: Franciszek Pindel
:::

>Blok pamięci podręcznej procesorów x86-64 ma 64 bajty. Dla uproszczenia przyjmijmy, że w jednym cyklu zegarowym między pamięcią a procesorem można przesłać 64 bity danych. Ile nanosekund, w pesymistycznym przypadku, zajmie sprowadzenie bloku pamięci podręcznej z pamięci DRAM dla poniżej scharakteryzowanych modułów. Powtórz obliczenia zakładając, że pamięć działa w trybie sekwencyjnym (ang. burst mode), tj. podaje na kolejnych zboczach zegara szesnaście 64-bitowych słów bez czekania na polecenie zmiany kolumny.


* DDR4-1600, ${}^tCLK$ = 800MHz, ${}^tCAS$ = 10, ${}^tRCD$ = 10, ${}^tRP$ = 10, ${}^tRAS$ = 25

Przypadek pesymistyczny, czyli za jednym razem będą przesyłane 64 bity:

| operacja | operacja | czas w cyklach |
| -------- | ----------------- | -------------- |
| tRAS | tRCD | 10 |
| | CL (tCAS) | 10 |
| | przesył danych | 1 |
| | (dalej trwa tRAS) | 4 |
| | tRP | 10 |

Sumarycznie pobranie 64 bitów zajmie 35 cykli, czyli wysłanie 64 bajtów zajmie $35 \cdot 8 \cdot \frac{1}{800} \cdot 10^{-6} s = 35 \cdot 10^{-8} = 350\text{ ns}$

Pamięć DDRAM może przesyłać dane na obu zboczach zegara, potrzebne jest wysłanie 8 słów, co potrwa 4 cykle:

| operacja | operacja | czas w cyklach |
| -------- | ----------------- | -------------- |
| tRAS | tRCD | 10 |
| | CL (tCAS) | 10 |
| | przesył danych | 4 |
| | (dalej trwa tRAS) | 1 |
| | tRP | 10 |

Czyli 64 bajty mogą być wysłane w 35 cykli czyli $35 \cdot \frac{1}{800} \cdot 10^{-6} s = 4.375 \cdot 10^{-8} s = 43.75\text{ ns}$ (8 razy szybciej)

* DDR4-2133, ${}^tCLK$ = 1066.67MHz, ${}^tCAS$ = 15, ${}^tRCD$ = 15, ${}^tRP$ = 15, ${}^tRAS$ = 36

pesymistyczny przypadek:

| operacja | operacja | czas w cyklach |
| -------- | ----------------- | -------------- |
| tRAS | tRCD | 15 |
| | CL (tCAS) | 15 |
| | przesył danych | 1 |
| | (dalej trwa tRAS) | 5 |
| | tRP | 15 |

Sumarycznie pobranie 64 bitów zajmie 51 cykli, czyli wysłanie 64 bajtów zajmie $51 \cdot 8 \cdot \frac{1}{1066.67} \cdot 10^{-6} s \approx 0,38 \cdot 10^{-6} = 380\text{ ns}$

sekwencyjne przesłanie, potrzebne są 4 cykle

| operacja | operacja | czas w cyklach |
| -------- | ----------------- | -------------- |
| tRAS | tRCD | 15 |
| | CL (tCAS) | 15 |
| | przesył danych | 4 |
| | (dalej trwa tRAS) | 2 |
| | tRP | 15 |

czyli znowu zamiast ośmiu przesłań wystarczy 1, czyli to potrwa $47.5ns$

## Zadanie 8

:::success
Autor: Wojciech Bogucki
:::

**DDR4-2133**
$CLK = 1066.67$ MHz co daje $0,94$ ns
$t_{CAS} = 15$
$t_{RCD} = 15$
$t_{RP} = 15$
$t_{RAS} = 36$

Liczba wierszy tablicy to $4GiB / 8KiB = 524288$

### Single-channel

Umiemy przeczytać $16$ słowa na cykl, czyli $128$ bajtów.
Jeden wiersz($8KiB$) wyślemy w ciągu $64$ cykli.

$t_{wierszu} = max(t_{RAS}, t_{RCD} + 64 \cdot t_{CAS} + 64) + t_{RP}$
$t_{wierszu} = max(36, 15 + 64 \cdot 15 + 64) + 15 = 1039 + 15 = 1054$
$t_{wierszu} \cdot 0,94 = 1054 \cdot 0,94 = 990,76$ ns

Wynik dla całej pamięci wyniesie:
$990,76 \cdot 524288 = 519443578,88\ \text{ns} = 0,519443579$ s

### Dual-channel

Umiemy przeczytać $32$ słowa na cykl, czyli $256$ bajtów.
Jeden wiersz($8KiB$) wyślemy w ciągu $32$ cykli.

$t_{wierszu} = max(t_{RAS}, t_{RCD} + 32 \cdot t_{CAS} + 32) + t_{RP}$
$t_{wierszu} = max(36, 15 + 32 \cdot 15 + 32) + 15 = 527 + 15 = 542$
$t_{wierszu} \cdot 0,94 = 542 \cdot 0,94 = 509,48$ ns

Wynik dla całej pamięci wyniesie:
$509,48 \cdot 524288 = 267114250,24\ \text{ns} = 0,26711425$ s