###### tags: `ASK`

# Raport do zadania opt-randwalk

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

Najpierw sprwdziłem skutki zamiany instrukcji warunkowych na instrukcje z użyciem operatorów logicznych. Wyniki przedstawiłem w tabelach poniżej oraz na wykresie zrobionym na podstawie wartości N i czasów z tych tabel. Testy wykonane dla t = 14 oraz s = 16.

randwalk0
| N | Czas | Branch misprediction ratio |
|:---:| -------- |:--------------------------:|
| 1 | 8.053672 | 21.330% |
| 2 | 7.983976 | 21.331% |
| 3 | 8.182764 | 21.330% |
| 4 | 8.153354 | 21.330% |
| 5 | 8.085408 | 21.331% |
| 6 | 8.016095 | 21.331% |
| 7 | 7.941456 | 21.330% |
| 8 | 8.020312 | 21.330% |
| 9 | 7.949940 | 21.331% |
| 10 | 7.932605 | 21.330% |
| 11 | 8.127629 | 21.330% |
| 12 | 7.959895 | 21.331% |
| 13 | 7.990303 | 21.330% |
| 14 | 7.988952 | 21.331% |
| 15 | 8.272947 | 21.330% |

randwalk1
| N | Czas | Branch misprediction ratio |
|:---:| -------- |:--------------------------:|
| 1 | 3.408502 | 0.003% |
| 2 | 3.400219 | 0.002% |
| 3 | 3.422301 | 0.002% |
| 4 | 3.370914 | 0.002% |
| 5 | 3.392439 | 0.002% |
| 6 | 3.417570 | 0.003% |
| 7 | 3.461794 | 0.002% |
| 8 | 3.354639 | 0.003% |
| 9 | 3.393111 | 0.002% |
| 10 | 3.460069 | 0.002% |
| 11 | 3.443107 | 0.003% |
| 12 | 3.428670 | 0.002% |
| 13 | 3.518907 | 0.002% |
| 14 | 3.668939 | 0.002% |
| 15 | 4.004049 | 0.002% |

Wykres na podstawie czasów obu implementacji

Następnie zmierzyłem wartości IPC dla obu implementacji randwalk dla t = 14 i t = 15 oraz obliczyłem wartości średnie. Wyniki przedstawiają tabele poniżej

Tabela dla implementacji randwalk0
| Rozmiar tablicy w n | Wartość IPC dla t = 14 | dla t = 15 |
|:-------------------:|:----------------------:|:----------:|
| 4 | 0.778 | 0.777 |
| 5 | 0.778 | 0.777 |
| 6 | 0.779 | 0.779 |
| 7 | 0.778 | 0.777 |
| 8 | 0.778 | 0.779 |

| Średnia | t = 14 | t = 15 |
| ------- | ------ | ------ |
| | 0.778 | 0.778 |

Tabela dla implementacji randwalk1
| N | Wartość IPC dla t = 14 | dla t = 15 |
|:---:|:----------------------:|:----------:|
| 4 | 3.546 | 3.544 |
| 5 | 3.546 | 3.539 |
| 6 | 3.527 | 3.536 |
| 7 | 3.522 | 3.524 |
| 8 | 3.540 | 3.529 |

| Średnia | t = 14 | t = 15 |
| ------- |:------:| ------ |
| | 3.5363 | 3.5344 |

Na koniec wykonałem test w podobnym czasie dla różnych kolejności instrukcji (czterech instrukcji, które dodałem). Oto wyniki:

| N | Bez zmiany (IPC) | W odwrotnej kolejności | Zamienione parami |
| --- |:----------------:|:----------------------:|:-----------------:|
| 4 | 3.546 | 3.784 | 3.806 |
| 5 | 3.546 | 3.784 | 3.806 |
| 6 | 3.527 | 3.800 | 3.806 |
| 7 | 3.522 | 3.772 | 3.804 |
| 8 | 3.540 | 3.768 | 3.804 |

Wnioski
---
* Ile instrukcji maszynowych ma ciało pętli przed i po optymalizacji?
Po wykonaniu
`objdump -d randwalk.o`
skopiowałem zawartość pętli randwalk0 i randwalk1 do plików v0 oraz v1. Po wykonaniu instrukcji
`wc -l v0 v1`
wyświetlił mi się wynik.


Czyli przed optymalizacją ciało pęli miało 47 instrukcji maszynowych, a po - 53.
* Ile spośród nich to instrukcje warunkowe?
v0 - 12
(z czego 9 to skoki, a 3 to pozostałe)
v1 - 11
(z czego 3 to skoki, a 8 to pozostałe)

* Jak optymalizacja wpłynęła na IPC?

Wartość IPC wzrosła prawie pięciokrotnie, co widać na tabelach w wynikach eksperymentów. Wynika z tego, że optymalizacja znacząco wpłynęła na IPC. Przykłada się to również na zwiększenie wydajności randwalk.

* Jak na IPC wpływa zmiana kolejności instrukcji w ciele pętli?

Jak widać w tabeli w wynikach eksperymentów, zmiana kolejności instrukcji w ciele pętli ma małe znaczenie patrząc na IPC. Jednak zawsze jest te kilka dziesiętnych instrukcji na cykl więcej, więc podczas optymalizacji stałej można się zastanowić w jakiej kolejności postawić kolejne instrukcje w pętli, aby porgram był bardziej wydajny.

* Czy rozmiar tablicy ma duży wpływ na działanie programu?

Patrząc na eksperymenty, które wykonałem, rozmiar tablicy nie ma dużego wpływu na działanie programu. Jedyne zwróciło moją uwagę to, że dla n = 15 program działa trochę wolniej choć nie jest to duża różnica. Od n = 16 program zwraca segmentation fault.

Ostatnia wersja jest najlepsza, bo dzięki zmianie instrukcji warunkowej na działania z użyciem operatorów logicznych został zmniejszony branch misprediction ratio( z 21% do prawie 0% co jest ogromną różnicą), co daje lepszą wydajność drugiej implementaci (randwalk1), co jasno wynika z danych (m. in z tabeli w wynikach eksperymentów).