---
# System prepended metadata

title: Raport do zadania opt-binsearch
tags: [ASK]

---

###### tags: `ASK`

# Raport do zadania opt-binsearch

### Autor: Piotr Stokłosa

Konfiguracja
---

Informacje o systemie:

 * Dystrybucja: Ubuntu 18.04.1
 * Jądro systemu: Linux 5.3.0
 * Kompilator: gcc 7.5.0
 * Procesor: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz (Coffee Lake)
 * Liczba rdzeni: 6

Pamięć podręczna:

 * L1d: 32 KiB, 8-drożny (per rdzeń), rozmiar linii 64B
 * L2: 256 KiB, 4-drożny (per rdzeń), rozmiar linii 64B
 * L3: 9 MiB , 12-drożny (współdzielony), rozmiar linii 64B

Pamięć TLB:

 * L1d: 4 KiB strony, 4-drożny, 64 wpisy
 * L2: 4 KiB + 2 MiB strony, 12-drożny, 1536 wpisów

Informacje o pamięciach podręcznych uzyskano na podstawie wydruku programu
`x86info`, `lscpu`, `getconf`.

Wyniki eksperymentów
---

Porównałem czasy obu implementacji wraz z ilością trafień i chybień w pamięć podręczną. Wyniki przedstawiłem w poniższej tabeli, na podstawie której wykonałem wykres znajdujący się pod tabelą.

Porównanie czasów i cache missów obu implementacji rozważając $n \in <10,25>$
|  N  |  Czas v0  |  Czas v1  | V0: Miss ratio L1 | Miss ratio L2 | Miss ratio L3 | Miss ratio TLB | V1: Miss ratio L1 | Miss ratio L2 | Miss ratio L3 | Miss ratio TLB |
|:---:|:---------:|:---------:|:-----------------:|:-------------:|:-------------:|:--------------:|:-----------------:| ------------- |:-------------:|:--------------:|
| 10  | 0.549301  |  0.71231  |       0.002       |    0.0026     |     0.003     |      0.0       |      0.0022       | 0.0032        |    0.0036     |      0.0       |
| 11  | 0.591601  | 0.780418  |      0.0044       |    0.0048     |    0.0052     |      0.0       |      0.0054       | 0.0064        |    0.0066     |      0.0       |
| 12  |  0.64138  | 0.862473  |       0.009       |    0.0088     |    0.0088     |      0.0       |       0.012       | 0.0124        |    0.0126     |      0.0       |
| 13  | 0.694204  |  0.93674  |      0.5498       |    0.0186     |    0.0182     |      0.0       |      0.1778       | 0.0238        |     0.023     |      0.0       |
| 14  | 0.848681  | 1.061663  |      20.534       |    0.0766     |    0.0648     |      0.0       |      4.6808       | 0.0766        |    0.0664     |      0.0       |
| 15  | 0.999505  | 1.194455  |      32.0084      |    3.9338     |     0.122     |      0.0       |      9.6962       | 1.0716        |     0.14      |      0.0       |
| 16  | 1.321632  | 1.388533  |      41.3106      |    38.1158    |     0.129     |      0.0       |      14.6258      | 8.295         |    0.1168     |      0.0       |
| 17  | 1.873946  | 1.663287  |      48.499       |    125.812    |    0.0532     |      0.0       |      19.2514      | 15.571        |    0.0678     |      0.0       |
| 18  | 2.405031  | 2.022898  |      55.172       |   187.7012    |    0.2866     |      0.0       |      23.4456      | 27.5314       |    0.2652     |      0.0       |
| 19  | 3.140495  |  2.47196  |      66.1204      |   215.5166    |    2.5674     |      0.0       |      27.2668      | 39.5888       |     1.416     |      0.0       |
| 20  | 3.812463  | 3.133371  |      72.5436      |   209.1498    |    14.7002    |      0.0       |      30.7246      | 52.592        |    4.6314     |      0.0       |
| 21  | 5.411926  | 4.283793  |      82.541       |   216.4466    |    57.0358    |      2.55      |      35.3952      | 65.69         |    11.7586    |     1.4106     |
| 22  | 7.891976  | 5.906443  |      91.3036      |    217.998    |   106.2094    |     7.8432     |      41.8124      | 80.0264       |    22.0342    |     4.979      |
| 23  | 10.058547 | 7.915053  |      95.4122      |   214.7496    |   128.9154    |    12.3956     |      48.246       | 96.9516       |    33.8526    |     8.836      |
| 24  | 12.410624 | 10.338867 |      98.1114      |    225.307    |    143.514    |    16.3512     |      54.3952      | 111.1754      |    47.789     |    12.5398     |
| 25  | 14.253311 | 12.196276 |     101.4766      |   240.5614    |    152.164    |    19.9936     |      60.4276      | 128.8364      |    55.3296    |    16.0264     |

Wykres przedstawia czasy obu implementacji binary search.

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



Porównałem również wartości IPC dla orygianlnego kodu oraz po zamianie kilku instrukcji miejscami (w przypadku dodawania) / przerzuceniu w inne miejsce pętli (w przypadku instrukcji warunkowej).

| N   | oryginalna kolejność | po przerzuceniu instrukcji warunkowej na koniec pętli | Po zamianie kolejnością dodawania |
| --- |:--------------------:| ----------------------------------------------------- |:---------------------------------:|
| 21  |        0.472         | 0.533                                                 |               0.492               |
| 22  |        0.361         | 0.413                                                 |               0.370               |
| 23  |        0.272         | 0.328                                                 |               0.285               |
| 24  |        0.222         | 0.261                                                 |               0.231               |


