Dlaczego MATLAB jest tak szybki w mnożeniu macierzy?

Robię pewne testy porównawcze z CUDA, C ++, C #, Java i używam MATLAB do weryfikacji i generowania macierzy. Kiedy wykonuję mnożenie macierzy za pomocą MATLAB, 2048x2048nawet większe macierze są prawie natychmiast mnożone.

             1024x1024   2048x2048   4096x4096
             ---------   ---------   ---------
CUDA C (ms)      43.11      391.05     3407.99
C++ (ms)       6137.10    64369.29   551390.93
C# (ms)       10509.00   300684.00  2527250.00
Java (ms)      9149.90    92562.28   838357.94
MATLAB (ms)      75.01      423.10     3133.90

Tylko CUDA jest konkurencyjna, ale myślałem, że przynajmniej C ++ będzie nieco zbliżony i nie 60 razy wolniejszy. Nie wiem też, co myśleć o wynikach w C #. Algorytm jest tak samo jak C ++ i Java, ale nie olbrzymi skok 2048z 1024.

Jak MATLAB wykonuje tak szybkie mnożenie macierzy?

Kod C ++:

float temp = 0;
timer.start();
for(int j = 0; j < rozmer; j++)
{
    for (int k = 0; k < rozmer; k++)
    {
        temp = 0;
        for (int m = 0; m < rozmer; m++)
        {
            temp = temp + matice1[j][m] * matice2[m][k];
        }
        matice3[j][k] = temp;
    }
}
timer.stop();

Oto moje wyniki z użyciem MATLAB R2011a + Parallel Computing Toolbox na maszynie z Tesla C2070:

>> A = rand(1024); gA = gpuArray(A);
% warm up by executing the operations a couple of times, and then:
>> tic, C = A * A; toc
Elapsed time is 0.075396 seconds.
>> tic, gC = gA * gA; toc
Elapsed time is 0.008621 seconds.

MATLAB wykorzystuje wysoce zoptymalizowane biblioteki do mnożenia macierzy, dlatego zwykłe mnożenie macierzy MATLAB jest tak szybkie. gpuArrayWersja używa magmy .

Zaktualizuj za pomocą R2014a na maszynie z Tesla K20c, a nowe timeiti gputimeitfunkcje:

>> A = rand(1024); gA = gpuArray(A);
>> timeit(@()A*A)
ans =
    0.0324
>> gputimeit(@()gA*gA)
ans =
    0.0022

Zaktualizuj za pomocą R2018b na maszynie WIN64 z 16 fizycznymi rdzeniami i Tesla V100:

>> timeit(@()A*A)
ans =
    0.0229
>> gputimeit(@()gA*gA)
ans =
   4.8019e-04

(Uwaga: w pewnym momencie (zapomnę, kiedy dokładnie) gpuArrayzmieniłem z MAGMA na cuBLAS - MAGMA jest nadal używana do niektórych gpuArrayoperacji)

Tego rodzaju pytania powracają i należy na nie odpowiedzieć jaśniej niż „MATLAB używa wysoce zoptymalizowanych bibliotek” lub „MATLAB używa MKL” raz na przepełnieniu stosu.

Historia:

Mnożenie macierzy (wraz z wektorem macierzy, mnożeniem wektora i wieloma rozkładami macierzy) jest (są) najważniejszymi problemami w algebrze liniowej. Inżynierowie rozwiązują te problemy z komputerami od pierwszych dni.

Nie jestem ekspertem od historii, ale najwyraźniej wtedy wszyscy przepisali jego wersję FORTRAN za pomocą prostych pętli. Potem pojawiła się pewna standaryzacja, wraz z identyfikacją „jąder” (podstawowych procedur), które większość problemów algebry liniowej potrzebowała do rozwiązania. Te podstawowe operacje zostały następnie znormalizowane w specyfikacji o nazwie: podprogramy podstawowej algebry liniowej (BLAS). Inżynierowie mogliby wówczas nazwać te standardowe, dobrze przetestowane procedury BLAS w swoim kodzie, co znacznie ułatwi ich pracę.

BLAS:

BLAS ewoluował z poziomu 1 (pierwsza wersja, która definiowała operacje na wektorach skalarnych i wektorach) do poziomu 2 (operacje na macierzach wektorowych) do poziomu 3 (operacje na macierzach) i dostarczał coraz więcej „jąder”, więc bardziej znormalizowanych i więcej podstawowych operacji algebry liniowej. Oryginalne implementacje FORTRAN 77 są nadal dostępne na stronie internetowej Netlib .

