---
# System prepended metadata

title: 'Lista 12 (27.05.2021), grupa pwit'
tags: [pwit, ask21, ćwiczenia]

---

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



