---
title: Raport do zadania 1
tags: ASK
author: Mateusz Reis
---

# Raport do zadania 1

### Autor: Mateusz Reis
### Numer indeksu: 316276

Konfiguracja
---

Informacje o systemie:

* Dystrybucja: Debian
* Jądro systemu: 5.3.0-53-generic
* Kompilator: gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
* Procesor: AMD A8-6500
* Liczba rdzeni: 4

Pamięć podręczna:

* L1d: 16 KiB, 4-drożny (per rdzeń), rozmiar linii 64B
* L2: 2048 KiB, 16-drożny (per rdzeń), rozmiar linii 64B
* L3: brak , ?-drożny (współdzielony), rozmiar linii 64B

Pamięć TLB:

* L1d: 4KiB strony, w pelni asocjacyjny, 64 wpisy
* L2: 4KiB strony, 8-drożny, 1024 wpisów

Informacje o pamięciach podręcznych uzyskano na podstawie wydruku programu
`x86info`.

Wyniki eksperymentów
---
Tabelka dla kazdej wersji mnozenia (wynik zostal usredniony na podstawie 10 pomiarow):

#### Tabelka dla wersji malmut0(ijk)
|Wymiar macierzy|Czas (s)|Ilosc instrukcji|Ilosc instrukcji w ciagu 1 cyklu|Ilosc cykli na jedna iteracje petli|
|---------------|--------|----------------|--------------------------------|-|
| 16 x 16 | 0.0000081 | 31341 | 1.3898 |5.50555|
| 64 x 64 | 0.000526 | 1872670 | 1.2146 |5.8815 |
| 256 x 256 | 0.0368245 | 118032870 | 0.9374 |7.50513|
| 512 x 512 | 2.62226 | 941888919 | 0.0998 |66.7354|
| 1024 x 1024 | 27.4029 | 7525646399 | 0.0781 |89.7414|

#### Tabelka dla wersji malmut1(kij)
|Wymiar macierzy|Czas (s)|Ilosc instrukcji|Ilosc instrukcji w ciagu 1 cyklu|Ilosc cykli na jedna iteracje petli|
|---------------|--------|----------------|--------------------------------|-|
| 16 x 16 | 0.0000073 | 26951 | 1.0588 |6.21443|
| 64 x 64 | 0.0004121 | 1606295 | 1.1188 |5.47688|
| 256 x 256 | 0.0251398 | 101189598 | 1.0964 |5.50107|
| 512 x 512 | 0.285333 | 807407399 | 0.7774 |7.34404|
| 1024 x 1024 | 2.59365 | 6450847630 | 0.6797 |8.83893|

#### Tabelka dla wersji malmut2(jki)
|Wymiar macierzy|Czas (s)|Ilosc instrukcji|Ilosc instrukcji w ciagu 1 cyklu|Ilosc cykli na jedna iteracje petli|
|---------------|--------|----------------|--------------------------------|-|
| 16 x 16 | 0.0000077 | 31048 | 1.2904 |5.87421|
| 64 x 64 | 0.0026941 | 1868440 | 0.2092 |34.0704|
| 256 x 256 | 0.175323 | 117966854 | 0.195 |36.0583|
| 512 x 512 | 5.1626 | 941626317 | 0.0542 |122.847|
| 1024 x 1024 | 66.972 | 7524605517 | 0.033 |212.359|

#### Tabelka dla wersji malmut3(kafelkowanie)
|Wymiar macierzy|Czas (s)|Ilosc instrukcji|Ilosc instrukcji w ciagu 1 cyklu|Ilosc cykli na jedna iteracje petli|
|---------------|--------|----------------|--------------------------------|-|
| 16 x 16 | 0.0000077 | 31360 | 1.3678|5.59749|
| 64 x 64 | 0.0003686 | 1990555 | 1.7854|4.25303|
| 256 x 256 | 0.0307984 | 127371303 | 1.1948|6.35414|
| 512 x 512 | 0.35866 | 1018960814 | 0.8131|8.86136|
| 1024 x 1024 | 2.98021 | 8151656617 | 0.78|9.7331|

### Wykres
przedstawiajacy ostantnia kolumne w stosunku do rozmiaru macierzy:

