On 24 Sty, 17:33, Mariusz Marszałkowski <m...@g...com> wrote:

> Mam takie wyniki:
> Matlab 0.68
> Ten kod który zamieściłem 2.25
> Czyli matlab jest szybszy 3.3 razy.


Pod wplywem linkow z poprzedniego watku zaczalem troszke
eksperymentowac,
wyniki dojrzaly chyba do wyjscia na swiat

Dla uproszczenia sobie zycia testuje tylko macierze o rozmierze
bedacym wielokrotnoscia 192 (NWW(64,24)). Wyniki wrzucam dla 960.

Mierzone w kilka razy w petli, biore najlepszy wynik (praktycznie sie
nie roznily),
watek mial ustawione priorytet real time.

Indeksowanie: C(i,,j) = B(i,k)*C(k,j)
lub w rozwinieciu na c:
C[i*N+j] += A[i*N+k]*B[k*N+j]; (*)


1. Algorytm naiwny, ijk
46.6s

2. Prosta sztuczka, w ostatniej petli chcemy isc po kolei po pamieci,
a nie skakac. Patrzymy na (*) i ustalamy koljnosc petli na ikj.
Wynik, 10.23s $ razy lepiej.

3. Kod z konkursu. Wywalilem czesc wielowatkowa, bo mam jeden rdzen.
Korzysta on tam z fortranowskiego sposobu zapisu macierzy,
ale to nie ma znaczenia dla szybkosci. Wkladajac mu macierze
w odwrotnej kolejnosci dostajemy to samo (bo (B' *A')'=A*B)
Jesli to ja czegos nie popsulem:), wynik niewiele lepszy:
9.644s.

4. Wstepna transpozycja. Kolega machnal. Przed wykonaniem
wlasciwego sumowania przepisujemy macierz do tymczasowej
tablicy i tranponujemy ja. Kolejnosc ijk.
Kolejne przyszpieszenie 8.177s

5. Mnozymy blokami wielkosci SNxSN a bloki metoda ikj.
Kod niewiele mniej czytelny niz w ikj. W zaleznosci
od SN
8: 3.572 16: 3.262
24: 2.771 32: 2.634
48: 2.725 64: 2.574
Znaczna poprawa. Zeszlismy ponizej 2.6s, 18 razy lepiej niz naiwnie.

6. Kod z http://lwn.net/Articles/255364/ trzeci w 6.2.1
Ten sam algorytm, napisany (wg autora) tak, aby podpowiedziec
kompilaorowi
jak ma optymalizowac.
W zaleznosci od SN:
8: 4.634 16: 3.081
24: 2.624 32: 2.418
48: 2.206 64: 2.189
Ponizej 2.2s. Kilkanascie procent lepiej.

7. MATLAB.
piorytet wysoki, kilka prob, wybrana najlepsza
1.48s
30 razy lepiej niz naiwnie, nadal niepomijalnie szybciej niz
to, co udalo mi sie bez przesadnego siedzenia(1.7razy wolniej)
nad kodem lub wyszukiwania(1.5 razy wolniej) w sieci wycisnac z c++.


Jako bonus, kody (tylko moje, a noz cos poknocilem):

pozdrawiam
bartekltg

template <class T,int SM> void dgemm_bikj(T *A, T *B, T *C, int N)
{
int i,j,k,ii,kk,jj;

for (i = 0; i < N; i+=SM)
for (k = 0; k < N; k+=SM)
for (j = 0; j < N; j+=SM)
for (ii = i; ii < i+SM; ii++)
for (kk = k; kk < k+SM; kk++)
for (jj = j; jj < j+SM; jj++)
C[ii*N+jj] += A[ii*N+kk]*B[kk*N+jj];
}

void dgemm_ikj(double *A, double *B, double *C, int N)
{
int i,j,k;
for (i = 0; i < N; i++)
for (k = 0; k < N; k++)
for (j = 0; j < N; j++)
C[i*N+j] += A[i*N+k]*B[k*N+j];
}

void dgemm_ijk(double *A, double *B, double *C, int N)
{
int i,j,k;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 0; k < N; k++)
C[i*N+j] += A[i*N+k]*B[k*N+j];
}