# Lista 12 (27 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 | X | X | | | 6
| Wojciech Bogucki | X | X | X | X | | | | | 5
| Michał Doros | X | X | X | X | X | X | X | X | 8
| Marko Golovko | | | | | | | | | 0
| Magdalena Jarecka | | | | | | | | | 0
| Szymon Jędras | X | X | X | X | X | X | | | 6
| Heorhii Karpenko | X | X |==X==| X | X | X | | | 6
| Szymon Kosakowski | X | X | X | X | | | | | 4
| Izabella Kozioł | | | | | | | | | 0
| Franciszek Malinka | X | X | X | X | X | X | X | | 7
| Filip Pazera | X | X | X | X | | | | | 4
| Franciszek Pindel | X | X | X | X | X | X | X | X | 8
| Kacper Puchalski | X | X | X | X | | | | | 4
| Kacper Solecki | X | X | X | X | X | X | | X | 7
| Andrzej Tkaczyk | X | X | X | X | X | | | | 5
| Łukasz Wasilewski | X | X | X | X | | | | | 4
| Vladyslav Yablonskyi | X | X | X | X | X | | | | 5
| Adam Zyzik | X | X | X | X | X | | | | 5
:::
## Zadanie 1
:::success
Autor: Szymon Kosakowski
:::
aliasing - kiedy kilka wskaźników wskazuje na to samo miejsce w pamięci.
restrict - na czas życia wskaźnika, tylko ten wskaźnik będzie służył do dostępu do wartośći na którą wskazuje
Kompilator nie może zooptymalizować bo *xp i *yp mogą wskazywać na to samo miejsce w pamięci. W takim wypadku swap i swap2 zwrócą inny wynik
```c=
void swap(long *xp, long *yp) {
*xp = *xp + *yp; /* x+y */
*yp = *xp - *yp; /* x+y-y = x */
*xp = *xp - *yp; /* x+y-x = y */
}
```
```
swap:
movq (%rsi), %rax
addq (%rdi), %rax
movq %rax, (%rdi)
subq (%rsi), %rax
movq %rax, (%rsi)
subq %rax, (%rdi)
ret
```
---
```c=
void swap_res(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 */
}
```
```
swap_res:
movq (%rsi), %rax
movq (%rdi), %rdx
movq %rax, (%rdi)
movq %rdx, (%rsi)
ret
```
---
```c=
void swap2(long *xp, long *yp) {
long x = *xp, y = *yp;
x = x + y, y = x - y, x = x - y;
*xp = x, *yp = y;
}
```
```
swap2:
movq (%rdi), %rax
movq (%rsi), %rdx
movq %rdx, (%rdi)
movq %rax, (%rsi)
ret
```
## Zadanie 2
:::success
Autor: Wojciech Bogucki
:::
**Inlining**
Zamiast wywoływać funkcję bezpośrednio wklejamy jej kod w miejscu wywołania.
---
\_\_attribute__ (pure) oznacza, że funkcja nie ma skutków ubocznych, a zwracana wartość zależy od argumentów i stanu zmiennych globalnych.
**Czyste funkcje**
W programowaniu czysta funkcja to funkcja, która ma następujące właściwości:
1. Wartości zwracane przez funkcję są identyczne dla identycznych argumentów (brak zmian z lokalnymi zmiennymi statycznymi, zmiennymi nielokalnymi, zmiennymi argumentami odwołań lub strumieniami wejściowymi).
2. Użycie funkcji nie ma skutków ubocznych (brak mutacji lokalnych zmiennych statycznych, zmiennych nielokalnych, zmiennych argumentów referencyjnych lub strumieni wejścia / wyjścia).
---
Treść zadania:
```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;
}
```
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.
> [name=Franciszek Malinka] Mam bardziej pytanie niż uwagę. Czemu sam atrybut "pure" nie załatwia sprawy? Tj. czemu kompilator mimo tego, że funkcja jest czysta, "inlajnuje" ją w taki sposób, jak gdyby nie była pure? Nie mógłby jej mądrzej inlajnować?
## Zadanie 3
:::danger
Autor: Łukasz Wasilewski
:::
Wydruk z GodBolta:
```asm=
foobar:
test rsi, rsi
je .L1
sub rdx, rcx #x = y-z
lea rax, [rdi+rsi*8]#wyznaczenie końca tabeli
imul rdx, rdx#x^2
.L3:
mov QWORD PTR [rdi], rdx
add rdi, 8
add rdx, 7
cmp rdi, rax
jne .L3
.L1:
ret
```
```c=
void foobar(long a[], size_t n, long y, long z){
if (n == 0) return;
long x = y-z;
long x_kwadrat = x*x;
long *end = a + n;
do {
*a = x_kwadrat;
a++;
x_kwadrat+=7;
} while (a != end);
}
```
Niezmienniki pętli: to wartości które nie zmieniają się podczas wykonania pętli, czyli tutaj x i x^2. Są wykonane przed pętlą.
Zmienne indukcyjne to zmienne, które z każdym wykonaniem pętli rosną lub maleją o stałą wartość. Tutaj są to i oraz j.
Strength reduction: Zastąpienie przez kompilator pewnych operacji szybszymi np zastąpienie mnożenia dodawaniem, lub wyliczenie niezmienników tylko raz. Tutaj są to zastąpienie j=7*i; a[i]=j+x * x przez
```
movq rdx,(rdi)
add $8,rdi
add $7,rdx i wyliczenie niezmienników.
```
```
// i = rdx, j = rsi
j = 7 * i;
// osłabiona:
j = (i << 3) - i;
```
## Zadanie 4
:::success
Autor: Filip Pazera
:::
**eliminacja wspólnych podwyrażeń** - technika polegająca na obliczaniu wspólnych podwyrażeń tylko raz a następnie wykorzystywaniu wyniku wielokrotnie.
```=
neigh:
subq $1, %rdx
leaq -1(%rcx), %r8
addq $1, %rcx
imulq %rsi, %rdx
leaq (%rdx,%rsi,2), %rsi
leaq (%rdx,%r8), %r9
addq %rcx, %rdx
movq (%rdi,%rdx,8), %rax
movq %rsi, %rdx
subq %rcx, %rsi
addq (%rdi,%r9,8), %rax
subq %r8, %rdx
addq (%rdi,%rdx,8), %rax
addq (%rdi,%rsi,8), %rax
ret
```
Wersja odtworzona z powyższego kodu:
```c=
long neigh(long a[], long n, long i, long j) {
long jp1 = j + 1;
long jm1 = j - 1;
long i_minus = (i - 1) * n;
long i_plus = i_minus + 2 * n; // (i + 1) * n
return a[i_minus + jm1] + a[i_minus + jp1]
+ a[i_plus - jp1] + a[i_plus - jm1];
}
```
Wyrażenia obliczone tylko raz: `j-1`, `j+1`, `(i-1)*n`, `(i+1)*n`.
W celu lepszego zoptymalizowania kodu zauważamy, że podwyrażenie `(i + 1) * n` występuje jedynie jako część większego podwyrażenia `(i + 1) * n + j`, a `(i - 1) * n` - część `(i - 1) * n - j`.
```c=
long neigh(long a[], long n, long i, long j) {
long u = (i + 1) * n + j;
long d = (i - 1) * n - j;
long ul = a[u - 1];
long ur = a[u + 1];
long dl = a[d + 1];
long dr = a[d - 1];
return ul + ur + dl + dr;
}
```
Instrukcje wygenerowane z powyższego kodu:
```=
neigh:
addq $1, %rdx
imulq %rsi, %rdx
addq %rsi, %rsi
leaq (%rdx,%rcx), %r8
subq %rsi, %rdx
subq %rcx, %rdx
movq 8(%rdi,%r8,8), %rax
addq -8(%rdi,%r8,8), %rax
addq 8(%rdi,%rdx,8), %rax
addq -8(%rdi,%rdx,8), %rax
ret
```
## Zadanie 5
:::success
Autor: Szymon Jędras
:::
**programy profilujące** - programy służące do interpretowania danych będących wynikiem ubocznym programu skompilowanym z flagą `-pg`.
**profil płaski** - mówi ile czasu program spędza w każdej funkcji jako absolutna wartość.
**profil grafu wywołań** - pokazuje historię wywołań.
**zliczanie interwałowe** - jest to sposób liczenia czasu spędzonego w odpowiednich funkcjach. Co pewien interwał (1.0 do 10.0 ms) system przerywa wykonywanie programu i sprawdza w jakiej funkcji się znajduje.
#### Jakie informacje niesie ze sobą profil płaski i profil grafu wywołań?
profil płaski:
procent czasu jaki program spędził wykonując daną funkcję,
czas spędzony w tej funkcji albo funkcji powyżej,
czas spędzony w tej funkcji,
liczba wywołań funkcji,
czas spędzony w danej funkcji podzielony przez liczba wywołań,
czas spędzony w danej funkcji albo funkcjach pochodnych podzielony przez liczba wywołań.
profil grafu wywołań:
procent czasu spędzonego w tej funkcji (wlicza to funkcje wywołane przez daną funkcję)
czas spędzony w tej funkcji
liczba wywołań funkcji
#### Czemu profilowanie programu wymaga zbudowania go ze specjalną opcją kompilatora -pg?
Ta flaga powoduje, że każde wywołanie funkcji woła funkcję `mcount`, która powoduje zapisanie informacji użytych później do profilowania.
#### Jak przy pomocy programu profilującego zidentyfikowano w [1, §5.14.2] procedury, które należało zoptymalizować?
Program profilujący dawał nam informacje ile czasu nasz program spędzał na konkretnym etapie programu.
#### Które optymalizacje przyniosły największy efekt?
1. Zmienienie algorytmu sortującego
2. Polepszenie algorytmu hashującego
3. Zmienienie algorytmu przeszukującego listę z rekurencyjnego na iteracyjny (2)
4. Zwiększenie tablicy
5. Zmienienie algorytmu zmieniającego duże litery na małe litery
## Zadanie 6
:::success
Autor: Kacper Solecki
:::
```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;
}
```
**ścieżka krytyczna** - zajmująca najwięcej czasu ścieżka zależności między danymi, dająca ograniczenie dolne na czas wykonywania kodu.
```=
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
```
```graphviz
digraph G {
node [shape = rectangle, style = filled, fillcolor = darkslategray1]
load [fillcolor = darkturquoise]
store [fillcolor = white]
mul
add
sub
lea
load2 [label = "load", fillcolor = darkturquoise]
load3 [label = "load", fillcolor = darkturquoise]
load4 [label = "load", fillcolor = darkturquoise]
store2 [label = "store", fillcolor = white]
{rank = same; store;store2;lea;add}
node [shape = box, style = filled, fillcolor = gray]
rsi [label = "%rsi"]
rdi [label = "%rdi"]
rdx [label = "%rdx"]
rcx [label = "%rcx"]
rsi2 [label = "%rsi"]
rax2 [label = "%rax"]
r82 [label = "%r8"]
{rank = same; rsi, rdi, rdx, rcx}
{rank = same; rsi2, rax2, r82}
rsi -> sub
sub -> mul
rdi -> load [color = red]
rdi -> load2
load -> mul [color = red]
load2 -> r82
mul -> load3 [color = red]
rdi -> load3
rdi -> load4
load3 -> add [color = red]
load2 -> lea
load4 -> lea
lea -> rsi2
lea -> store
rdx -> store
add -> store2 [color = red]
rcx -> store2
add -> rax2
}
```
Na czerwono zaznaczona jest ścieżka krytyczna.
Load latency = 4
Store latency = 4
**mikro-operacje** - elementarne operacje, które mogą być przetworzone przez jednostkę funkcyjną.
Operacja
```
imulq 24(%rdi), %rsi
```
Zostanie rozłożona na mikro-instrukcje, ponieważ musi zarówno wczytać dane z pamięci, jak i wykonać operację arytmetyczną - nie ma jednostki funkcyjnej, która robi obie te rzeczy
## Zadanie 7
:::success
Autor: Michał Doros
:::
**out-of-order** - wykonywanie instrukcji “do przodu”, niekoniecznie zgodnie z kolejnością. Procesor niekoniecznie wykonuje instrukcje w sekwencyjnej kolejności, tak jak my sobie to wyobrażamy w naszym modelu. Mimo to procesor gwarantuje, że niezależnie od tego w jakiej kolejności wykona instrukcje, to rezultat działania naszego kodu będzie identyczny z tym, jaki byśmy otrzymali, gdyby wykonywał je sekwencyjnie.
**mikroarchitektura** - opis sprzętowej implementacji procesora, określa elementy procesora takie jak bloki funkcjonalne i jednostki wykonawcze oraz połączenia między nimi
> cytat z 5.7: “the underlying system design by which a processor executes instructions.”
**jednostki funkcyjne** części procesora wyspecjalizowane do wykonywania konkretnego rodzaju operacji
| T- | Stage 1 | Stage 2 | Stage 3 | Stage 4 | Stage 5 |
| --- | ---------------------------------------------- | -------------------------------- | ------------------------------- | -------------------------------- | -------------------------------- |
| 1 | rsi -= 1, load 24(rdi), load 16(rdi) | | | | |
| 2 | | load 24(rdi), load 16(rdi) | | | |
| 3 | | | load 24(rdi), load 16(rdi) | | |
| 4 | | | | load 24(rdi), load 16(rdi) | |
| 5 | | | | | load 24(rdi), load 16(rdi) |
| 6 | mulq rdi, rsi | | | | |
| 7 | | mulq rdi, rsi | | | |
| 8 | | | mulq rdi, rsi | | |
| 9 | load (rdi, rsi, 8), load 32(rdi) | | | | |
| 10 | | load (rdi, rsi, 8), load 32(rdi) | | | |
| 11 | | | load (rdi, rsi, 8),load 32(rdi) | | |
| 12 | | | | load (rdi, rsi, 8), load 32(rdi) | |
| 13 | | | | | load (rdi, rsi, 8), load 32(rdi) |
| 14 | rax += 4, lea (rsi, r8, 8), oblicz adres (rcx) | | | | |
| 15 | oblicz adres (rdx), store rax | | | | |
| 16 | store rsi | store rax | | | |
| 17 | | store rsi | store rax | | |
| 18 | | | store rsi | store rax | |
| 19 | | | | store rsi | |
19 instrukcji + dispatch przed rozpoczęciem + retirement po zakończneiu
## Zadanie 8
:::success
Autor: Franciszek Pindel
:::
> Posługując się programem llvm-mca (ang. machine code analyzer) wbudowanym w Compiler Explorer przedstaw symulację pojedynczego wywołania funkcji «nonsense». Do parametrów programu dodaj: «-mcpu=haswell -timeline -iterations=1». Na diagramie Timeline view wskaż punkty **wysłania** (ang. dispatch), **wykonania** i **zatwierdzenia** (ang. retire) instrukcji. Ile czasu zajmuje wykonanie funkcji według symulatora? Wyjaśnij dokładnie z czego wynikają przestoje w przetwarzaniu instrukcji? Na którym z rejestrów procesor użył techniki **przezywania rejestrów** (ang. register renaming)?
* **wysłanie** - moment w którym funkcja została zdekodowana, rozdzielona na mikro-operacje i czeka na wysłanie do odpowiednich jednostek funkcyjnych
* **wykonanie** - instrukcja została wykonana przez jednostki funkcyjne
* **zatwierdzenie** - wynik wykonania instrukcji może zostać zapisanym do rejestrów (np. byliśmy w branchu i przewidzenie skoku okazało się poprawne)
* **przezywanie rejestrów** - rejestry są modyfikowane dopiero po zatwierdzeniu. Przekazywanie rejestrów jest techniką pozwalającą na komunikację pomiędzy jednostkami pamięci bez konieczności pobierania potrzebnej wartości z rejestru. Najłatwiej to pokazać na przykładzie: załóżmy że są wykonywane dwie instrukcje:
```
movq $3, %rax
addq $4, %rax
```
Ponieważ `movq` modyfikuje rejestr `%rax`, to w specjalnej tabeli zostanie utworzona para `(tag, rejestr)`, np:
```
(11, %rax)
```
skojarzy tag `11` z rejestrem `%rax`
Gdy `addq` będzie dekodowana, to jako operand otrzyma tag odpowiadający rejestrowi do którego się odnosi, czyli `11`
Gdy `movq` się wykona, wyprodukuje parę `(3, 11)` zawierającą wartość rejestu i odpowiadający mu tag, teraz może się wykonać `addq` pobierając wartość z odpowiadającego tagu
W ten sposób dane przepływają bez udziału rejestrów
`D` - instrukcja została wysłana
`e` - instrukcja się wykonuje
`E` - instrukcja została wykonana
`R` - instrukcja została zatwierdzona
`=` - instrukcja wysłana, czeka na wykonanie
`-` - instrukcja wykonana, czeka na zatwierdzenie
```
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
```
Licząc do momentu wykonania ostatniej instrukcji wykonanie trwało 16 cykli
Przestoje w wykonaniu instrukcji wynikają z tego, że instrukcje czekają na dane, które jeszcze nie zostały obliczone (w trakcie prezentacji omówię szczegółowo każdą z instrukcji)
Przezywanie rejestrów odbyło się dla rejestru `%rsi`, `%r8`, `%rax` (zauważmy, że w momencie wykonywania instrukcji `movq (%rdi,%rsi,8), %rax` teoretycznie wartość `%rsi` została zmieniona przez kolejną instrukcję, ale nie stało się tak dzięki przezywaniu)
Sign in with Wallet
Connect another wallet