# Raport do zadania texture

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

### Ważne:
Wszystkie eksperymenty przeprowadzone są 12-krotnie z takim samym ziarnem: 0xFEEDC0DE. Następnie odrzucane są dwa skrajne wyniki, a z pozostałych liczona jest średnia arytmetyczna.

### Wnioski

#### Czemu zmiana organizacji danych spowodowała przyspieszenie?
Cała tekstura jest teraz przechowywana w postaci kafelków, które są w pamięci umieszczone po sobie. Aby odwołać się do pewnego elementu o współrzędnych $(x,y)$ należy najpierw obliczyć numer kafelka, w którym ten element się znajduje. Numer ten mnożę razy $(2^k)^2$, by przesunąć się o liczbę elementów, które były w poprzednich kafelkach. Następnie liczę indeks tego szukanego elementu w kafelku.

Takie rozwiązanie pozwala zdecydowanie poprawić lokalność algorytmu, co jest główną przyczyną jego przespieszenia. Konieczność załadowania wielu elementów tablicy do pamięci podręcznej zachodzi zdecydowanie rzadziej niż w niezoptymalizowanej wersji.

#### Czy translacja adresów ma zauważalny wpływ na wydajność przeglądania tekstury?
Tak, translacja ma zauważalny wpływ. Szczególnie widoczne jest to dla domyślnego rozmiaru macierzy ($8192$). Wtedy wariant `index0` jest odrobinę szybszy od (w teorii) optymalniejszego `index1`. Jednak po zwiększeniu rozmiaru dwukrotnie `index1` wykonuje się prawie dwa razy szybciej od drugiej wersji. Pokazuje to, że dla pewnych rozmiarów danych wprowadzanie takiej optymalizacji nie gwarantuje poprawy wydajności, wręcz przeciwnie, może ją zmniejszyć (mimo tego, że jest mniej chybień w pamięć podręczną). Optymalizacja przynosi natomiast bardzo znaczne zyski, gdy rozmiar danych wzrasta.

#### Jaki jest optymalny rozmiar kafla?

W moim rozumieniu rozmiar optymalny to taki, który powoduje najmniej chybień w pamięci podręcznej. Zatem:

W przypadku symulacji rozmiar $2^6$ był najbardziej optymalnym (spomiędzy ${1 .. 12}$).

Dla mojej konfiguracji wyniki są następujące (rozmiar kafelka == log(rozmiar kafelka)):
### L1:

### L2:

Wykresy pokazują jasno, że najbardziej optymalnym rozmiarem kafelka jest $2^8$. Jest tak, ponieważ większe kafelki przestają mieścić się w pamięci L1 i powodują chybienia.

## Dalsze obliczenia będą wykonywane z szerokością kafelka ustaloną na $2^8$

#### Czy zoptymalizowana wersja wykonuje więcej instrukcji na jeden element?

##### Wyniki dla $N=16384$ (rozmiar macierzy)

#### > Total instructions:
`index0`: $826263870$
`index1`: $2343204587$

Można zauważyć, że wersja zoptymalizowana wykonuje zdecydowanie więcej instrukcji na element niż wersja niezoptymalizowana. Mimo to program jest w stanie wykonać się prawie dwukrotnie szybciej ($1.037965s$ do $0.516235s$), ponieważ instrukcje te są mniej kosztowne (nie są bowiem dostępami do pamięci spowodowanymi chybieniami, a prostymi instrukcjami arytmetycznymi).

## Jak zmieniło się IPC?

##### Wyniki dla $N=16384$ (rozmiar macierzy)

#### > Instructions per cycle:
`index0`: $0.210$
`index1`: $0.401$

Liczba wykonanych instrukcji na cykl wzrosła. Powodem tego zjawiska jest to, że instrukcje wykonywane w wersji zoptymalizowanej są średnio dużo mniej kosztowne niż te w niezoptymalizowanej i mimo, że jest ich więcej, to procesor jest w stanie wykonać ich więcej w takim samym czasie.