W kierunku lepszej wydajności:

Tak więc z biegiem lat (zwłaszcza między wydaniami BLAS poziomu 1 i poziomu 2: wczesne lata 80.) zmienił się sprzęt wraz z nadejściem operacji wektorowych i hierarchii pamięci podręcznej. Te zmiany umożliwiły znaczne zwiększenie wydajności podprogramów BLAS. Następnie pojawili się różni dostawcy, którzy wdrażali procedury BLAS, które były coraz bardziej wydajne.

Nie znam wszystkich historycznych wdrożeń (wtedy nie urodziłem się ani nie byłem dzieckiem), ale na początku 2000 roku pojawiły się dwa najbardziej znaczące: Intel MKL i GotoBLAS. Twój Matlab korzysta z Intel MKL, który jest bardzo dobrym, zoptymalizowanym BLAS, a to wyjaśnia doskonałą wydajność, którą widzisz.

Szczegóły techniczne dotyczące mnożenia macierzy:

Dlaczego więc Matlab (MKL) jest tak szybki w dgemm(dwukrotne ogólne mnożenie macierzy-macierzy)? Mówiąc prosto: ponieważ wykorzystuje wektoryzację i dobre buforowanie danych. W bardziej złożonych terminach: patrz artykuł dostarczony przez Jonathana Moore'a.

Zasadniczo, gdy wykonujesz mnożenie w dostarczonym kodzie C ++, wcale nie jesteś przyjazny dla pamięci podręcznej. Ponieważ podejrzewam, że stworzyłeś tablicę wskaźników do tablic wierszowych, twoje dostępy w wewnętrznej pętli do k-tej kolumny „matice2”: matice2[m][k]są bardzo wolne. Rzeczywiście, kiedy uzyskujesz dostęp matice2[0][k], musisz uzyskać k-ty element tablicy 0 macierzy. Następnie w następnej iteracji musisz uzyskać dostęp matice2[1][k], który jest k-tym elementem innej tablicy (tablica 1). Następnie w następnej iteracji uzyskujesz dostęp do kolejnej tablicy i tak dalej ... Ponieważ cała matryca matice2nie mieści się w najwyższych pamięciach podręcznych (ma 8*1024*1024duże bajty), program musi pobrać żądany element z pamięci głównej, tracąc dużo czas.

Jeśli właśnie przetransponowałeś macierz, aby dostęp był w ciągłych adresach pamięci, twój kod działałby już znacznie szybciej, ponieważ teraz kompilator może ładować całe wiersze w pamięci podręcznej w tym samym czasie. Po prostu wypróbuj zmodyfikowaną wersję:

timer.start();
float temp = 0;
//transpose matice2
for (int p = 0; p < rozmer; p++)
{
    for (int q = 0; q < rozmer; q++)
    {
        tempmat[p][q] = matice2[q][p];
    }
}
for(int j = 0; j < rozmer; j++)
{
    for (int k = 0; k < rozmer; k++)
    {
        temp = 0;
        for (int m = 0; m < rozmer; m++)
        {
            temp = temp + matice1[j][m] * tempmat[k][m];
        }
        matice3[j][k] = temp;
    }
}
timer.stop();

Możesz więc zobaczyć, jak po prostu pamięć podręczna znacznie zwiększyła wydajność kodu. Teraz prawdziwe dgemmimplementacje wykorzystują to na bardzo szerokim poziomie: wykonują mnożenie na blokach macierzy określonych przez rozmiar TLB (bufor lookaside tłumaczenia, krótka historia: co można skutecznie buforować), aby przesyłać strumieniowo do procesora dokładnie ilość danych, które może przetworzyć. Innym aspektem jest wektoryzacja, używają one wektoryzowanych instrukcji procesora w celu uzyskania optymalnej przepustowości instrukcji, czego tak naprawdę nie można zrobić z wieloplatformowego kodu C ++.

Wreszcie, ludzie twierdzący, że jest to spowodowane algorytmem Strassena lub Coppersmitha-Winograda, są w błędzie, oba te algorytmy nie są możliwe do wdrożenia w praktyce ze względu na wspomniane wyżej względy sprzętowe.

To dlaczego . MATLAB nie wykonuje naiwnego mnożenia macierzy przez zapętlanie każdego elementu, tak jak w kodzie C ++.

Oczywiście zakładam, że właśnie użyłeś C=A*Bzamiast pisać funkcję mnożenia.

Matlab włączył LAPACK jakiś czas temu, więc zakładam, że ich mnożenie macierzy używa czegoś co najmniej tak szybko. Kod źródłowy LAPACK i dokumentacja są łatwo dostępne.

