---
# System prepended metadata

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

---

###### 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
![](https://i.imgur.com/x6fgVow.png)

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.

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

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).