Konkurs: najszybsze mno�enie macierzy

S�awa i nagroda!!!

O co chodzi?

Konkursowym wyzwaniem jest opracowanie od podstaw i ca�kowicie samodzielnie jak najszybszej funkcji bestdgemm mno�enia dw�ch macierzy NxN, tzn. implementacja dzia�ania algebry liniowej

C = AB.

Mo�na u�ywa� dowolnego (ale poprawnego ;-) algorytmu mno�enia macierzy: zwyk�ego z GALu ("wiersz razy kolumna"), Strassena, itd. Mo�na stosowa� (niemal) dowolne sztuczki: programowanie w assemblerze, masywn� r�wnoleg�o��, OpenMP, itp. S� tak�e pewne warunki formalne przyj�cia rozwi�zania:

  1. funkcja ma prawid�owo (w granicach rozs�dku) mno�y� "dowolne" (w granicach rozs�dku) macierze kwadratowe "dowolnego" wymiaru (w granicach rozs�dku)
  2. funkcja nie mo�e korzysta� w �adnym zakresie z istniej�cych bibliotek numerycznych (w wersji binarnej lub �r�d�owej)
  3. funkcja musi by� napisana w j�zyku C, dzia�a� poprawnie na students.mimuw.edu.pl i kompilowa� si� pod GCC
  4. rozwi�zanie - kod �r�d�owy funkcji w pliku o nazwie bestgemm.c - nale�y przes�a� na m�j adres e-mail do 26. maja.

Uwaga! W trakcie konkursu mog� pojawia� si� jakie� w�tpliwo�ci, uwagi, itp. powoduj�ce kosmetyczne (mam nadziej�) zmiany w zadaniu. Prosz� wi�c �ledzi� na bie��co modyfikacje tej strony!

Rzeczywi�cie, takie w�tpliwo�ci pojawi�y si�.
Czy mo�na podkr�ci� sw�j kod pod podany program testuj�cy?
By�oby to bardzo nieeleganckie. Kod testuj�cy mo�e by� zmieniony, a nam zale�y na funkcji tak generalnej, jak to tylko mo�liwe. Doda�em stosowne formalistyczne zastrze�enia (14.05.09.).
Czy macierz C jest zainicjalizowana na zero?
Nie, nie mo�emy tego zak�ada�.

Funkcja powinna mie� nast�puj�cy format wywo�ania: 


void bestdgemm(double *A, double *B, double *C, int N);

Umawiamy si�, �e tablice A, B, C s� jednowymiarowe d�ugo�ci N2, ich elementami s� liczby typu double i zachodzi nast�puj�ca relacja pomi�dzy elementami tabicy w programie, a abstrakacyjnym tworem matematycznym, jakim jest macierz:

A[(j-1)*N+i-1] = Ai,j, dla i,j = 1..N (analogicznie dla B, C).

Podstawowym (lecz niekoniecznie jedynym) kryterium oceny funkcji jest ca�kowity czas dzia�ania (real time) nast�puj�cego programu, kt�ry wywo�uje funkcj� bestdgemm: 



  1. /* 
  2. Standardowa kompilacja: 
  3. 	gcc -o testdgemm -static -O3 -funroll-loops -malign-double -fopenmp testdgemm.c bestdgemm.c -lblas -lpthread -lgfortran -lm
  4. Uruchomienie: 
  5. 	time ./testdgemm
  6. Wyniki na students.mimuw.edu.pl:
  7. 	[przykry@students ProgramyC]$ time ./testdgemm
  8. 	[  16.......]
  9. 	[  32.......]
  10. 	[  64.......]
  11. 	[ 128.......]
  12. 	[ 256.......]
  13. 	[ 512.......]
  14. 	[1024.......]
  15. 	[2048.......]
  16.  
  17. 	real	3m43.872s
  18. 	user	3m38.312s
  19. 	sys	0m2.373s
  20. */
  21.  
  22. #include <stdio.h>
  23. #include <stdlib.h>	
  24. #define MAXN 2048	/* maksymalny rozmiar macierzy; w testach mo�e by� wi�cej lub mniej */
  25. #define MULT 2		/*skok w rozmiarze macierzy; je�li badam macierz wymiaru K, to nast�pna ma wymiar MULT*K; w testach mo�e mie� inn� warto��, np. 3 */
  26. #define DONE fprintf(stderr,".")
  27. #define mtxalloc(N) malloc((N)*(N)*sizeof(double))
  28. #define mtxinit(A,N) {int i; for(i=0; i < (N)*(N); A[i]=i++);} /* lub cos podobnego */
  29. /* macierze kwadratowe *//* wymiar macierzy */"[%4d"/* poni�sza sekwencja jest przyk�adowa i w testach mo�e ulec zmianie: istotne jest, �e wyst�puje w niej kilka kolejnych wywo�a� bestdgemm() */"]\n");
  30. } /* for... */

