Lista 12 (27.05.2021), grupa pwit

# Lista 12 (27.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 | X | | |Kacper Bajkiewicz | X | X | X | X | X | | | | |Bartłomiej Hildebrandt| X | X | X | X | X | | | | |Dominik Komła | X | X | X | X | X | | | | |Aleksandra Kosińska | X | X | X | X | X | | | | |Oleś Kulczewicz | X | X | X | X | X | | | | |Damian Lukas | X | X | X | X | | | | | |Michał Mikołajczyk | X | X | X | X | X | | | | |Mateusz Opala | X | X | X | X | X | | | | |Łukasz Orawiec | X | X | X | X | X | X | | | |Szymon Pielat |==X==| X | X | X | X | X | | | |Łukasz Pluta | X | X | X | X | X | | | | |Kamil Puchacz | X | X | X | X | X | X | | | |Magdalena Rzepka | X | X | X | X | X | X | | | |Cezary Stajszczyk | X | X | 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 | X | | | ::: ## Zadanie 1 :::info Autor: Szymon Pielat ::: ![](https://i.imgur.com/MEYElIb.png) **aliasing memory** - describes a situation in which a data location in memory can be accessed through different symbolic names in the program. Thus, modifying the data through one name implicitly modifies the values associated with all aliased names, which may not be expected by the programmer **restrict** - is a keyword that can be used in pointer declarations. By adding this type qualifier, a programmer hints to the compiler that for the lifetime of the pointer, only the pointer itself or a value directly derived from it (such as pointer + 1) will be used to access the object to which it points. jeżeli *xp, *yp wskazywało by na tą samą komórke w pamięci, i wywolalibysmy swap() np *xp == *yp == 3 to dostalibyśmy niepoprawny wynik *xp == *yp == 0 ```=c void swap(long *restrict xp, long *restrict yp) { *xp = *xp + *yp; /* x+y */ *yp = *xp - *yp; /* x+y-y = x */ *xp = *xp - *yp; /* x+y-x = y */ } ``` ## Zadanie 2 :::info Autor: Damian Lukas ::: Ile razy zostanie zawołana funkcja «my_strlen» w funkcji «my_index» i dlaczego? Usuń atrybut2 «noinline» funkcji «my_strlen». Czy zezwolenie kompilatorowi na przeprowadzenie **inliningu** pomogło? Dodaj atrybut «pure» do funkcji «my_strlen». Czemu tym razem kompilator był w stanie lepiej zoptymalizować funkcję «my_index»? Czym charakteryzują się **czyste funkcje**? ```c= __attribute__((noinline)) size_t my_strlen(const char *s) { size_t i = 0; while (*s++) i++; return i; } const char *my_index(const char *s, char v) { for (size_t i = 0; i < my_strlen(s); i++) if (s[i] == v) return &s[i]; return 0; } ``` **Inlining** Zamiast wywoływać funkcję bezpośrednio wklejamy jej kod w miejscu wywołania. **Czyste funkcje** Jest niezależna od zmiennych globalnych, wywołanie jej z takim samym argumentem zawsze daje taki sam wynik. The __attribute__ ((pure)) means that the function has no side effects and the value returned depends on the arguments and the state of global variables. Therefore it is safe for the optimizer to elide some calls to it, if the arguments are the same, and the caller did not do anything to change the state of the globals in between the calls. In computer programming, a pure function is a function that has the following properties: 1. The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams). 2. The function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams). Funkcja my_strlen w asm: ```scala= my_strlen: xorl %eax, %eax cmpb $0, (%rdi) je .L4 .L3: addq $1, %rax cmpb $0, (%rdi,%rax) jne .L3 ret .L4: ret ``` my_index z artybutem `__attribute__((noinline))`: ```scala= my_index: xorl %edx, %edx jmp .L8 .L10: leaq (%rdi,%rdx), %rax cmpb %sil, (%rdi,%rdx) je .L7 addq $1, %rdx .L8: call my_strlen cmpq %rdx, %rax ja .L10 xorl %eax, %eax .L7: ret ``` Funkcja ``my_strlen`` zostałnie wywołana ``min(k,length(s))``(gdzie `k` to `s[k]==v`) razy. Jest ona wywoływana przy każdym sprawdzeniu warunku. Jak usuniemy `__attribute__((noinline))`: ```scala= my_index: movzbl (%rdi), %ecx xorl %edx, %edx xorl %eax, %eax testb %cl, %cl je .L7 .L10: addq $1, %rax cmpb $0, (%rdi,%rax) jne .L10 cmpq %rax, %rdx jnb .L14 leaq (%rdi,%rdx), %rax cmpb %sil, (%rdi,%rdx) je .L7 addq $1, %rdx xorl %eax, %eax testb %cl, %cl jne .L10 .L7: ret .L14: xorl %eax, %eax ret ``` Teraz kod procedury `my_strlen` jest bezposrednio w funkcji, więc nie wywołujemy funkcji `my_strlen` tylko mamy pętle w funkcji my_index. Dodajemy pure : `__attribute__((noinline,pure))` ```c= my_index: call my_strlen addq %rdi, %rax jmp .L8 .L10: movq %rdi, %r8 addq $1, %rdi cmpb %sil, -1(%rdi) je .L7 .L8: cmpq %rax, %rdi jne .L10 xorl %r8d, %r8d .L7: movq %r8, %rax ret ``` Teraz procedura `call my_strlen` jest wywoływana tylko raz. ## Zadanie 3 :::info Autor: Kacper Bajkiewicz ::: **niezmiennik pętli** - własność prawdziwa przed i po zakończeniu każdej iteracji pętli > [name=Piotr Witkowski] Niezmiennik pętli. W i-tej iteracji zachodzi: > $\forall_{k, t.że k < i}. (a'[k] = 7*k + x'^2) \wedge x' = y' - z' \wedge y' = y \wedge z' = z$. Zmienna z primem --- zmienna po wykonaniu i-tej interacji. Zmienna bez prima --- wartość z poprzedniej iteracji. **zmienne indukcyjne** - zmienna której wartość jest zmieniana (zwiększana lub zmniejszana) o stałą w każdej iteracji pętli lub jest liniową funkcją innej zmiennej indukcyjnej **osłabienie** - optymalizacja wprowadzana przez kompilator, w wyniku której kosztowne operacje zostały zastąpione przez dające taki sam wynik ale tańsze inne operacje Zmienne indukcyjne: ```x``` (stała), ```j``` jako liniowa funkcja dwóch zmiennych indukcyjnych), ```i``` jako zmienna której wartość jest zmieniana stałą liczbę razy Niezmienniki pętli: $x = y - z$, $a[i] = 7*i + x*x$ ```c= void foobar(long a[], size_t n, long y, long z) { for (int i = 0; i < n; i++) { long x = y - z; long j = 7 * i; a[i] = j + x * x; } } ``` ``` foobar: testq %rsi, %rsi je .L1 subq %rcx, %rdx leaq (%rdi,%rsi,8), %rax imulq %rdx, %rdx .L3: movq %rdx, (%rdi) addq $8, %rdi addq $7, %rdx cmpq %rax, %rdi jne .L3 .L1: ret ``` Przed pętlę wyniesiono $x = y - z$ (bo nie potrzeba wykonywać tego n razy, skoro za każdym razem wynik tego obliczenia jest ten sam) i $x*x$ (skoro y - z jest niezmienne, to (y - z)*(y - z) = x*x też). Osłabiono $j = 7*i$ (nie ma potrzeby co iterację wykonywać tego mnożenia, skoro w i+1szej iteracji wartość j to tak naprawdę wartość w i-tej + 7) (zamiast mnożenia mamy tańsze dodawanie). Próba odtworzenia zoptymalizowanego kodu: ```c= void foobar(long a[], size_t n, long y, long z) { if (n == 0) return; z = y - z; z *= z; long end = a + 8*n; do { *a = z; a = a + 8; z = z + 7; } while (a != end); } ``` Trochę bardziej wysokopoziomowo: ```c= void foobar(long a[], size_t n, long y, long z) { if (n == 0) return; z = y - z; z *= z; for(long i = 0; i < n; i++){ a[i] = z + 7; z += 7; } } ``` ## Zadanie 4 :::info Autor: Bartosz Troszka ::: ![](https://i.imgur.com/URRDLGU.png) ```c= neigh: subq $1, %rdx // i = i-1 leaq -1(%rcx), %r8 // r8 = j-1 addq $1, %rcx // j = j+1 imulq %rsi, %rdx // i = i*n leaq (%rdx,%rsi,2), %rsi // n = i + 2n leaq (%rdx,%r8), %r9 // r9 = i + r8 = i + j - 1 addq %rcx, %rdx // i = i+j movq (%rdi,%rdx,8), %rax // rax = a[i] movq %rsi, %rdx // i = n subq %rcx, %rsi // n = n-j addq (%rdi,%r9,8), %rax // rax = a[r9] subq %r8, %rdx // i = i - r8 = i - (j-1) addq (%rdi,%rdx,8), %rax // rax += a[i] addq (%rdi,%rsi,8), %rax // rax += a[n] ret long neigh(long a[], long n, long i, long j) { i = i - 1; long temp = j - 1; j = j + 1; i = i * n; n = i + 2*n; // (i-1)*n + 2n = i*n + n = (i+1)*n long temp2 = i + temp; // (i-1)*n + j-1 i = i + j; // (i-1)*n + j+1 long res = a[i]; // (i-1)*n + j+1 // ur i = n; // (i+1)*n n = n - j; // (i+1)*n - (j+1) res += a[temp2] //ul i = i - temp; //(i+1)*n - (j-1) res += a[i]; //dl res += a[n]; //dr } ``` Wyrażenia policzone raz: `(i-1)*n` `(i+1)*n` `j-1` `j+1` Optymalizacja: ```c= long neigh(long a[], long n, long i, long j) { long inj = i*n + j; long ul = a[inj - n - 1]; long ur = a[inj - n + 1]; long dl = a[inj + n - 1]; long dr = a[inj + n + 1]; // long ul = a[(i-1)*n + (j-1)]; // long ur = a[(i-1)*n + (j+1)]; // long dl = a[(i+1)*n - (j-1)]; // long dr = a[(i+1)*n - (j+1)]; return ul + ur + dl + dr; } neigh: imulq %rsi, %rdx addq %rcx, %rdx movq %rdx, %rcx subq %rsi, %rcx addq %rdx, %rsi movq 8(%rdi,%rcx,8), %rax addq -8(%rdi,%rcx,8), %rax addq -8(%rdi,%rsi,8), %rax addq 8(%rdi,%rsi,8), %rax ret ``` ## Zadanie 5 :::info Autor: Bartłomiej Hildebrandt ::: > Na podstawie [1, §5.14.1] odpowiedz na następujące pytania. Do czego służą programy profilujące? Jakie informacje niesie ze sobą profil płaski i profil grafu wywołań? Czemu profilowanie programu wymaga zbudowania go ze specjalną opcją kompilatora -pg? Na czym polega zliczanie interwałowe? Jak przy pomocy programu profilującego zidentyfikowano w [1, §5.14.2] procedury, które należało zoptymalizować? Które optymalizacje przyniosły największy efekt? ### Do czego służą programy profilujące? **Profilowanie programu** obejmuje uruchomienie wersji programu, w której został włączony kod instrumentacji, aby określić, ile czasu wymagają różne części programu. Może to być bardzo przydatne do zidentyfikowania części programu (tzw. wąskich gardeł), na których powinniśmy się skupić w naszych działaniach optymalizacyjnych. ### Jakie informacje niesie ze sobą profil płaski i profil grafu wywołań? **profil płaski** - określa ile czasu procesora zostało zużyte na każdą z funkcji w programie **profil grafu wywołań** - oblicza liczbę wywołań każdej funkcji, z podziałem na kategorie według tego, która funkcja wykonuje wywołanie Obydwie informacje są przydatne. Czasy dają poczucie względnego znaczenia różnych funkcji w określaniu całkowitego czasu wykonywania. Informacje o wywołaniu pozwalają nam zrozumieć dynamiczne zachowanie programu. ### Czemu profilowanie programu wymaga zbudowania go ze specjalną opcją kompilatora -pg? Ze względu na to, że profilowanie programu wymaga trzech kroków: 1. Program musi zostać skompilowany i połączony z programem profilującym 2. Następnie program w wersji wykonywalnej jest uruchamiany 3. Następuje analiza programem profilującym ### Na czym polega zliczanie interwałowe? **zliczanie interwałowe** - jest to technika pomiaru czasu, w której skompilowany program utrzymuje licznik dla każdej funkcji, rejestrując czas spędzony na wykonywaniu tej funkcji. System operacyjny powoduje, że program jest przerywany w regularnych odstępach czasu (zazwyczaj w odstępach w zakresie od 1 do 10 ms). Następnie określa, jaką funkcję wykonywał program, gdy wystąpiło przerwanie i zwiększa licznik tej funkcji o zmierzony czas. ### Jak przy pomocy programu profilującego zidentyfikowano w [1, §5.14.2] procedury, które należało zoptymalizować? Jako przykład została podana aplikacja, która obejmuje kilka różnych zadań oraz struktur danych. Analizuje ona statystyki dokumentu tekstowego dotyczące występowania wybranych sekwencji słów o dowolnej długości. Tworzy on tabelą określającą ile razy każda sekwencja wystąpiła w tekście. Zostało przetestowane 7 wersji programu: ![](https://i.imgur.com/SMu11Sj.png) Każda procedura robi coś innego: - `Sort` - sortuje słowa - `List` - skanuje połączoną listę w poszukiwaniu pasującego słowa (słów) - `Lower` - konwertuje stringa do lowercase - ... Dzięki profilerowi, możemy łatwo zaobserwować, które części programu wymagają optymalizacji. ### Które optymalizacje przyniosły największy efekt? W 1 przypadku jest to procedura `Sort`, w kolejnych 4 przypadkach jest to procedura `List`, a w 5 przypadku jest to procedura `Strlen`, a w ostatnim wszystkie czasy są podobne. ## Zadanie 6 :::info Autor: Łukasz Orawiec ::: ```c= void nonsense(long a[], long k, long *dp, long *jp) { long e = a[2]; long g = a[3]; long m = a[4]; long h = k - 1; long f = g * h; long b = a[f]; long c = e * 8; *dp = m + c; *jp = b + 4; } ``` ```= nonsense: subq $1, %rsi imulq 24(%rdi), %rsi movq 16(%rdi), %r8 movq (%rdi,%rsi,8), %rax movq 32(%rdi), %rsi addq $4, %rax leaq (%rsi,%r8,8), %rsi movq %rsi, (%rdx) movq %rax, (%rcx) ret ``` <br/> ```graphviz digraph { node[shape="box" style=filled fillcolor=lightgrey] rdi rsi1 [label="rsi"] rdx rcx node [shape="box", style="rounded"] load1 [label="load\nmovq (%rdi,%rsi,8), %rax"] load2 [label="load"] load3 [label="load\nmovq 16(%rdi), %r8"] load4 [label="load\nmovq 32(%rdi), %rsi"] store1 [label="store"] store2 [label="store"] rsi1->sub->imul imul->load1->add->store1 [penwidth = 2] rdi->load1 rcx->store1 rdi->load2->imul [penwidth = 2] rdi->load3->lea->store2 rdi->load4->lea rdx->store2 } ``` ## Zadanie 7 :::info Autor: Wojciech Adamiec ::: :::info ![](https://i.imgur.com/hCtHgeo.png) ::: **Out of order** - W mikroprocesorach superskalarnych zdolność do zmiany wykonywania kolejności instrukcji, tak, aby jak najefektywniej wykorzystać dostępne jednostki wykonawcze (moc obliczeniową procesora) – by równolegle wykonywać jak najwięcej instrukcji maszynowych, minimalizując tym samym czas wykonywania programów. **Mikroarchitektura** - Opis sprzętowej implementacji procesora definiujący jego działanie. **Jednostka funkcyjna** - Functional units are a part of a CPU that performs the operations and calculations called for by the computer program. PL - Część procesora odpowiedzialna za wykonywanie poszczególnych mikro-instrukcji. ![](https://i.imgur.com/7K5ixfJ.png) ![](https://i.imgur.com/Upu88GJ.png) latency == czas trwania issue == cooldown * kod z polecenia: ```assembly= nonsense: subq [1] $1, %rsi imulq [2, 3] 24(%rdi), %rsi movq [4] 16(%rdi), %r8 movq [5] (%rdi,%rsi,8), %rax movq [6] 32(%rdi), %rsi addq [7] $4, %rax leaq [8] (%rsi,%r8,8), %rsi movq [9] %rsi, (%rdx) movq [10] %rax, (%rcx) ret ``` ![](https://i.imgur.com/ze8DJbM.png) Wykonanie zajmie 23 cykle. Load - 4 cykle Mul - 3 cykle Load - 4 cykle Load - 4 cykle Lea - 4 cykle Store - 4 cykle ![](https://i.imgur.com/pAHklNA.png) Druga wersja ---------- ![](https://i.imgur.com/7K5ixfJ.png) ![](https://i.imgur.com/pAHklNA.png) ```graphviz digraph { node[shape="box" style=filled fillcolor=lightgrey] rdi rsi1 [label="rsi"] rdx rcx node [shape="box", style="rounded"] load1 [label="load\nmovq (%rdi,%rsi,8), %rax"] load2 [label="load\n 24(%rdi)"] load3 [label="load\nmovq 16(%rdi), %r8"] load4 [label="load\nmovq 32(%rdi), %rsi"] store1 [label="store"] store2 [label="store"] rsi1->sub->mul mul->load1->add->store1 [penwidth = 2] rdi->load1 rcx->store1 rdi->load2->mul [penwidth = 2] rdi->load3->lea->store2 rdi->load4->lea rdx->store2 } ``` | Cykl | Etap 1 | Etap 2 | Etap 3 | Etap 4 | |:---- | --------------------- | ---------------- | ---------------- |:---------------- | | 1 | sub, load 24, load 32 | | | | | 2 | | load 24, load 32 | | | | 3 | | | load 24, load 32 | | | 4 | | | | load 24, load 32 | | 5 | mul, load 16 | | | | | 6 | | mul, load 16 | | | | 7 | | | mul, load 16 | | | 8 | load 8 | | | load 16 | | 9 | lea, store rdx | load 8 | | | | 10 | | store rdx | load 8 | | | 11 | | | store rdx | load 8 | | 12 | add | | | store rdx | | 13 | store rcx | | | | | 14 | | store rcx | | | | 15 | | | store rcx | | | 16 | | | | store rcx | ## Zadanie 8 :::info Autor: Michał Mikołajczyk ::: :::info ![](https://i.imgur.com/5RUE0E6.png) ::: **Wysłanie** - Dispatch means the sending of an instruction to a queue in preparation to be scheduled in an out-of-order processor. **Zatwierdzenie** - Retire means the instruction (microoperation) leaves the "Retirement Unit". It means that in Out-of-order CPU pipeline the instruction is finally executed and its results are correct and visible in the architectural state as if they execute in-order. **Przezywanie rejestrów** - Register renaming is used to eliminate false data dependencies arising from the reuse of registers by successive instructions that do not have any real data dependencies between them. ```c= void nonsense(long a[], long k, long *dp, long *jp) { long e = a[2]; long g = a[3]; long m = a[4]; long h = k - 1; long f = g * h; long b = a[f]; long c = e * 8; *dp = m + c; *jp = b + 4; } ``` ``` D - dispatched e - executing E - executed R - retired ``` ``` Timeline view: 01234567 Index 0123456789 [0,0] DeER . . . . subq $1, %rsi [0,1] DeeeeeeeeER . . imulq 24(%rdi), %rsi [0,2] DeeeeeE---R . . movq 16(%rdi), %r8 [0,3] .D=======eeeeeER . movq (%rdi,%rsi,8), %rax [0,4] .DeeeeeE-------R . movq 32(%rdi), %rsi [0,5] .D============eER. addq $4, %rax [0,6] .D=====eE-------R. leaq (%rsi,%r8,8), %rsi [0,7] . D======eE-----R. movq %rsi, (%rdx) [0,8] . D============eER movq %rax, (%rcx) [0,9] . DeeeeeeeE-----R retq ``` ``` Iterations: 1 Instructions: 10 Total Cycles: 18 Total uOps: 13 Dispatch Width: 4 uOps Per Cycle: 0.72 IPC: 0.56 Block RThroughput: 3.3 ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.