# Lista 10 (13.05.2021), grupa pwit

###### tags: `ask21` `ć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!**

Tabelka zawiera tylko osoby zapisane do grupy.

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
|Wojciech Adamiec | X | X | | X | | X | X | X |
|Kacper Bajkiewicz | X | X | | X | | | | |
|Bartłomiej Hildebrandt| X | X | | X | | X | X | X |
|Dominik Komła | X | X | | X | | | | |
|Aleksandra Kosińska | X | X | | X | | | | |
|Oleś Kulcewicz | X | X | | X | | | X | |
|Damian Lukas | X | X | | X | | | | |
|Michał Mikołajczyk | X | X | | X | | | | |
|Mateusz Opala | X | X | | X | | | | |
|Łukasz Orawiec | X | X | | X | X | X | | |
|Szymon Pielat | X | X | | X | | | | |
|Łukasz Pluta | X | X | | X | | | | X |
|Kamil Puchacz | X | X | | X | | X | X | |
|Magdalena Rzepka | X | X | X | X | | X | | |
|Cezary Stajszczyk | X | X | | X | | | | |
|Jakub Szajner | X | X | | X | | X | X | |
|Bartosz Troszka |==X==| X | | X | | X | X | |
|Miłosz Urbanik | X | X | | X | | X | X | |

Deklaracje zadań z listy 9
| | 6 | 7 |
| --------------------:| --- | --- |
| ... | | |
:::

## Zadanie 1
:::info
Autor: Kacper Bajkiewicz
:::

**głowica** - element dokonujący zapisu/odczytu

**sektor** - najmniejsza fizyczna jednostka zapisu danych na dysku

**czas wyszukiwania** - czas potrzebny kontrolerowi dysku na znalezienie szukanych danych (przeniesienie głowicy między ścieżkami)

**czas opóźnienia obrotowego** - czas w którym dysk obraca się do pozycji w której szukane dane znajdują się pod głowicą odczytu-zapisu.

**czas transferu** - czas potrzebny głowicy na przeczytanie całego sektora


**1. Średni czas wyszukiwania**
Zakładamy że ścieżki są równooddalone z rozkładem jednostajnym. Wtedy wartość oczekiwana to 1/2(Tmax - Tmin). Tmin to 0 (od razu jesteśmy na szukanej ścieżce), Tmax to maksymalny czas na przejście wszystkich ścieżek.

Tmax = liczba_scieżek * scieżki / czas, mamy 400 000 ścieżek i w 1ms przeskakujemy o 50 000 ścieżek. Czyli Tmax ~ 4ms.

> [name=Piotr Witkowski] To obliczenie nie jest poprawne!

Losujemy dwie ścieżki X, Y z przedziału <0, max_liczba_ścieżek> i sprawdzimy jaka jest wartość oczekiwana ich różnicy.

print( sum( abs(random()*8 - random()*8 ) for _ in range(100000) ) / 100000 )

Wynik to: 2.6635967711512234.
Czyli średni czas wyszukiwania to 2,67s.

**2. Średni czas opóźnienia obrotowego**
120 obrotów na sekundę. 1/120 sekundy na jeden obrót.
Maksymalny czas to czas pełnego obrotu, minimalny to 0 (wtedy będziemy od razu na miejscu).
Zatem wartość oczekiwana takiego rozkładu to Tmax - Tmin / 2.
Czyli średni czas opóźnienia obrotowego to:
1/240 = 4,2ms.

**3. Średni czas transferu**

Czas przeczytania całej ścieżki / liczba sektorów.

1/120s * 1/2500 = 1/300000s = 0,3ms.

**4. Całkowity średni czas obsługi żądania**
Suma tych trzech czasów średnich.


## Zadanie 2
:::info
Autor: Dominik Komła
:::

Rozważmy dysk o następujących parametrach: $360$ obrotów na minutę (RPM), $512$ bajtów na sektor, $96$ sektorów na ścieżkę, $110$ ścieżek na powierzchnię.