�ci�gnij plik testdgemm.c!

Testy podstawowe wykonam poleceniem time ./testdgemm na komputerze z procesorem Intel Core 2 Duo E6550, w razie w�tpliwo�ci skorzystam z bardziej precyzyjnych metod pomiaru.

Je�li w komentarzu do funkcji bestdgemm nie zostanie zaznaczone inaczej, program testuj�cy zostanie skompilowany poleceniem jak powy�ej.

W komentarzu do funkcji warto tak�e za��czy� uzyskane przez siebie wyniki na students.mimuw.edu.pl. Niestety nie mo�emy wykorzysta� students.mimuw.edu.pl jako maszyny referencyjnej, bo czasy wykonania podlegaj� du�ym fluktuacjom.

Zwyci�stwo

Konkurs odbywa si� w trzech kategoriach:

Najszybszy na MIM
Wygrywa ten kod, kt�ry okaza� si� najszybszy w�r�d nades�anych
Szybszy od standardowych BLAS�w
Wygrywa, gdy program mno�y szybciej od BLAS�w zainstalowanych w LABie
Szybszy od zoptymalizowanych BLAS�w
Wygrywa, gdy program mno�y szybciej od zoptymalizowanych BLAS�w (najprawdopodobniej ATLAS)

Por�wnanie wszystkich wynik�w we wszystkich kategoriach zamieszcz� na tej stronie najwcze�niej w czerwcu (je�li autor zastrze�e sobie anonimowo��, podam tylko jego nick).

Nagroda zostanie wr�czona zwyci�zcy w najszerszej z mo�liwych kategorii.

Wyniki 2009

Dzi�kuj� wszystkim zawodnikom i gratuluj� niesamowitych czas�w!!! Zawody by�y naprawd� emocjonuj�ce, a kolejno�� zawodnik�w zmienia�a jak w kalejdoskopie. Cho� najszybszy program napisa� p. Skrzypczy�ski, to zwyci�y� p. Maczy�ski. Niestety, program p. Skrzypczy�skiego zak�ada, �e wymiar macierzy jest wielokrotno�ci� liczby 4.

Mam nadziej�, �e w przysz�orocznej edycji dojdzie do prawdziwie morderczego starcia!

Miejsce Zawodnik Czas (s) Nades�any kod Wynik i uwagi
ATLAS 5.5
Krzysztof Skrzypczy�ski 11.1 bestdgemm.c Niestety nie dzia�a dla niekt�rych wymiar�w macierzy
1. Kornel Maczy�ski 32.7 bestdgemm.c Najszybszy na MIM. Szybszy od std BLAS.
BLAS 69.2
Sebastian Chojniak 84.2 Niestety �le/nie dzia�a dla macierzy du�ych wymiar�w
2. Radomir Mastalerz 486.2 bestdgemm.c

Pomiary czasu na komputerze LABowym, Dell Precision 390, z procesorem Intel(R) Core(TM)2 CPU DualCore 6600 2.40GHz, 4MB cache. Wielokrotnie mno�ono macierze wymiaru od 16 do 2048. Punktem odniesienia by�y standardowe BLASy ze students oraz ATLAS niestety z nieco innej (prawdopodobnie troch� szybszej - dzi�kuj� p. Skrzypczy�skiemu za zwr�cenie uwagi) maszyny, Intel Core 2 Duo DualCore E6550 2.30GHz, 4MB cache.

Aktualizacja: 06.10.2010, 10:29:18.
© Piotr Krzy�anowski