Możesz także zajrzeć do artykułu Goto i Van De Geijna „Anatomia wysokowydajnego mnożenia macierzy” na stronie http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.1785&rep=rep1&type=pdf

Odpowiedź brzmi: LAPACK, a biblioteki BLAS sprawiają, że MATLAB jest oślepiająco szybki w operacjach matrycowych, a nie żaden zastrzeżony kod przez ludzi z MATLAB.

Użyj bibliotek LAPACK i / lub BLAS w kodzie C ++ do operacji na macierzach i powinieneś uzyskać podobną wydajność jak MATLAB. Biblioteki te powinny być swobodnie dostępne w każdym nowoczesnym systemie, a części zostały opracowane przez dziesięciolecia w środowisku akademickim. Należy pamiętać, że istnieje wiele implementacji, w tym niektóre zamknięte źródła, takie jak Intel MKL .

Dyskusja na temat tego, jak BLAS osiąga wysoką wydajność, jest dostępna tutaj.

BTW, z mojego doświadczenia jest poważny problem z wywoływaniem bibliotek LAPACK bezpośrednio z c (ale warto). Musisz dokładnie przeczytać dokumentację.

Podczas mnożenia macierzy używasz naiwnej metody mnożenia, która wymaga czasu O(n^3).

Istnieje algorytm mnożenia macierzy, który wymaga O(n^2.4). Co oznacza, że n=2000Twój algorytm wymaga ~ 100 razy więcej obliczeń niż najlepszy algorytm.
Naprawdę powinieneś sprawdzić stronę wikipedii pod kątem mnożenia macierzy, aby uzyskać dodatkowe informacje na temat efektywnych sposobów jej realizacji.

W zależności od wersji Matlaba, sądzę, że może już korzystać z twojego GPU.

Inna rzecz; Matlab śledzi wiele właściwości twojej matrycy; w jej przekątnej, hermetyce i tak dalej, i specjalizuje się w oparciu o nią algorytmy. Może specjalizuje się w oparciu o macierz zerową, którą mi przekazujesz, czy coś takiego? Może buforowanie powtarzających się wywołań funkcji zaburza Twoje czasy? Być może optymalizuje powtarzające się nieużywane produkty matrycowe?

Aby uchronić się przed takimi zdarzeniami, użyj matrycy liczb losowych i upewnij się, że wymuszasz wykonanie, drukując wynik na ekranie lub dysku lub w inny sposób.

MATLAB wykorzystuje wysoce zoptymalizowaną implementację LAPACK od Intela znaną jako Intel Math Kernel Library (Intel MKL) - w szczególności funkcję dgemm . Szybkość Ta biblioteka wykorzystuje funkcje procesora, w tym instrukcje SIMD i procesory wielordzeniowe. Nie dokumentują używanego algorytmu. Jeśli miałbyś wywołać Intel MKL z C ++, powinieneś zobaczyć podobną wydajność.

Nie jestem pewien, jakiej biblioteki MATLAB używa do mnożenia GPU, ale prawdopodobnie coś takiego jak nVidia CUBLAS .

Ogólna odpowiedź na pytanie „Dlaczego matlab jest szybszy w wykonywaniu xxx niż inne programy” jest taka, że ​​matlab ma wiele wbudowanych, zoptymalizowanych funkcji.

Inne używane programy często nie mają tych funkcji, więc ludzie stosują własne kreatywne rozwiązania, które są zaskakująco wolniejsze niż profesjonalnie zoptymalizowany kod.

Można to interpretować na dwa sposoby:

1) Powszechny / teoretyczny sposób: Matlab nie jest znacznie szybszy, po prostu źle robisz test porównawczy

2) Realistyczny sposób: w tym przypadku Matlab jest szybszy w praktyce, ponieważ języki takie jak c ++ są zbyt łatwo używane w nieskuteczny sposób.

Ostry kontrast wynika nie tylko z niesamowitej optymalizacji Matlaba (omówionej już w wielu innych odpowiedziach), ale również ze sposobu, w jaki sformułowałeś macierz jako obiekt.

Wygląda na to, że macie matrycę listę list? Lista list zawiera wskaźniki do list, które następnie zawierają elementy macierzy. Lokalizacje zawartych list są przypisywane arbitralnie. Gdy zapętlasz swój pierwszy indeks (numer wiersza?), Czas dostępu do pamięci jest bardzo znaczący. Dla porównania, dlaczego nie spróbujesz zaimplementować macierzy jako pojedynczej listy / wektora za pomocą następującej metody?

