---
# System prepended metadata

title: Raport do zadania 1
tags: [ASK]

---

---
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:

![](https://i.imgur.com/pwbUbMz.png)
:::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 