On 21 Sty, 09:22, thrunduil <t...@w...pl> wrote:

> To jest w zasadzie niemozliwe. Kod mnozenia macierzy jest bardzo

Nie mow za wczesnie niemozliwe, bo pozniej trzeba bedzie odkrecac:)

U mnie dzieje sie to samo, przy parametrach jakie podal Mariusz
mnozenia te nie sa robione zbyt wydajnie.

> zlozony. Bez naprawde dobrze stuningowanego memory use, wstaweg
> asemblerowych
> i dlugiego testowania parametrow optymalizacyjnych nie ma szans na
> zblizenie sie do wydajnosci Matlaba. Istnieja szybsze implementacje
> mnozenia macierzy,
> np GOTO blas jest ok 10% szybszy, ale i tak to jest w zasadzue
> technologiczny limit na dzisiaj.
> Kod Matlabla (tj bibliteka MKL, matlab nie napisal tego kodu sam)
> jest o rzad wielkosci szybszy od dobrze stuningowanego kodu w C.

Dwie rownowazne operacje (1000 wektorow mnozymy przez macierz 1000 na
1000),
tylko raz w petli, a raz zwijamy w paczuszke. Jak wynikalo z
sasiedniego
postu, algorytm jest ten sam bo matlab korzysta z n^3.

>> tic;a*b;toc
Elapsed time is 2.585347 seconds.

>> tic,for j=1:1000,a*v;end;toc
Elapsed time is 15.379616 seconds.

No to sie okazuje, ze narzut matlaba dla niewielkich wektorkow jest
spory.
Intelowski BLAS pokazuje skrzydla dopiero dla konkretnej ilosci
danych.

Sam uwzam, ze nie jest to szczegolnie uciezliwe, nie zdarzylo mi sie
na to narzekac, to nadal malutkie macierze a mnozyc ciagle
wektor chce raczej przez macierz rzadka (a wektor ma megabajty)
ale moge sobie wyobrazic zagadnienia, gdzie taka operacja bedzie
dominujaca.

pozdrawiam
bartekltg

do góry

On 21 Sty, 09:28, Wit Jakuczun <w...@g...com> wrote:
> On 21 Sty, 09:18, bartekltg <b...@g...com> wrote:
>
> > > Ale mogil sie postarac a wrecz powinni. Wystarczy rozpoznac
> > > ze mnozymy wektor przez macierz i dac goto do wyspecjalizowanej
> > > procedurki. Tak samo jesli mnozymy macierz [NxK] przez [KxM] dla
> > > M i N znacznie wiekszych niz K, to jakas wyspecjalizowana procedura
> > > wymnozylaby duzo szybciej niz ogolna.
>
> > Dla bardzo malych K mozna by sie bawic w rozwijanie petli.
> > Dla wiekszych - nie ma znaczenia przy algorytmie n^3.
>
> Może to rzuci jakieś światło na całą dyskusję (slaj
16ty):http://www-users.mat.uni.torun.pl/~bala/wyklad
_arch/wshop2000.pdf
> Złożoność ciągle jest N^3 ale działa szybciej niż pętelki.

> Blokowe mnożenie wykorzystuje ATLAS. Idea jest taka, żeby
> cache maskymalnie efektywnie wykorzystać.
> Ja kiedyś robiłem porównania ATLAS vs ręczny kod i ATLAS był
> dużo szybszy. Z tego co pamiętam to oprócz mnożenia rozwiązywałem
> układy równań.

Zgoda. Ale to nadal ten sam algorytm, wykonuje sie dokaldnie te same
mnozenie, jedynie w rozsadniejszej dla procesora kolejnosci.

> http://www.mimuw.edu.pl/~przykry/matmult.php

Szkoda, ze nie wiedzialem;)

pozdrawiam
bartekltg

do góry

On 21 Sty, 09:54, bartekltg <b...@g...com> wrote:

> > Może to rzuci jakieś światło na całą dyskusję (slaj
16ty):http://www-users.mat.uni.torun.pl/~bala/wyklad
_arch/wshop2000.pdf
> > Złożoność ciągle jest N^3 ale działa szybciej niż pętelki.
> > Blokowe mnożenie wykorzystuje ATLAS. Idea jest taka, żeby
> > cache maskymalnie efektywnie wykorzystać.
> > Ja kiedyś robiłem porównania ATLAS vs ręczny kod i ATLAS był
> > dużo szybszy. Z tego co pamiętam to oprócz mnożenia rozwiązywałem
> > układy równań.
>
> Zgoda. Ale to nadal ten sam algorytm, wykonuje sie dokaldnie te same
> mnozenie, jedynie w rozsadniejszej dla procesora kolejnosci.
>
Czyli nie ten sam :). Teoretyczna złożoność taka sama ale praktycznie
to są różne algorytmy.

