# Raport do zadania transpose

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

Wyniki eksperymentów
---

### Metodologia
Każdy eksperyment przeprowadzany był w następujący sposób:
* Wykonaj program `transpose` 12 razy dla pewnego rozmiaru
* Odrzuć dwa najbardziej skrajne wyniki (najmniejszy i największy)
* Policz średnią arytmetyczną z pozostałych rekordów
* Zwróć wynik

Rozmiary były odpowiednio z przedziałów:
* $[4,4096]$ dla pomiarów wpływu rozmiaru kafelka na wydajność programu
* $[8,16384]$ przy mierzeniu czasu wykonwania `transpose` dla różnych rozmiarów macierzy.

### Wykresy

#### Wpływ rozmiaru kafelka na wydajność `transpose`

###### BLOCK = 4

###### BLOCK = 8

###### BLOCK = 16

###### BLOCK = 32

###### BLOCK = 64

###### BLOCK = 128

#### Wpływ rozmiaru macierzy na czas działania programu

##### Chybienia na przedziale $(0,4096]$
###### L1

###### L2

###### TLB

##### `transpose0`

###### Przedział $[0,4096]$

###### Przedział $(4096,8192]$

###### Przedział $(8192,12288]$

###### Przedział $(12288,16384]$

##### `transpose1`

###### Przedział $[0,4096]$

###### Przedział $(4096,8192]$

###### Przedział $(8192,12288]$!

###### Przedział $(12288,16384]$!

Wnioski
---

### Jaki wpływ na wydajność ma rozmiar kafelka?
Podobnie jak w przypadku zadania `matmult` rozmiar kafelka ma znaczny wpływ na wydajność programu. Kafelkowanie pozwala na zwiększenie lokalności programu, co z kolei bezpośrednio przekłada się na czas jego działania, zmniejszając go znacznie.

Stosując technikę kafelkowania należy uważnie dobierać rozmiary kafelków, gdyż źle dobrana wielkość może dopowadzić do znacznego pogorszenia wydajności.

W moim przypadku pomiary wykazują, że największa wydajność osiągana jest, gdy rozmiar kafelka to 16 lub 32. Gdy rozmiar ten wynosi 4, to wydajność jest już niższa, ponieważ wymagane jest więcej kosztownych dostępów do pamięci (bo częściej musimy załadofać kafelek). Wielkość kafelka nie może być też za duża, ponieważ wtedy przestaje się on mieścić w pamięci podręcznej i elementy z tego bloku zaczynają nadpisywać pozostałe. Wprowadza to konieczność częstszych dostępów do pamięci niższego poziomu, co zmniejsza znacznie wydajność programu. W moich eksperymentach można taki spadek zauważyć już dla wartości 64.

### Czy czas wykonania programu z różnymi rozmiarami macierzy identyfikuje rozmiary poszczególnych poziomów pamięci podręcznej?
Tak, można zidentyfikować rozmiary poszczególnych poziomów pamięci odczytując wykres. Można skorzystać ze zjawiska zwanego 'super-alignment'. Polega ono na tym, że jeśli zbiór danych na których pracujemy (working set), czyli w tym wypadku rozmiar macierzy, jest potęgą dwójki, bądź jej wielokrotnością, to danemu elementowi macierzy może zostać przypisany indeks (jednoznacznie identyfikujący zbiór w pamięci podręcznej) taki sam (modulo jakaś potęga dwójki) jak innemu elementowi, który już znajduje się w cache'u. Jeśli dojdzie do takiego zdarzenia, to powstanie konieczność nadpisania całego zbioru (setu) w pmięci podręcznej, co generuje bardzo duże koszty.

Korzystając z faktu, że owe indeksy przystają do siebie modulo jakaś potęga dwójki, oraz patrząc na wykresy zależności czasu wykonania programu `transpose` od rozmiaru macierzy, możemy zauważyć, że na owych wykresach pewne skoki "niewydajności" pojawiają się okresowo. Zauważalna jest również różnica w wysokości tych skoków. Możemy wyróżnić trzy rodzaje takich "górek" (na przykład spoglądając na wykres dla `transpose1` z przedziału $(12288,16384]$ ).

Według mnie istnieje zależność pomiędzy rodzajem "górki", a rozmiarem poszczególnych poziomów cache'u. Najmniejszy skos odpowiada L1, średni L2, a największy L3.