---
title: Raport do zadania 4
tags: ASK
author: Mateusz Reis
---

# Raport do zadania 4

### Autor: Mateusz Reis
### Numer indeksu: 316276

Konfiguracja
---

Informacje o systemie:

Informacje o systemie:

* Dystrybucja: Debian
* Jądro systemu: 5.3.0-53-generic
* Kompilator: gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
* Procesor: AMD A8-6500
* Liczba rdzeni: 4

Pamięć podręczna:

* L1d: 16 KiB, 4-drożny (per rdzeń), rozmiar linii 64B
* L2: 2048 KiB, 16-drożny (per rdzeń), rozmiar linii 64B
* L3: brak , ?-drożny (współdzielony), rozmiar linii 64B

Pamięć TLB:

* L1d: 4KiB strony, w pelni asocjacyjny, 64 wpisy
* L2: 4KiB strony, 8-drożny, 1024 wpisów

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

Wyniki eksperymentów
---
Pomiary zostaly wykonane dla tablic o wymaiarch od 2^11 do 2^27
wraz ze stala liczba krokow rowna 2^20.
Ponizej zostala przedstawiona tabelka z wynikami IPC oraz czas w (s):

|--Tablica-|binsearch0|binsearch1|
|-|-|-|

|n|rozmiar pamieci|IPC|czas|IPC|czas|
|-|-|-|-|-|-|
|11|7 KiB|1.3012|0.0303003|1.3012| 0.03678
|12|15 KiB|1.2309|0.0344004|1.005| 0.0416502
|13|31 KiB|0.731|0.0613397|0.9473| 0.0513389
|14|64 KiB|0.6239|0.0767645|0.8273|0.0598848
|15|127 KiB|0.5469|0.0921443|0.7517|0.0692875
|16|255 KiB|0.5238|0.101674|0.6896| 0.0801838
|17|511 KiB|0.4612|0.121504|0.6215| 0.0947092
|18|1023 KiB|0.4277|0.13806|0.5514| 0.11169
|19|2047 KiB|0.2791|0.222997|0.4919| 0.144472
|20|4095 KiB|0.1342|0.485353|0.3996| 0.227758
|21|8191 KiB|0.0943|0.721927|0.2655| 0.328108
|22|16383 KiB|0.0768|0.926211|0.1927| 0.438795
|23|32767 KiB|0.0698|1.06239|0.1501| 0.552432
|24|65535 KiB|0.0658|1.17308|0.1242| 0.666932
|25|131071 KiB|0.0585|1.36937|0.1072| 0.79743
|26|262143 KiB|0.0523|1.58946|0.0927| 0.945394
|27|524287 KiB|0.0483|1.78797|0.0811| 1.11127

Na podstawie tabelki tworzymy wykres IPC/rozmiar tablicy

:::danger
binsearch0
:::
:::warning
binsearch1
:::

oraz czas/rozmiar tablicy

:::danger
binsearch0
:::
:::warning
binsearch1
:::

Wnioski
---
Rozwiazanie binsearch1 dziala zdecydowanie szybciej niz jego odpowiednik z numerem 0, poniewaz jego dostepy do pamieci sa duzo lepiej zoragnizowane, jak i sama funkcja wykonuje zdecydowanie mniej operacji.

>Dzieki zmianie organizacji danych mozemy szukac zdecydowanie szybciej
>(co byloby jeszcze bardziej widoczne przy wiekszej liczbie przeszukiwan)
>jest to spodowane tym ze gdy zaczynamy szukac elementu w tablicy posortowanej wczytujemy do cache srodek tablicy i pewna ilosc elementow o bliskich indeksach. Natepnie dla duzych tablic wyrzucamy wszystko co wczytalismy i wczytujemy nowe elementy. Uzywajac tablicy wzorowanej na drzewie wczytujemy poczatek tablicy i kolejne elementy. Dzieki temu ze nie cofamy sie w tablicy a elementy mniejsze i wieksze, w ktore celuje klasyczny binsearch, sa stosunkowo niedaleko od naszej aktualnej pozycji znajduja sie juz w pamieci, co pozwala nam uniknac wczytywania danych z wiekszej pamieci w kazdej iteracji petli.
-----
>Zmiana kolejnosci instrukcji w ciele petli zawartej w binsearch1 jest niemozliwa, poniewaz po takiej operacji nasze poszukiwanie pomijaloby pierwszy element a w przypadku gdy szukana wartosc nie wystepowala by w tablicy program konczylby sie bledem segmentation fault.
-----
>Uzycie __builtin_expect(long exp,long c) daje kompilatorowi informacje ze warunek exp==c jest bardziej prawdopodobny niz inne, pozwala to zakolejkowac instrukcje, ktore maja byc wykonane po spelnieniu warunku.
Jesli sprawdzamy warunek, ktory zachodzi bardzo czesto, pozwala to przyspieszyc wykonywanie instrukcji. Fukcja ta ustawia prawdopodobienstwo spelnienia warunku na 0.9. W moim rozwiazaniu nie udalo sie tego uzyc, poniewaz uzywam ifa, tylko raz w calej petli, ktorego nie sposob przewidziec.

>Uzycie __builtin_prefetch(*addr..) pozwala na zaladowanie danych do pamieci cache, zanim zostana one uzyte. Jesli uzyjemy tej funkcji np. przed wykonywaniem obliczen mozemy zaoszczedzic czas na pozniejszym odczycie wartosci, poniewaz nasze dane beda juz w cache kiedy skonczymy obliczenia. W moim rozwiazaniu znow nie udalo sie uzyc tego rozwiazania, poniewaz petla wykonuje jeden dostep do pamieci, wykonuje 3 razy dodawanie i raz mnozenie i konczy iteracje, tak wiec uzycie __builtin_prefetch nie daje poprawy wydajnosci.