> >http://www.mimuw.edu.pl/~przykry/matmult.php
>
> Szkoda, ze nie wiedzialem;)
>
Ja wiedziałem ale to wiele nie zmieniło... :D

Pozdrawiam,
Wit Jakuczun

do góry

On 21 Sty, 10:03, Wit Jakuczun <w...@g...com> wrote:

> Czyli nie ten sam :). Teoretyczna złożoność taka sama ale praktycznie
> to są różne algorytmy.

Nie tylko zlozonosc. Nawet ilosc operacji mnozenia doubli
taka sama:)

> > >http://www.mimuw.edu.pl/~przykry/matmult.php
>
> > Szkoda, ze nie wiedzialem;)
>
> Ja wiedziałem ale to wiele nie zmieniło... :D

Popatrzylem na najszybszy kod. Odechcailo mi sie:)

pozdrawiam
bartekltg

do góry

On 21 Sty, 09:41, bartekltg <b...@g...com> wrote:

> U mnie dzieje sie to samo, przy parametrach jakie podal Mariusz
> mnozenia te nie sa robione zbyt wydajnie.

Co to znaczy, ze nie sa robione zbyt wydajnie?
MKL jest pisany tak, zeby byc bardzo optymalnym juz przy macierzach
rzedu 30x30.
To jest blisko dolnego limitu wielkosci blokow wykorzystywanych w
Lapacku u musi byc optymalne.

> No to sie okazuje, ze narzut matlaba dla niewielkich wektorkow jest
> spory.

To nie ma nic wspolnego z narzutem Matlaba.
To sie nie skaluje liniowo. Kod mnozenia gdy prawa strona jest
macierza robi pewna sztuczke - blocking, podstawowy kod mnozenia ma
conajmniej szesc zagniezdzonych petli w taki sposob aby potrzebne
rzeczy byly w pamieci cache.
Cache misses dla L2 to koszt rzedu 200-300 cykli procesora. Unikniecie
wiec koniecznosci czytania pamieci daje duze oszczednosci.
Da sie to zrobic gdy prawa strona jest macierza, Gdy mnozy sie
wielkokrotnie przez wektor z prawej strony wykorzystanie pamieci jest
duzo gorsze, stad roznica efektywnosci. Narzut petli powinien byc
zaniedbywalny.

> Intelowski BLAS pokazuje skrzydla dopiero dla konkretnej ilosci
> danych.

Nie specjalnie pokazuje, peak jest dla macierzy ok 1.5tys x 1.5 tys.
Pozniej nastepuje pewne zalamanie.

do góry

On 21 Sty, 10:07, bartekltg <b...@g...com> wrote:

> Popatrzylem na najszybszy kod. Odechcailo mi sie:)

http://lwn.net/Articles/255364/

tutaj duzo lepiej widac co sie dzieje

do góry

On 21 Sty, 10:57, thrunduil <t...@w...pl> wrote:
> On 21 Sty, 10:07, bartekltg <b...@g...com> wrote:
>
> > Popatrzylem na najszybszy kod. Odechcailo mi sie:)
>
> http://lwn.net/Articles/255364/
>
> tutaj duzo lepiej widac co sie dzieje

Dobry artykuł. Dzięki.


Pozdrawiam,
Wit Jakuczun

do góry

epsilon$ while read LINE; do echo \>"$LINE"; done < "thrunduil"
>MKL jest pisany tak, zeby byc bardzo optymalnym juz przy macierzach
>rzedu 30x30.

Co to znaczy "bardzo optymalnym"?


--
[------------------------]
[ K...@e...eu.org ]
[ http://epsilon.eu.org/ ]
[------------------------]

do góry

On 2010-01-21, Mariusz Kruk <M...@e...eu.org> wrote:
> epsilon$ while read LINE; do echo \>"$LINE"; done < "thrunduil"
>>MKL jest pisany tak, zeby byc bardzo optymalnym juz przy macierzach
>>rzedu 30x30.
>
> Co to znaczy "bardzo optymalnym"?

W wolnym tłumaczeniu: "bardzo najlepszy".

--
Secunia non olet.
Stanislaw Klekot

do góry

On 21 Sty, 11:40, Mariusz Kruk <M...@e...eu.org> wrote:

> Co to znaczy "bardzo optymalnym"?

wezmy dowolny problem optymalizacji praktycznej -> jest funkcja i
zbior solverow numerycznych.
Kazdy solver daje rozwiazanie optymalne, ale jedne bardziej inne mniej.

do góry