###### tags: `ASK` # Raport do zadania opt-matmult ### 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: 64 KiB, 4-drożny (per rdzeń), rozmiar linii 64B * L3: 9 MiB , 12-drożny (współdzielony), rozmiar linii 64B Pamięć TLB: * L1d: 4KiB strony, 4-drożny, 64 wpisy * L2: 4KiB strony, 4-drożny, 64 wpisów Informacje o pamięciach podręcznych uzyskano na podstawie wydruku programu `x86info`, `lscpu`, `getconf`. Wyniki eksperymentów --- 1. Przeprowadzilem po kilkanaście testów dla każdego zaimplementowanego algorytmu mnożenia macierzy i zapisałem uśrednione wartości w tabeli poniżej. Informacje zodybłem używając instrukcji ``` ./matmult -p ipc -n X -v Y ``` Gdzie X jest wartością 64,128,256 lub 512, a Y wartością 0,1 lub 2. Cykle na iterację obliczyłem ze wzoru x - Liczba instrukcji. y - Liczba instrukcji na cykl z - bok sześcianu podniesiony do potęgi 3 (liczba iteracji) Cykle na iterację = $\frac{\frac{x}{y}}{z}$ Implementacja | N=64 Instrukcje na cykl |Instrukcje |Cykle na iterację|N=128 Instrukcje na cykl| Instrukcje |Cykle na iterację |N=256 Instrukcje na cykl|Instrukcje | Cykle na iterację|N=512 Instrukcje na cykl|Instrukcje |Cykle na iterację ---- | ----- | -------- | -------- |--- | --- | --- | --- | --- | --------------- | --- |------- |---- ijk | 2,9 | 2401054 | 3,158377 | 2,3 | 19039583 | 3,947296 | 1,3 | 151652845 | 6,953242 | 1,45 | 1210585918 | 6,220391691 kij | 3,1 | 2921177 | 3,594647 |2,8 | 23217369 | 3,953894 | 2,8 | 185141471 | 3,941176 | 2,9 | 1478758678 | 3,799176108 jki | 2,5 | 3183257 | 4,857265 |1,1 | 25314400 | 10,9735 | 0,7 | 201918481 | 17,19326 | 0,67 | 1612976122 | 17,93672925 ![](https://i.imgur.com/1Cojcg9.png) 2. Następnie wykonałem testy za pomocą instrukcji ``` ./matmult -p memory -n 512 -v X ``` Gdzie X jest wartością 0,1 lub 2. Implementacja ijk: ![](https://i.imgur.com/n27kdT3.png) Implementacja kij: ![](https://i.imgur.com/kL3lBKX.png) Implementacja jki: ![](https://i.imgur.com/kRUepWR.png) Są to jedynie przykładowe wyniki jakie mi wyszły, lecz po powtórzeniu tych testów i uśrednieniu wartości były one bardzo podobne do tych przykładowych. 3. Wykonałem również po kilkanaście testów dla N = 1024 dla bloków o długości kolejnych potęg liczby 2 (oczywiście implementacji «matmult3»). Wyniki przedstawiłem w poniższej tabelce. |Rozmiar Bloku| Uśredniony czas | | -------- | -------- | | 1 | 3,6 sek | | 2 | 2,8 sek | | 4 | 1,51 sek | | 8 | 1,16 sek | | 16 | 1,16 sek | | 32 | 1,64 sek | | 64 | 2,49 sek | | 128 | 2,78 sek | | 256 | 2,89 sek | | 512 | 2,91 sek | | 1024 | 3,58 sek | 4. Potem wykonałem kilkanaście pomiarów dla wersji blokowej i na ich podstawie stwrzyłem tabelę, którą zamiesciłem poniżej. | | Czas | L1 Data Cache miss ratio |L2 Data Cache miss ratio| L3 Cache miss ratio | Data TLB miss ratio | | -------- | -------- | ------------------- | ------------------- | ------------------- | ------------------ | | BLOCK * BLOCK tiled version | 1,16 sek | 26,3% | 9,45 % | 0,88 % | 0,019 % | 5. Przeprowzdziłem również eksperyment sprawdzający czasy implementacji zerowej («matmult0») dla wartości długości boku od N = 16 do N = 2048, wykonując test co N=16. Wyniki zamieściłem w pliku Dane.txt (dołączyłem go do repozytorium), ponieważ jest ich dosyć dużo. Wnioski --- * Czy uzyskane wyniki różnią się od tych uzyskanych na slajdzie? Róźnią się pod względem ilości cykli na iterację oraz dla N = 64 implementacja ijk jest lekko bardziej wydajniesza niż implementacja kij, lecz wykres wygląda niemal identycznie. * Z czego wynika rozbieżność między wynikami dla poszczególnych wersji mnożenia macierzy? Przede wszystkim ze sposobu implementacaji poszczególnych algorytmów. Każdy sposób mnożenia macierzy ma inną szansę na chybienie podczas wykonywania instrukcji. Wyniki trafień i chybień dla N = 512 można zobaczyć powyżej w wynikach eksperymentów. * Jaki wpływ ma rozmiar kafelka na wydajność «matmult3»?/Czy rozmiar kafelka ma znaczenie? Jak można zauważyć rozmiar bloku ma znaczenie na wydajność «matmult3». Dla bloków o rozmiarze 8/16 mnożenie odbędzie się w najszybszym czasie. Im rozmiar bloku bardziej odbiega od rozmiaru 8/16 tym wydajność zncząco spada. Po ustawieniu definicji wartości «A_OFFSET», «B_OFFSET», «C_OFFSET» na 0 możemy zauważyć lekki spadek wydajności. Wykonałem kilkanaście testów dla N = 1024 i uśredniony czas to 1,25 sek. Wydajność więc spadła o 100% - 1,16 sek / 1,25 sek = 7,2 % * Dla jakich wartości n obserwujesz znaczny spadek wydajności? Według danych z pliku Dane.txt zauważyłem mocny spadek wydajności dla n = $2^{x}$ oraz dla n = $2^{x} - 2^{x-2}$ . Podsumowanie --- Po wykonaniu kilkunastu pomiarów dla implementacji trzeciej (z rozmiarem bloku równym 16) stwierdzam, że wersja ta jest najlepsza bo działa znacznie szybciej niż poprzednie implementacje co jasno wynika z danych zamieszczonych wyżej (w porównaniu z pierwszą tabelą w tym wynikach eksperymentów). Niestety w tym przypadku kosztem jest mniejsza czytelność kodu.