:::danger
IJK
:::
:::warning
KIJ (zostal zasloniety przez kafelkowanie)
:::
:::success
JKI
:::
:::info
Kafelkowanie
:::

Wnioski
---
>Uzyskane wyniki nieznacznie roznia sie od tych przedstawionych na slajdach, widac dosyc wyraznie w ktorym miejscu wyszlismy poza cache L2. Wynika to z dluzszego czasu dostepu do pamieci wyzszych poziomow
-----------------------
>Rozbieznosc wynika z sposobu przechodzenia po macierzach

>>w wersji 0
przechodzimy po macierzy b wierszami co skutkuje wczytywaniem nowych wierszy w niemal kazdym obrocie petli. Daje to wspolczynnik chybien na poziomie powyzej 50% co jest objawia sie ogromnym wzrostem cykli procesora potrzebnych na jeden obrot petli.
>>w wersji 1
przechodzimy po macierzach wierszami co pozwala nam uniknac wczytywania danych co obrot, dzieki czemu nie marnujemy czasu na oczekiwanie na dane.
Odbija sie to na wspolczynniku chybiem, ktory oscyluje wokol 6%. Pozwala to na osiagniecie zadowalajacych wynikow nawet dla duzych rozmiarow macierzy.

>>w wersji 2
oczytujemy kazda macierz wierszami wiec przy kazdym odczycie danych pytamy o informacje, ktore nie znajduja sie w naszej pamieci cache co skutkuje wspolczynnikiem chybien rownym 100%, widac to szegolnie gdy nasze dane przerosna pamiec cache.

>>w wersji 3
wczytujemy cale bloki naszych macierzy co pozwala znacznie efektywniej korzystac z pamieci i nie wymaga tak czestego wczytywania danych z wolniejszych pamieci. Sposob ten jest szcegolnie efektywny dla bardzo duzych danych poniewaz wypelniamy na raz nasza pamiec cache danymi ktorych zaraz bedziemy uzywac. Na wykresie i w tabelkach nie widac tak dokladnie przewagi tego rozwiazania, poniewaz wykonanie mnozenia macierzy 2048x2048 dla wersji 2 zajeloby zbyt duzo czasu.
------------
> Ponizsza tabelka przedstawia wplyw rozmiaru kafelka na wydajnosc algorytmu :
>
>
>
>
>
|Rozmiar kafelka|16x16|64x64|256x256|512x512|1024x1024|
|-|-|-|-|-|-|-|-|
|4|0.000017 |0.000688|0.032970 |0.489633|4.624116|
|8|0.000014 |0.000687 |0.030493 |0.486988 |4.651389 |
|16|0.000017|0.000686|0.0307984|0.35866|4.977306|
|32|0.000013|0.000689|0.031883|0.383981|4.273074 |
|64|0.000017|0.000568|0.030554|0.512697 |4.791583|
|128|0.000018 |0.000686|0.031701 |0.493415 |4.803542|

==Te testy roznia sie od testow z tabelki powyzej z powodu wiekszego obciazenia procesora==

>Jak widac z tabelki rozmiar kafelka ma znikomy wplyw na wydajnosc algorytmu
-----
>Spadek wydajnosci mozna zaobserwowac dla n >= 512, macierz ma wtedy rozmiar 2048 KiB wiec w pamieci cache L2 mozemy trzymac tylko jedna taka macierz co generuje duza ilosc chybien i odczytow z pamiec operacyjnej, ktora nie jest tak wydajna jak pamiec cache.
-----
>Zmiana wartosci <<*_OFFSET>> na 0 powoduje spadek wydajnosci w kafelkowanej wersji poniewaz przykladowo czesc macierzy a bedzie znajdowala sie w zbiorze x a proba przeczytania macierzy b bedzie skutkowac sprawdzeniem wlasnie zbioru x, co wygeneruje conflict miss.
Po takim zdarzeniu wyrzucimy czesc macierzy a, ktorej bedziemy potrzebowac w nastepnej iteracji ~ psuje to idee wczytywania danych "na zapas".
Natomiast zmiana <<*_OFFSET>> na inne wartosci dopoki sa one rozne nie wplywa znaczaco na wydajnosc