#include <vector>

struct matrix {
    matrix(int x, int y) : n_row(x), n_col(y), M(x * y) {}
    int n_row;
    int n_col;
    std::vector<double> M;
    double &operator()(int i, int j);
};

I

double &matrix::operator()(int i, int j) {
    return M[n_col * i + j];
}

Należy zastosować ten sam algorytm mnożenia, aby liczba flopów była taka sama. (n ^ 3 dla macierzy kwadratowych o rozmiarze n)

Proszę o czas, aby wynik był porównywalny z tym, co miałeś wcześniej (na tej samej maszynie). Dzięki porównaniu pokażesz dokładnie, jak znaczący może być czas dostępu do pamięci!

W C ++ jest wolny, ponieważ nie używasz wielowątkowości. Zasadniczo, jeśli A = BC, gdzie wszystkie są macierzami, pierwszy rząd A można obliczyć niezależnie od drugiego rzędu itp. Jeśli wszystkie A, B i C są wszystkie n na macierzach n, możesz przyspieszyć mnożenie przez współczynnik n ^ 2, jak

a_ {i, j} = sum_ {k} b_ {i, k} c_ {k, j}

Jeśli użyjesz, powiedzmy, Eigen [ http://eigen.tuxfamily.org/dox/GettingStarted.html ], wielowątkowość jest wbudowana, a liczba wątków jest regulowana.

Ponieważ MATLAB jest początkowo językiem programowania opracowanym dla numerycznej algebry liniowej (manipulacje macierzowe), który zawiera biblioteki specjalnie opracowane do mnożenia macierzy. A teraz MATLAB może dodatkowo korzystać z GPU (procesora graficznego) .

A jeśli spojrzymy na wyniki obliczeń:

             1024x1024   2048x2048   4096x4096
             ---------   ---------   ---------
CUDA C (ms)      43.11      391.05     3407.99
C++ (ms)       6137.10    64369.29   551390.93
C# (ms)       10509.00   300684.00  2527250.00
Java (ms)      9149.90    92562.28   838357.94
MATLAB (ms)      75.01      423.10     3133.90

wtedy możemy zobaczyć, że nie tylko MATLAB jest tak szybki w mnożeniu macierzy: CUDA C (język programowania NVIDIA) ma lepsze wyniki niż MATLAB. CUDA C ma również biblioteki opracowane specjalnie do mnożenia macierzy i wykorzystuje procesory graficzne.

Krótka historia MATLAB

Cleve Moler, przewodniczący działu informatyki na Uniwersytecie w Nowym Meksyku, zaczął opracowywać MATLAB pod koniec lat siedemdziesiątych. Zaprojektował go, aby dać swoim studentom dostęp do LINPACK (biblioteki oprogramowania do wykonywania numerycznej algebry liniowej) i EISPACK(jest biblioteką oprogramowania do numerycznego obliczania algebry liniowej) bez konieczności uczenia się Fortran. Wkrótce rozprzestrzenił się na inne uniwersytety i znalazł silną publiczność w społeczności matematyki stosowanej. Jack Little, inżynier, został narażony na to podczas wizyty Moler na Uniwersytecie Stanforda w 1983 roku. Uznając jego potencjał komercyjny, dołączył do Moler i Steve'a Bangerta. Przepisali MATLAB w C i założyli MathWorks w 1984 roku, aby kontynuować rozwój. Te przerobione biblioteki były znane jako JACKPAC. W 2000 r. MATLAB został przepisany, aby używać nowszego zestawu bibliotek do manipulacji matrycą, LAPACK (jest standardową biblioteką oprogramowania do numerycznej algebry liniowej).

Źródło

Co to jest CUDA C.

CUDA C korzysta również z bibliotek specjalnie opracowanych do mnożenia macierzy, takich jak OpenGL (Open Graphics Library). Wykorzystuje także GPU i Direct3D (w MS Windows).

Platformy CUDA jest przeznaczony do pracy z języków programowania takich jak C, C ++ i Fortran. Ta dostępność ułatwia specjalistom od programowania równoległego korzystanie z zasobów GPU, w przeciwieństwie do wcześniejszych interfejsów API, takich jak Direct3D i OpenGL , które wymagały zaawansowanych umiejętności programowania grafiki. Ponadto CUDA obsługuje platformy programistyczne, takie jak OpenACC i OpenCL .

Przykład przepływu przetwarzania CUDA:

1. Skopiuj dane z pamięci głównej do pamięci GPU
2. CPU inicjuje jądro obliczeniowe GPU
3. Rdzenie CUDA GPU wykonują jądro równolegle
4. Skopiuj uzyskane dane z pamięci GPU do pamięci głównej

Porównywanie prędkości procesora i GPU

Przeprowadziliśmy test porównawczy, w którym zmierzyliśmy czas potrzebny do wykonania 50 kroków czasowych dla rozmiarów siatki 64, 128, 512, 1024 i 2048 na procesorze Intel Xeon X5650, a następnie za pomocą procesora graficznego NVIDIA Tesla C2050.

Dla rozmiaru siatki 2048 algorytm pokazuje 7,5-krotny czas obliczeń z ponad minuty na procesorze do mniej niż 10 sekund na GPU. Wykres skali logarytmicznej pokazuje, że procesor jest rzeczywiście szybszy dla małych rozmiarów siatki. Jednak wraz z rozwojem i dojrzewaniem technologii rozwiązania GPU są coraz bardziej w stanie poradzić sobie z mniejszymi problemami.

Źródło

Od wprowadzenia do przewodnika programowania CUDA C:

Kierując się nienasyconym zapotrzebowaniem rynku na grafikę 3D w czasie rzeczywistym, programowalny procesor graficzny lub GPU ewoluował w wysoce równoległy, wielowątkowy procesor manycore z ogromną mocą obliczeniową i bardzo dużą przepustowością pamięci, co ilustrują Figure 1i Figure 2.

Rysunek 1. Operacje zmiennoprzecinkowe na sekundę dla procesora i karty graficznej

Rycina 2 . Przepustowość pamięci dla procesora i karty graficznej

Przyczyną rozbieżności w zdolności do operacji zmiennoprzecinkowych między CPU a GPU jest to, że GPU specjalizuje się w intensywnych obliczeniach, bardzo równoległych obliczeniach - dokładnie o to, czym jest renderowanie grafiki - i dlatego zaprojektowano je tak, aby więcej tranzystorów było poświęconych przetwarzaniu danych zamiast buforowania danych i kontroli przepływu, jak schematycznie ilustruje Figure 3.

Rycina 3 . GPU poświęca więcej tranzystorów przetwarzaniu danych

Mówiąc dokładniej, procesor graficzny jest szczególnie dobrze przystosowany do rozwiązywania problemów, które można wyrazić jako obliczenia równoległe do danych - ten sam program jest wykonywany równolegle na wielu elementach danych - z dużą intensywnością arytmetyczną - stosunek operacji arytmetycznych do operacji pamięci. Ponieważ ten sam program jest wykonywany dla każdego elementu danych, istnieje mniejsze wymaganie dotyczące zaawansowanej kontroli przepływu, a ponieważ jest on wykonywany na wielu elementach danych i ma wysoką intensywność arytmetyczną, opóźnienie dostępu do pamięci można ukryć za pomocą obliczeń zamiast pamięci podręcznych dużych danych .

Przetwarzanie równoległe danych odwzorowuje elementy danych na wątki przetwarzania równoległego. Wiele aplikacji przetwarzających duże zestawy danych może korzystać z modelu programowania równoległego w celu przyspieszenia obliczeń. W renderowaniu 3D duże zestawy pikseli i wierzchołków są mapowane na równoległe wątki. Podobnie aplikacje do przetwarzania obrazów i mediów, takie jak przetwarzanie końcowe renderowanych obrazów, kodowanie i dekodowanie wideo, skalowanie obrazu, widzenie stereo i rozpoznawanie wzorów mogą mapować bloki obrazów i piksele na wątki przetwarzania równoległego. W rzeczywistości wiele algorytmów poza obszarem renderowania i przetwarzania obrazów jest przyspieszanych przez przetwarzanie równoległe do danych, od ogólnego przetwarzania sygnału lub symulacji fizyki do finansów obliczeniowych lub biologii obliczeniowej.

Źródło

Zaawansowane czytanie

• GPU (jednostka przetwarzania grafiki)
• MATLAB
• Przewodnik programowania CUDA C.
• Korzystanie z GPU w MATLAB

• Podstawowe podprogramy algebry liniowej (BLAS)

• Anatomia wysokowydajnego mnożenia macierzy , autorstwa Kazushige Goto i Roberta A. Van De Geijna

Kilka interesujących twarzy

Napisałem mnożenie macierzy C ++, które jest tak szybkie jak Matlab, ale zajęło to trochę uwagi. (Zanim Matlab używał do tego GPU).

Cytat z tej odpowiedzi .