---
# System prepended metadata

title: Raport do zadania opt-transpose
tags: [ASK]

---

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