###### tags: `ASK` # Raport do zadania opt-transpose ### 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: 256 KiB, 4-drożny (per rdzeń), rozmiar linii 64B * L3: 9 MiB , 12-drożny (współdzielony), rozmiar linii 64B Pamięć TLB: * L1d: 4 KiB strony, 4-drożny, 64 wpisy * L2: 4 KiB + 2 MiB strony, 12-drożny, 1536 wpisów Informacje o pamięciach podręcznych uzyskano na podstawie wydruku programu `x86info`, `lscpu`, `getconf`. Wyniki eksperymentów --- 1. Wykonałem po kilkanaście testów dla każdego rozmiaru Bloku od 1 do 2048 ($2^{0}$,$2^{1}$, ... ,$2^{11}$) dla rozmiaru macierzy N = 16384. Wyniki uśrednione przedstawiłem poniżej w tabeli. | Rozmiar Bloku | Czas | L1 Data Cache miss ratio | L2 Data Cache miss ratio | L3 Cache miss ratio | Data TLB miss ratio| | -------- | -------- | --- | --- | --- | --- | | 1 | 7,9 sek | 103% | 240% | 106% | 50% | | 2 | 4,2 sek | 43% | 114% | 51% | 20,5% | | 4 | 2,18 sek | 22,6% | 56,7% | 27% | 10,5% | | 8 | 1,1 sek | 14,5% | 37% | 17,7% | 5,7% | | 16 | 2,18 sek | 41,4% | 135% | 24,5% | 3,3% | | 32 | 1,72 sek | 53,4% | 137% | 17% | 1,8% | | 64 | 1,74 sek | 53,3% | 134% | 13,5% | 1% | | 128 | 2,15 sek | 53,7% | 126% | 38% | 0,7% | | 256 | 7 sek | 53,4% | 106% | 102% | 0,4% | | 512 | 7,5 sek | 53,3% | 104% | 104% | 0,3% | | 1024 | 7,6 sek | 53,2% | 104% | 104% | 0,2% | | 2048 | 7,8 sek | 103% | 160% | 104% | 50% | 2. Wykonałem również testy dla różnych wartości N odpowiednio dla rozmiaru bloku 2,8,64. Dane przedstawia poniższy wykres. ![](https://i.imgur.com/aRGFVpu.png) Tabela na podstawie której został wykonany wykres: |N |Czasy: Blok = 2|Blok = 8 | Blok = 64 | |---|---|---|---| |64 |0.000006 |0.000005 |0.00001 | |128 |0.000036 |0.000016 |0.000035| |192 |0.000117 |0.000055 |0.000065| |256 |0.000266 |0.000083 |0.000455| |384 |0.000588 |0.000249 |0.000207| |512 |0.001663 |0.000329 |0.001303| |768 |0.002396 |0.000691 |0.004087| |1024 |0.007945 |0.003774 |0.005273| |2048 |0.040656 |0.01141 |0.024927| |4096 |0.180817 |0.047046 |0.101344| Tu przedstawiłem uśrednione informacje o czasach i miss ratio wybranych N przy implementacji «transpose0». | Długość boku macierzy | Potrzebna pamięć | Czas | L1 Data Cache miss ratio | L2 Data Cache miss ratio | L3 Cache miss ratio | | --------------------- | ---------------- | ----------- | ------------------------ | ------------------------ | ------------------- | | 128 | 64 KiB | 0.000095600 | 72.059933 | 14.735733 | 0.195933 | | 144 | 81 KiB | 0.000066333 | 6.3712 | 13.748733 | 0.1142 | | 256 | 256 KiB | 0.000347333 | 65.566133 | 110.648067 | 0.132867 | | 272 | 289 KiB | 0.000122133 | 6.5018 | 14.332133 | 0.124667 | | 3072 | 36864 = 36 Mib | 0.155187267 | 75.406533 | 110.600733 | 76.3168 | | 3056 | 36481 Kib | 0.068847267 | 71.882 | 163.341667 | 11.440533 | 3. Na koniec porównałem obie implementacje. Wynik już na podstawie wykładu oraz poprzedniego zadania był oczywisty, ale postanowiłem zrobić po 3 uśrednione testy, aby faktycznie to potwierdzić. | N | Czas v0 | Czas v1 | | -------- | -------- | ----------- | | 3056 | 0.068846867 | 0.013631267 | | 4656 | 0.188424533 | 0.032854200 | | 6272 | 0.392965467 | 0.064221933 | Wnioski --- * Jaki wpływ na wydajność «transpose1» ma rozmiar kafelka? Na podstaweie tabeli w wynikach eksperymentów rozmiar kafelka ma wpływ na wydajnośc «transpose1». Można zauważyć wyraźny spadek wydajności algorytmu przy długości bloku znacznie odbiegającej od wartości BLOCK = 8, dla której implementacja transpozycji macierzy działa najszybciej (średnio 1,1 sek dla N = 16384). Widać również wariacje trafień i chybień. Wyraźnie jednak widać, że najwięcej trafień mamy dla wartości BLOK = 8, ponieważ optymalizuje to procent trafień do poszczególnych cache'y. * Czy czas wykonania programu z różnymi rozmiarami macierzy identyfikuje rozmiary poszczególnych poziomów pamięci podręcznej? Na podstawie tabeli, w której zamieściłem odpowiednie wartości N, takie aby pamięć macierzy była wielokrotnością pamięci poszczególnych cashe, możemy zauważyć znaczny spadek wydajności (co widać po czasie) (w porównaniu do N o 16 powiększonego, co również zamieściłem w tabeli) oraz znaczny spadek procentowy trafień do tych właśnie cache'y, których wielokrotność badałem. Na podsawie czasów i tych obserwacji jednak ciężko mi byłoby jednoznacznie wyznaczyć rozmiar poszczególnych cache'y. Podsumowanie --- Na podstawie uśrednionych wartości czasów wyraźnie widać, że implementacja «transpose1» jest szybsza od «transpose0». Tak jak w poprzednim zadaniu, rozwiązanie blokowe jest najbardziej wydajne. Wynika to wszystko z danych, które zamieściłem w wynikach eksperymetnów.