Następnie dodałem do implementacji binsearch1 funkcje «__builtin_expect» i «__builtin_prefetch».

Kod napisany za pomocą «__builtin_expect» i «__builtin_prefetch»:
```c=
bool binsearch1(T *arr, long size, T x) {

    long index = 0;
    T temp;

   do
   {

    size >>= 1;

    temp = arr[index];

    __builtin_prefetch (&arr[2*index + 1], 0, 1);
    __builtin_prefetch (&arr[2*index + 2], 0, 1);

    if (__builtin_expect((temp == x),0))
        return true;

    index <<= 1;
    index += 1;

    index += (temp < x);

  } while (size > 0);

  return false;
}
```
Tabela pomiżej przedstawia porównanie czasów implementacji binsearch1 po użyciu  «__builtin_expect» i «__builtin_prefetch» (wraz z ilością chybień w pamięć podręczną) z oryginalnym czasem binsearch1.

|  N  | Oryginalny czas | czas po użyciu  «__builtin_expect» i «__builtin_prefetch» | Miss ratio L1 | Miss ratio L2 | Miss ratio L3 | Miss ratio TLB |
|:---:|:---------------:|:---------------------------------------------------------:|:-------------:| ------------- | ------------- |:-------------- |
| 21  |    3.672598     |                         2.801822                          |    23.540%    | 58.360%       | 4.557%        | 2.442%         |
| 22  |    5.098410     |                         3.706259                          |    26.891%    | 68.040%       | 13.440%       | 4.127%         |
| 23  |    6.848917     |                         4.701354                          |    30.037%    | 78.266%       | 20.647%       | 5.681%         |
| 24  |    8.805575     |                         5.822148                          |    33.096%    | 87.586%       | 29.543%       | 7.092%         |

Po wykonaniu kilku testów dla n = 23 porównałem również branch misprediction ratio.

Średnia wartość dla oryginalnego binsearch1: 1.819%
dla binsearch1 po użyciu  «__builtin_expect» i «__builtin_prefetch»: 1.617%


Wnioski
---
* Czemu zmiana organizacji danych spowodowała przyspieszenie algorytmu wyszukiwania?

Zmiana organizacji danych spowodowała przyspieszenie algorytmu wyszukiwania, ponieważ zamiast "strzelać" w sam środek tablicy, przechodzimy ją "od początku". Powoduje to znaczne zmiejszenie ilości chybień w cache w początkowym stadium wyszukiwania (co w przypadku algorytmu o złożności logarytmicznej jest kluczowe). Porównanie dobrze widoczne jest w tabeli, którą umieściłem w wynikach eksperymentów. Dla przykładu dla N = 22, chybienia jakie widzimy dla implementacji binsearch0 są większe od tych dla implementacji binsearch1 o odpowiednio 2 razy (dla L1), 3 razy (dla L2) i nawet do 5 razy (dla L3)!

* Jak zmieniła się lokalność czasowa elementów przechowywanych w pamięci podręcznej?

Opisałem to już trochę pod poprzednim pytaniem. Dzięki temu, że przechodzimy tablicę od początku i tylko w jedną stronę, nie mamy tyle chybień, co w przypadku strzałów w środek tablicy.

* W jaki sposób zmiana kolejności instrukcji w ciele pętli zmienia IPC? 

Po zamianie instrukcji dodawania widzimy (dzięki tabeli w wynikach eksperymentów) lekki zwrost IPC. Większy natomiast wzrost widzimy po przerzuceniu instrukcji warunkowej na koniec pętli.

* Czy można to wytłumaczyć posługując się programem llvm-mca?

Po wywołaniu llvm-mca z flagą -timeline możemy zauważyć, że dzięki przerzuceniu instrukcji warunkowej
```c=
    if (temp == x)
        return true;
```
na koniec pętli
program charakteryzuje się większą przetwarzalnością potokową.
 
* Czy użycie instrukcji wbudowanych kompilatora «__builtin_expect» i «__builtin_prefetch» przynosi jakieś zyski? Jeśli ich użyjesz należy wytłumaczyć co robią.

Użycie «__builtin_expect» przynosi zyski, jeżeli zostaną mu podane dobrze przewidziane skoki.

«__builtin_prefetch» przynosi zyski poprzez zmniejszenie cache miss.

Szczegółowe definicje:

«__builtin_prefetch» is used to minimize cache-miss latency by moving data into a cache before it is accessed. You can insert calls to __builtin_prefetch into code for which you know addresses of data in memory that is likely to be accessed soon. If the target supports them, data prefetch instructions are generated. If the prefetch is done early enough before the access then the data will be in the cache by the time it is accessed. 

You may use __builtin_expect to provide the compiler with branch prediction information. In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform. However, there are applications in which this data is hard to collect.

Definicje wzięte ze strony: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html


Wersja z «__builtin_expect» i «__builtin_prefetch» jest znacznie wydajniesjza od oryginalnej implementacji na co wskazuje tabela znajdująca się w wynikach eksperymentów. Dzięki użyciu tych funkcji zmniejszyły się chybiena w pamięć podręczną co wyraźnie widać kiedy porównamy dwie tabele (z chybieniami binsearch1 oraz chybieniami w wersji z «__builtin_expect» i «__builtin_prefetch») oraz branch misprediction ratio, co również widać w wynikach eksperymentów.

Ostatnia wersja jest najlepsza, bo dzięki sprytniejszemu korzystaniu z cache'y więcej razy trafiamy w L1, L2 i w L3, co przekłada się na wydajność programu. Widać to wyraźnie na wykresie znajdującym się w wynikach eksperymentów. Podusmowując, implementacja binsearch1 jest bardziej wydajna dla dużych N, co jasno wynika z danych.