# Raport do zadania matmult

### 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 `matmult` 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 z przedziału $[16,704]$.

### Oznaczenia:
* v0 - wersja ijk (matmult0)
* v1 - wersja kij (matmult1)
* v2 - wersja jki (matmult2)
* v3 - wersja używająca kafelkowania (matmult3)

### Ważne:
Musiałem pozbyć się wszystkich wyników dla L3, ponieważ dla mojej konfiguracji sprzętowej program PAPI nie udostępnie tego licznikia związanego z tym poziomem pamięci.

### Porównanie wydajności funkcji mnożących macierze

### Zmiana BLOCK_SIZE

##### BLOCK_SIZE = 4

##### BLOCK_SIZE = 8

##### BLOCK_SIZE = 16 (standardowe własności)

##### BLOCK_SIZE = 32

##### BLOCK_SIZE = 64

### Zmiana *_OFFSET(BLOCK_SIZE=16):

##### *_OFFSET = 0


##### *_OFFSET = 1

##### A_OFFSET = 16, B_OFFSET = 8, C_OFFSET = 4

##### *_OFFSET - wartości domyślne

### %miss dla różnych funkcji

##### matmult0

##### matmult1

##### matmult2

##### matmult3

Wnioski
---

#### Czy uzyskane wyniki różnią się od tych uzyskanych na slajdzie?

Wyniki są zgodne z przewidywaniami, natomiast różnią się sposobem ich zaprezentowania. Z powodu problemów technicznych postanowiłem pokazać wydajność poszczególnych funkcji używając opcji `-p ipc` w programie `matmult`, zamiast używania liczby cykli na jeden obrót wewnętrznej pętli. Uważam, że ten sposób prezentacji równie dobrze oddaje różnice pomiędzy podejściami do tego problemu.

Uzyskane wyniki pokazują jednoznacznie, że najbardziej optymalną metodą mnożenia macierzy jest tzw. kafelkowanie. Następną najbardziej wydajną jest wersja `kij`, za nią `ijk` i na samym końcu `jki`.

#### Z czego wynika rozbieżność między wynikami dla poszczególnych wersji mnożenia macierzy?

Rozbieżnosci pomiędzy wynikami spowodowane są różnicami w podejściu do odczytywania pamięci. Poruszanie się w pętli w obrębie wiersza w tablicy dwuwymiarowej jest bowiem 'tańsze' od tej samej operacji przeprowadzonej na kolumnie. Wynika to z faktu, że tablica dwuwymiarowa jest przechowywana w pamięci w porzadku row-major, zatem wiersz po wierszu. Odczytywanie kolejnych elementów z kolumny wymaga zatem wielu skoków (a zatem wielu ponownych dostępów do pamięci, które prawdopodobnie skończą się nietrafieniem), w odróznieniu do czytania z wiersza, gdzie kolejne elementy znajdują się zaraz po sobie, co zwiększa prawdopodobieństwo na to, że szukana komórka już znajduje się w cache'u.