Obliczmy $T_{\text{avg transfer}}$:


$$T_{\text{avg transfer}} = \frac{60}{\text{RPM}} \cdot \frac{1}{\text{avg # sectors/track}} \cdot \frac{1000 \text{ms}}{1 \text{min}} \cdot 1000 = \frac{60}{360} \cdot \frac{1}{96} \cdot \underbrace{1000}_{\text{milisek.}} = 1.736ms$$

Skoro co bajt następuje przerwanie trwające $2.5 \mu s$, to łączny czas przerwań wyniesie:
$$512 \cdot 2.5\mu s = 1.28 ms$$

Czyli czas pozostały dla procesora bez użycia DMA to:
$1.736 - 1.28 = 0.45 ms$

Jednak jeśli użyjemy DMA, to tylko raz wyślemy przerwanie, więc procesor z całego czasu $1.736 ms$ straci jedynie $2.5\mu s$.

## Zadanie 3
:::info
Autor: Magdalena Rzepka
:::

**Magistrala** - zespół linii przenoszących sygnały oraz układów wejścia-wyjścia służących do przesyłania sygnałów między połączonymi urządzeniami.

**Przepustowość** - rzeczywista szerokosć pasma / maksymalna ilość informacji, jaka może być przesyłana w jednostce czasu.

**Cykl magistrali** - czas potrzebny do wykonania pojedynczej transakcji odczytu lub zapisu między procesorem a urządzeniem zewnętrznym, takim jak pamieć zewnętrzna.

**Podkradanie cykli** - metoda uzyskiwania dostępu do pamięci komputera (RAM) lub magistrali bez ingerencji w procesor. Jest podobny do bezpośredniego dostępu do pamięci (DMA), umożliwiając kontrolerom wejścia/wyjścia odczyt lub zapis pamięci RAM bez interwencji procesora.
Podczas gdy procesor odczytuje instrukcje z pamięci RAM, pamięć RAM jest dostępna dla innych urządzeń.

10 000 000 transferów/sek
320 000 000 bitów/sek = ok. 38MB/sek bez włączonego DMA

1 instrukcja = 32 bity

DMA -> 5MB/s

5/38 = ok. 13% zostanie wykorzystane przez DMA

40% instrukcji procesora wykonuje 1 cykl
60% instrukcji procesora wykonuje 2 cykl

60% * 13% = 7,8% instrukcji zabiera DMA
92,2% instrukcji zostaje

a) 10 milionów / 2 cykle = **5 milionów instrukcji**

b) 5 milionów * 0,922 = **4 610 000 instrukcji**

## Zadanie 4
:::info
Autor: Mateusz Opala
:::
Rozważamy procesor o częstotliwości taktowania 2.5GHz czyli 2.5 cyklu na nanosekundę.
a) Średni czas dostępu to po prostu wartość oczekiwana: $0.9*4+0.1*(0.95*16 + 0.05*(0.98*56+0.02*(256))=5,42$
cyklu. Stąd czas w nanosekundach to $5.42/2.5=2.168$.

b) Pesymistyczny czas to przypadek, w którym szukany blok znajduje się w DRAM. Wtedy będziemy go najpierw wyszukiwać w L1 potem w L2 i L3, a na końcu w DRAM. Stąd łączny czas, który poświęcimy to : $4+12+40+200=256$ cykli. Stąd czas w nanosekundach to $256/2.5=102.4$.

## Zadanie 5
:::info
Autor: Łukasz Orawiec
:::

Przed zleceniem **wyboru wiersza** musi zostać wykonany *precharge*, który resetuje wzmacniacze odczytu i przygotowuje je do załadowania nowego wiersza.

Kondensatory występujące w komórkach pamięci DRAM mają bardzo małą pojemność. Sygnał otrzymywany z komórki w momencie odczytu jest więc bardzo słaby i potrzebny jest **wzmacniacz odczytu**, który taką niewielką zmianę napięcia wykryje i zamieni ją na rozpoznawalny stan logiczny.

