# SEM2 SYK ćw. 7
## ZAD 2
Zadanie 2. Rozważmy program składający się z dwóch plików źródłowych:

/* str-a.c */
#include <stdio.h>

char *somestr(void);

int main(void) {
char *s = somestr();
s[5] = ’\0’;
puts(s);
return 0;
}

/* str-b.c */
char *somestr(void) {
return "Hello, world!";
}

Po uruchomieniu program kończy się z błędem dostępu do pamięci. Dlaczego? Gdzie została umieszczona
stała znakowa "Hello, world!"? Popraw ten program tak, by się poprawnie zakończył. Gdzie został
umieszczony ciąg znaków po poprawce? Nie wolno
:::info
Możemy zauważyć, że w pliku ‘str-b.c’ napisu “Hello, World” nie przypisujemy do żadnej zmiennej, a jedynie zwracamy. Spowoduje to, że zostanie on przypisany do sekcji “read only data”. Program konczy się błędem dostępu do pamięci, ponieważ w linii 8 ‘str-a.c’ chcemy modyfikowac ten napis.

static char temp[] = "Hello, world!";
char *somestr(void) {
    return temp;
}


:::
## ZAD 3 (2 pkt)
## ZAD 4
Jakie konstrukcje językowe w C są blokadami optymalizacji (ang. optimization blockers)? Porównaj funkcje combine1 i combine4 ze slajdów i wyjaśnij, dlaczego wydajniejsza wersja musiała zostać stworzona ręcznie.

void combine1(vec_ptr v, data_t *dest)
{
    long int i;
    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++) {
    data_t val;
    get_vec_element(v, i, &val);
    *dest = *dest OP val;
    }
}

void combine4(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v); // liczymy tylko raz długość
    data_t *d = get_vec_start(v);// zapisujemy wskaźnik na początek wektora
    data_t t = IDENT;            // zmienna tymczasowa
    for (i = 0; i < length; i++) 
        t = t OP d[i];           // akumulujemy w zmiennej tymczasowej
    *dest = t;
}

:::info
Blokada optymalizacji - aspekt programu, który może poważnie ograniczyć możliwości generowania zoptymalizowanego kodu przez kompilator.

W C blokadami optymalizacji są:
- Procedure calls
- Memory aliasing
Kompilator nie potrafi wykonać takiej optymalizacji, bo nie wie, że w intencji programisty adresy a i b są rozłączne. Widzi więc taki przypadek, w którym taka optymalizacja zmieniłaby semantykę programu.

Optymalizacje:
- długość v jest liczona tylko raz
- rezygnujemy ze sprawdzania czy próbujemy odczytać nieistniejący index w wektorze
- używamy zmiennej tymczasowej

Kompilator może podjąć się optymalizacji tylko i wyłącznie jeśli ma pewność, że optymalizacja nie będzie miała żadnch negatywnych skutków. Kompilator nie jest w stanie wykonać takich operacji, które mogłyby zmienić semantykę programu.


#### Problem 1
Funkcja `get_vec_element` jest nadmiarowa, ponieważ sprawdza, czy indeks nie jest większy niż długość wektora, a my już to wiemy z warunku pętli.
#### Rozwiązanie:
Wystarczy przed wejściem do pętli uzyskać wskaźnik na początek wektora, a później tylko zwiększać indeks bez zbędnego porównywania go z długością wektora.

---

#### Problem 2
Funkcja `vec_length` sprawdza długość wektora i niepotrzebnie wykonuje się w każdym obrocie pętli, bo wiemy, że jego długość się nie zmienia.
#### Rozwiązanie:
Wystarczy raz wywołać `vec_length` przed wejściem do pętli i zapisać wynik do jakiejś zmiennej.

---

#### Problem 3
W każdym obrocie pętli dwa razy wykonujemy dereferencję wskaźnika `dest`.
#### Rozwiązanie:
Możemy wprowadzić zmienną lokalną, do której będzie zapisywać wyniki.

:::
## ZAD 5
## ZAD 6
Rozpatrujemy procesor o charakterystyce podanej w tabeli 5.12 podręcznika „Computer Systems: A Programmer’s Perspective”. Zdefiniuj miarę wydajności CPE (ang. cycles per element/operation),
następnie wyjaśnij pojęcie granicy opóźnienia (ang. latency bound) oraz granicy przepustowości (ang. throughput bound) procesora. Skąd biorą się wartości w tabelce na stronie 560?

***CPE*** *(cycles per element/operation)* mówi o tym, ile cykli procesora zajmuje przetworzenie jakiegoś elementu/wykonanie jakiejś operacji.

O ***latency bound*** *(granica opóźnienia)* mówimy, gdy seria operacji musi zostać wykonana w ścisłej kolejności, ponieważ wynik jednej operacji jest wymagany przed rozpoczęciem kolejnej. Latency bound może ograniczyć wydajność programu.

***Throughput bound*** *(granica przepustowości)* charakteryzuje zdolność obliczeniową jednostek funkcjonalnych procesora. Ta granica staje się ostatecznym ograniczeniem wydajności programu.