Można w łatwy sposób stwierdzić który ze sposobów `matmult0`, `matmult1`, `matmult2` jest najbardziej optymalny ustalając w jaki sposób "przemieszcza się" on po macierzy. W każdym obrocie wewnętrznej pętli w `matmult0` odczytywany jest jeden nowy element z wiersza, jeden z kolumny, a jeden to stała pozycja (która tylko przy pierwszym wykonaniu pętli jest 'nowa', potem jest już w cache'u).

W `matmult1` w każdym obrocie wewnętrznej pętli odbywają sie dwa dostępy do wiersza, co pozwala domniemywać, że będzie to najszybszy algorytm.

Wersja `matmult2` za każdym razem dwukrotnie odwołuje się do elementu z kolumny, co z bardzo dużym prawdopodobieństwem generuje tzw. missy. Jest to zatem najmniej optymalne podejście.

Sytuacja wygląda inaczej w wersji `matmult3` (kafelkowanie). Ta metoda różni się od pozostałych trzech, ponieważ w każdym obrocie wewnętrznej pętli odwołuje się do komórki kafelka, który już (najprawdopodobniej) znajduje się w pamięci podręcznej. Docelowo metoda ta ma generować najwięcej trafień, co potwierdzają wyniki eksperymentów.

#### Jaki wpływ ma rozmiar kafelka na wydajność `matmult3`?
Rozmiar kafelka ma znaczny wpływ na wydajność `matmult3`. Wynika to z tego, że ta metoda polega na zapisywaniu całego kafelka w pamięci podręcznej. Gdy jego rozmiar rośnie, to przestaje się on w niej mieścić, co powoduje nadpisywanie w cache'u poprzednio zapisanych elementów tegoż kafelka, a w dalszym rozrachunku prowadzi do większej liczby chybień. Rozmiar ten nie może być jednak zbyt mały, gdyż wtedy ładowanie całego kafelka nie będzie już dużo bardziej wydajne od 'zwyczajnego' przejścia się po tablicy dwuwymiarowej tak jak w metodach `matmult0`, `matmult1`, `matmult2`.

Jak widać na wykresach największa wydajność dla `matmult3` osiągana jest, gdy BLOCK_SIZE=16. Gdy wynosi on 8, to wyniki są delikatnie gorsze. Dla wartości 4 zauważamy jeszcze większy spadek wydajności(1.7 do 1.4 instrukcji na cykl). Przy rozmiarze 32 można zauważyć, że wydajność zmniejsza się nieznacznie, natomiast dla BS=64 widać już jej znaczny spadek (1.7 do 1.2).

Według autorów pracy naukowej pt."[The Cache Performance and Optimizations of Blocked Algorithms](https://suif.stanford.edu/papers/lam-asplos91.pdf)", optymalnym rozmiarem kafelka zdaje się być $\sqrt C$, gdzie $C$ jest rozmiarem pamięci podręcznej w bajtach. W moim przypadku byłoby to 128 lecz wyniki jasno pokazują, że dla wyższych rozmiarów szybkość spada.

[Źródło](https://suif.stanford.edu/papers/lam-asplos91.pdf)

#### Dla jakich wartości $n$ obserwujesz znaczny spadek wydajności?
Najsłabsze wyniki osiągane są, gdy $n=512$, co zdaje się powtarzać w każdym z pomiarów. Dla `matmult3` spadki wydajności można zaobserwować dla $n=128*k$. Szczególnie dobrze widać to na wykresie prezentującym liczbę chybień w zależności od rozmiaru macierzy.

Spadki te mogą wynikać ze zjawiska o nazwie "self interference". Polega ono na tym, że dla pewnych wartości $n$ niektóre komórki tablicy zostają zmapowane do miejsc w pamięci podręcznej, gdzie znajduje się już jakiś element, który również chcemy przechowywać. Powoduje to nadpisanie tych elementów, a także wielu następnych (na przykład całego wiersza lub kafelka), ponieważ "self interference" jest zjawiskiem objawiającym się cyklicznie.

Wartości $n$ dla których możemy obserwować ten proces zależą od:
* rozmiaru linii
* drożności
* rozmiaru pamięci podręcznej

#### Czy rozmiar kafelka ma znaczenie?
Rozmiar kafelka ma znaczenie tylko dla `matmult3`, ponieważ pozostałe funkcje nie korzystają w żaden sposób z BLOCK_SIZE. Wpływ rozmiaru kafelka opisałem wyżej, odpowiadając na pytanie "Jak rozmiar kafelka wpływa na wydajność `matmult3`?".

#### Czy inny wybór wartości domyślnych `*_OFFSET` daje poprawę wydajności?
Nie znalazłem takich wartości offsetów, które poprawiłyby wydajność. Natomiast po ustawieniu ich wszystkich na 0 wydajność spada. Wynika to z faktu, że wszystkie 3 macierze mogą znajdować się w tym samym miejscu w pamięci, co prowadzi do konfliktów.