---
# System prepended metadata

title: Raport do zadania randwalk

---

# Raport do zadania randwalk

### Autor: Marcin Dąbrowski
### Numer indeksu: 315370

Konfiguracja
---

Informacje o systemie:

 * Dystrybucja: Debian 10
 * Jądro systemu: 4.19.0-9-amd64
 * Kompilator: gcc version 8.3.0 (Debian 8.3.0-6) 
 * Procesor: AMD FX-6300
 * Liczba rdzeni: 6

Pamięć podręczna:

 * L1d:  16 KiB, 4-drożny (per rdzeń), rozmiar linii 64B
 * L2: 2 MiB, 16-drożny (per 2 rdzenie), rozmiar linii 64B
 * L3: 8 MiB , 64-drożny (współdzielony), rozmiar linii 64B

Pamięć TLB:

 * L1d: 4KiB strony, 255-drożny, 48 wpisy
 * L2: 4KiB strony, 8-drożny, 1024 wpisów

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


## Wnioski

### Ile instrukcji maszynowych ma ciało pętli przed i po optymalizacji?
Przed optymalizacją: $52$
Po optymalizacji: $56$
Obliczone przy użyciu [Compiler explorer](https://godbolt.org/z/6PvoeG) (werjsa gcc: 8.3)
### Ile spośród nich to instrukcje warunkowe?
$9$  ($8$ x instrukcja `SETcc`, $1$ raz skok)

*(wcześniej $11$ x instrukcja skoku)

### Jak optymalizacja wpłynęła na IPC?
Optymalizacja miała znaczny wpływ na liczbę instrukcji wykonanych na cykl. Wzrosła ona o prawie 2,5 krotnie. Różnicę tę dobrze pokazuje wykres:
![](https://i.imgur.com/PvvqyL6.png)

Największy wpływ na poprawę IPC miało zamienienie  warunkowych skoków na instrukcje `SETcc` wykorzystujące zmienne logiczne.

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

#### Informacje:
##### 0 - oznacza instrukcję `i-=((d==0)&(i>0))`
##### 1 - oznacza instrukcję `i+=((d==1)&(i<n-1))`
##### 2 - oznacza instrukcję `j-=((d==2)&(j>0))`
##### 3 - oznacza instrukcję `j+=((d==3)&(j<n-1))`

#### Wykres przedstwiający różnice w IPC dla różnych ustawień instrukcji 0, 1, 2, 3:
![](https://i.imgur.com/N5YKL1C.png)

#### Porównanie wykresów chybień w L1 oraz w L2 dla wersji 1032 oraz 3120:
##### L1:
![](https://i.imgur.com/813oxQO.png)
##### L2:
![](https://i.imgur.com/4dwAxg1.png)

Najszybszy (z tych, które przebadałem) wariant ułożenia kolejnych instrukcji:
```c=
i+=((d==1)&(i<n-1));
i-=((d==0)&(i>0));
j+=((d==3)&(j<n-1));
j-=((d==2)&(j>0));
```

Bardzo zauważalny jest spadek w momencie, gdy instrukcje są ułożone następująco:
```c=
j+=((d==3)&(j<n-1));
i+=((d==1)&(i<n-1));
j-=((d==2)&(j>0));
i-=((d==0)&(i>0));
```

Na powyższych wykresach widać wyraźnie, że różnica nie ma swojego źródła w procencie chybień w pamięci podręczne poziomu 1 i 2. Niestety moja konfiguracja nie pozwala mi na wykonanie takiego wykresu, na którym porównałbym ze sobą wskaźniki TLB dla obu kolejności wykonywania instrukcji. 

Mimo, że nie jestem tego w stanie podeprzeć danymi (nie działa mi również opcja `-p branch`), uważam, że to różnica w "celności" przewidywania skoków jest najważniejszym czynnikiem powodującym rozbieżność w wartościach IPC dla wariantów 3120 oraz 1032, gdyż wszystkie pozostałe zdają się nie odbiegać od siebie. 

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

Pokazane przeze mnie wykresy zdają się pokazywać, że rozmiar ma wpływ na działanie programu. Szczególnie dobrze widać to na wykresach L1 oraz L2, gdzie widoczne jest, że gdy $n=7$ to zaczyna rosnąć liczba chybień w L1 (ponieważ jego rozmiar to $2^7 * 2^7 = 16384$). Kolejny znaczący wzrost zauważyć można gdy $n=12$. Jest to moment kiedy tablica przestaje się mieścić w całości w pamięci podręcznej drugiego poziomu. 

Oba te zjawiska wpływają na wydajność programu. Widać to na wykresie przedstawiającym porównanie liczników IPC dla `randwalk0` oraz `randwalk1`, gdy ta wartość dla wersji zoptymalizowanej zaczyna się zmniejszać gdy $n=12$. 

Nie powiedziałbym natomiast, że, dla danych, które byłem w stanie przetestować, wpływ ten jest duży. Różnice w wydajności (IPC) to raptem kilka punktów procentowych.