**Latency** - liczba cykli procesora, jaką zajmuje wykonanie operacji
**Issue** - minimalna liczba cykli, która musi upłynąć, by można było zacząć kolejną niezależną operację
**Capacity** - wskazuje ile operacji można rozpocząć jednocześnie
## ZAD 7
## ZAD 8
Rozważmy dysk o następujących parametrach: jeden talerz; jedna głowica; 400 tysięcy ścieżek
na powierzchnię; 2500 sektorów na ścieżkę; 7200 obrotów na minutę; czas wyszukiwania: 1ms na przeskoczenie o 50 tysięcy ścieżek.
1. Jaki jest średni czas wyszukiwania?
2. Jaki jest średni czas opóźnienia obrotowego?
3. Jaki jest czas transferu sektora?
4. Jaki jest całkowity średni czas obsługi żądania?


$T_{avg-seek} = \frac{1}{3} \cdot \frac{400000}{50000} = \frac{8}{3} \approx 2,667ms$
(czas, aż głowica wejdzie na pierwszy bit)
Głowica kręci się tylko w jedną stronę, więc tutaj średnią będzie połowa czasu całego obrotu
$T_{avg-rotation} = \frac{1}{2} \cdot \frac{60s}{7200RPM} \cdot \frac{1000ms}{1s} \approx 4 ms$
(ile czasu trwa czytanie bitów z sektora)
Trzeba przelecieć cały sektor.
$T_{avg-transfer} = \frac{60s}{7200RPM} \cdot \frac{1}{2500sectors/tracks} \cdot \frac{1000ms}{1s} \approx 0,003ms$
Znajdź ścieżkę, dojedź do pierwszego bitu, odczytaj
$T_{access} = T_{avg-seek} + T_{avg-rotation} + T_{avg-transfer} = 2,667ms + 4ms + 0,003ms = 6,67ms$
## ZAD 9 .
Rozważmy dysk 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ę. Procesor czyta z dysku całe sektory. Dysk sygnalizuje
dostępność danych zgłaszając przerwanie na każdy przeczytany bajt. Jaki procent czasu procesora będzie
zużywała obsługa wejścia-wyjścia, jeśli wykonanie procedury przerwania zajmuje 2.5µs? Należy zignorować
czas wyszukiwania ścieżki i sektora.
* Czas transferu:
$T_{avg\ transfer} = \frac{1}{96 \frac{sektory}{ścieżka}} * \frac{1}{360 RPM} \approx 0.00002893518min \approx 1.736 ms$

* Czas przerwań:
$512\frac{bajty}{sektor} * 2.5µs = 1.28ms$

* Jaki procent czasu będzie zajmowała obsługa wejścia/wyjścia:
$\frac{\text{czas przerwań}}{\text{czas transferu}} = \frac{1.28ms}{1.736ms} *100 = 73.7\%$

* Do systemu dodajemy kontroler DMA. Przerwanie będzie generowane tylko raz po wczytaniu sektora do pamięci. Jak zmieniła się zajętość procesora?
$\frac{\text{czas przerwań}}{\text{czas transferu}} = \frac{0.0025ms}{1.736ms} *100 = 0.144\%$

Do systemu dodajemy kontroler DMA. Przerwanie będzie generowane tylko raz po wczytaniu sektora do pamięci. Jak zmieniła się zajętość procesora?

Dodajemy kontroler DMA, przerwanie generowane jest tylko raz po wczytaniu sektora pamieci, Jak zmienila sie zajetosc procesora?
Procesor jest teraz mniej zajęty,
Bez kontrolera DMA, procesor używa zaprogramowanego wejścia-wyjścia, i jest w pełni zajęty przez całość trwania operacji wejścia, czy wyjścia, co uniemożliwia mu wykonywanie innych zadań.
Z DMA, procesor wykonuje transfer, potem wykonuje inne operacje w trakcie trwania transferu, po czym dostaje sygnał przerwania od kontrolki DMA.
$\frac{\text{czas przerwań}}{\text{czas transferu}} = \frac{0.0025ms}{1.736ms} *100 = 0.144\%$
## ZAD 10 .
W przeważającej większości systemów implementujących moduły DMA, procesor ma niższy
priorytet dostępu do pamięci głównej niż moduły DMA. Dlaczego?

DMA - direct memory access; gwarancja wykonywania transferów do pamięci.

Moduły DMA zazwyczaj mają wyższy priorytet dostępu do pamięci ogólnej, gdyż nie mają wystarczającej pamięci podręcznej, aby zapisywać dane. Procesor z kolei może sobie te dane zapisać.

Przykładem może być karta sieciowa, która wymaga regularnej możliwości transferu danych.

Dzięki temu modułowi procesor nie musi pośredniczyć w dostępie do pamięci.

DMA ma za zadanie odciążyć procesor główny od przesyłania danych (np. z urządzenia wejściowego do pamięci). Procesor może w tym czasie zająć się innymi działaniami, wykonując kod programu pobrany uprzednio z pamięci RAM do pamięci podręcznej.
///
Moduły DMA mają wyższy priorytet dostępu do pamięci ogólnej, ponieważ nie mają wystarczającej pamięci podręcznej, aby zapisywać dane.
Przykład: karta sieciowa. Jeśli nie miałaby możliwości regularnego transferu danych, mogłyby one zostać utracone.