Przed zleceniem **wyboru kolumny** otwarty wiersz jest wczytywany do bufora wzmacniaczy odczytu. Na tym buforze może być wykonywan sekwencja odczytów i zapisów do wybranych kolumn.

Pamięć dynamiczna musi być **odświeżana**, ponieważ z kondensatorów wraz z czasem ładunek wycieka. Komórka **pamięci statycznej** składa się z sześciu tranzystorów i nie ma w niej żadnego kondensatora, więc odświeżanie nie jest potrzebne.

Odświeżanie całej pamięci odbywa się wiersz po wierszu. Moduł DRAM utrzymuje licznik pamiętający adres ostatnio odświeżonego wiersza. Kontroler z ustaloną częstotliwością wydaje polecenie odświeżenia, które zwiększa licznik i odświeża wiersz.

## Zadanie 6
:::info
Autor: Miłosz Urbanik
:::

#### synchroniczna pamięć DRAM (synchronous dynamic random-access memory/ SDRAM)
pamięć DRAM, w której działanie jej interfejsu jest skoordynowane z zewnętrzym zegarem.


#### opóźnienie bramkowania kolumny $t_{CAS}$ (CL, column access strobe latency)
czas pomiędzy wysłaniem żadania dostępu do kolumny pamięci, a początkiem przekazywania danych do kontrolera. (Odczyt kolumny z sense amplifier'a i przekazanie jej na magistralę)

#### opóźnienie wyboru wiersza $t_{RCD}$ (row-to-column command delay)
czas od momentu wyboru aktywnego wiersza do rozpoczęcia wyboru aktywnej kolumny. (Naładowanie sense amplifier'a, ściągnięcia do niego całego wiersza, wyrównanie napięc do 0 i 1 we wzmacniaczu)

#### opóźnienie wstępnego ładowania wiersza $t_{RP}$ (row precharge)
czas pomiędzy zamknięciem dostępu do poprzednio odczytywanego wiersza, a rozpoczęciem dostępu do kolejnego. (Odnowienie wiersza, który znalazł się wcześniej w sense amplifierze)

#### opóźnienie bramkowania wiersza $t_{RAS}$ (row access strobe)
czas pomiędzy początkiem aktywacji wiersza do momentu odświeżenia wiersza.


Komórka pamięci ma przydzielony wirtualny adres (model tablicy komórek), który przez procesor jest tłumaczony na adres fizyczny, który ostatecznie kontroler pamięci przekłada na adres odpowiedniego układu pamięci RAM, oraz w ramach tego układu odpowiednią lokalizacją kolumny i wiersza samej pamięci.

1. Odczyt zaczyna się, gdy kontroler upewni się, że adres wiersza pamięci jest dostępny i wyłącza sygnał $RAS$. Włączenie sygnału wiersza zamyka aktywny wiersz.
2. Sygnał $CAS$ wysłany jest po czasie $t_{RCD}$. Wtedy przekazujemy adres kolumny.
3. Adresowanie jest zakończone, natępnie pamięć przygotowuje się do przesłania danych w czasie $CL$
4. Kontroler może zadecydować o przesłaniu więcej niż jednego słowa, co pozwala na wypełnieniu pamięci podręcznej bez konieczności przesłania kolejnej sekwencji sygnałów $RAS$ i $CAS$
5. Kontroler może również zadecydować przesłaniu informacji o odczycie z innej kolumny aktywnego wiersza, bez konieczności transmitowania sygnału $RAS$.


## Zadanie 7
:::info
Autor: Kamil Puchacz
:::


Wiemy, że jeden blok ma $64$ bajty, a w trakcie jednego cyklu można przesłać $64$ bity, czyli jedno słowo.

Przygotowanie wiersza zajmie czas $t_{RP}$, a więc musimy wybrać kolumnę, a następnie wczytać ją do specjalnego wiersza. Wczytanie wiersza zajmie czas $t_{RP} + t_{RCD}$, jako że najpierw musimy wyszukać wiersz, a następnie znaleźć szukaną komórkę w tym wierszu. Kolejnym krokiem jest wczytanie tej komórki, a więc ustawiany jest na niej wskaźnik i w razie odczytywania danych z kolejnych komórek, dodajemy czas $t_{CAS}$.

Musimy wybrać kolumnę, a następnie wczytać ją do specjalnego wiersza. Wczytanie wiersza zajmie czas $t_{RP} + t_{RCD}$, skoro najpierw musimy wyszukać wiersz, a potem znaleźć szukaną komórkę w tym wierszu. Następnie musimy wczytać tą komórkę, a więc ustawiany jest na niej wskaźnik i w razie odczytywania danych z kolejnych komórek, więc dodajemy czas $t_{CAS}$.

W najgorszym przypadku liczba cykli (dla `DDR4-1600` i `DDR4-2133`) wyniesie:
$c_1 = max(tRAS,tRCD+8*tCAS+8)+tRP = 108$
$c_2 = max(tRAS,tRCD+8*tCAS+8)+tRP = 158$

policzmy czas wykorzystując obliczoną liczbę cykli i znane taktowanie:
$t_1 = \frac{c_1}{t_{CLK}} = \frac{108}{800\text{MHz}} = 135 ns$
$t_2 = \frac{c_2}{t_{CLK}} = \frac{158}{1066.67\text{MHz}} = 148 ns$

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

$c_1 = max(tRAS,tRCD+tCAS+4)+tRP = 35$
$c_2 = max(tRAS,tRCD+tCAS+4)+tRP = 51$

Taktowanie nie ulega zmianie, korzystamy więc z tych samych wzorów:
$t_1 = \frac{c_1}{t_{CLK}} = \frac{35}{800\text{MHz}} = 43.7 ns$
$t_2 = \frac{c_2}{t_{CLK}} = \frac{51}{1066.67\text{MHz}} = 47.8 ns$

## Zadanie 8
:::info
Autor: Wojciech Adamiec
:::
:::info
:::

Wiemy, że cała tablica zajmuje $4\text{GiB} = 2^{32} \text{ bajtów}$. Skoro rozmiar wiersza to $8\text{KiB} = 2^{13}\text{bajtów}$ to tablica będzie miała wymiary $2^{19} \text{ wierszy} \times 2^{13} \text{ kolumn}$. W jednym momencie możemy przeczytać $16$ słów, co odpowiada $2^7$ bajtom, a na cały wiersz składa się $2^{13}\text{bajtów}$. To znaczy, że w ciągu $\frac{2^{13}}{2^7} = 64$ czytań z kolumn można sprowadzić cały wiersz.


Dla DDR4-2133 mamy: $CLK = 1066.67 MHz$

$c_w = max(t_{RAS}, t_{RCD} + 64 \cdot t_{CAS}+ 64) + t_{RP}$

$c_w = max(36, 15 + 64 \cdot 15 + 64) + 15 = 1054$

$c_t = 2^{19} \cdot c_w = 552.599.552$

$t=\frac{552599552}{1066.67\text{MHz}} = \frac{552599552}{1066.67 \cdot 1000000}s = 0.519s$

**Dual-channel** – technologia stosowana w kontrolerach pamięci, do wydajniejszej obsługi pamięci RAM. Polega na podwojeniu przepustowości przesyłu danych pomiędzy kontrolerem pamięci a pamięcią RAM.

Dla konfiguracji dwukanałowej jesteśmy w stanie 2-razy szybciej sprowadzić cały wiersz, bo czytamy na cykl 32 słowa.

$c_w = max(t_{RAS}, t_{RCD} + 32 \cdot t_{CAS}+ 32) + t_{RP}$

$c_w = max(36, 15 + 32 \cdot 15 + 32) + 15 = 542$

$c_t = 2^{19} \cdot c_w = 276.299.776$

$t=\frac{276299776}{1066.67\text{MHz}} = \frac{276299776}{1066.67 \cdot 1000000}s = 0.267s$