---
# System prepended metadata

title: 'Lista 10 (13.05.2021), grupa pwit'
tags: [pwit, ask21, ćwiczenia]

---

# 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

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

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

```python=
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.

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


## 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}}$:

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

$$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.

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


#### 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.

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


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$.

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



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

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

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

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.

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

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$


