Ich mache einige Benchmarks mit CUDA, C ++, C #, Java und verwende MATLAB zur Verifizierung und Matrixgenerierung. Wenn ich eine Matrixmultiplikation mit MATLAB durchführe, werden 2048x2048
noch größere Matrizen fast sofort multipliziert.
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
Nur CUDA ist wettbewerbsfähig, aber ich dachte, dass mindestens C ++ etwas eng und nicht 60-mal langsamer sein wird. Ich weiß auch nicht, was ich über die C # -Ergebnisse denken soll. Der Algorithmus ist genau der gleiche wie C ++ und Java, aber es gibt einen riesigen Sprung 2048
von 1024
.
Wie führt MATLAB die Matrixmultiplikation so schnell durch?
C ++ - Code:
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();
Antworten:
Hier sind meine Ergebnisse mit MATLAB R2011a + Parallel Computing Toolbox auf einem Computer mit einem Tesla C2070:
MATLAB verwendet hochoptimierte Bibliotheken für die Matrixmultiplikation, weshalb die einfache MATLAB-Matrixmultiplikation so schnell ist. Die
gpuArray
Version verwendet MAGMA .Update mit R2014a auf einem Computer mit einem Tesla K20c und den neuen
timeit
undgputimeit
Funktionen:Update mit R2018b auf einem WIN64-Computer mit 16 physischen Kernen und einem Tesla V100:
(NB: Irgendwann (ich vergesse wann genau) wurde
gpuArray
von MAGMA auf cuBLAS umgestellt - MAGMA wird jedoch immer noch für einigegpuArray
Operationen verwendet.)quelle
Diese Art von Frage kommt immer wieder vor und sollte klarer beantwortet werden als "MATLAB verwendet hochoptimierte Bibliotheken" oder "MATLAB verwendet die MKL" einmal bei Stapelüberlauf.
Geschichte:
Die Matrixmultiplikation (zusammen mit der Matrixvektor-, Vektorvektormultiplikation und vielen der Matrixzerlegungen) ist (sind) das wichtigste Problem in der linearen Algebra. Ingenieure haben diese Probleme seit den Anfängen mit Computern gelöst.
Ich bin kein Experte für die Geschichte, aber anscheinend hat damals jeder seine FORTRAN-Version mit einfachen Schleifen umgeschrieben. Dann kam eine gewisse Standardisierung mit der Identifizierung von "Kerneln" (Grundroutinen), die die meisten linearen Algebra-Probleme brauchten, um gelöst zu werden. Diese Grundoperationen wurden dann in einer Spezifikation standardisiert, die als Grundlegende lineare Algebra-Unterprogramme (BLAS) bezeichnet wurde. Ingenieure könnten diese standardmäßigen, gut getesteten BLAS-Routinen dann in ihrem Code aufrufen, was ihre Arbeit erheblich erleichtert.
BLAS:
BLAS entwickelte sich von Level 1 (der ersten Version, die Skalarvektor- und Vektorvektoroperationen definierte) zu Level 2 (Vektormatrixoperationen) zu Level 3 (Matrixmatrixoperationen) und lieferte immer mehr "Kernel", die so standardisiert waren und mehr der grundlegenden linearen Algebraoperationen. Die ursprünglichen FORTRAN 77-Implementierungen sind weiterhin auf der Netlib-Website verfügbar .
Auf dem Weg zu einer besseren Leistung:
Im Laufe der Jahre (insbesondere zwischen den Versionen BLAS Level 1 und Level 2: Anfang der 80er Jahre) änderte sich die Hardware mit dem Aufkommen von Vektoroperationen und Cache-Hierarchien. Diese Entwicklungen ermöglichten es, die Leistung der BLAS-Subroutinen erheblich zu steigern. Verschiedene Anbieter implementierten dann BLAS-Routinen, die immer effizienter wurden.
Ich kenne nicht alle historischen Implementierungen (ich war damals noch nicht geboren oder ein Kind), aber zwei der bemerkenswertesten kamen Anfang der 2000er Jahre heraus: Intel MKL und GotoBLAS. Ihr Matlab verwendet Intel MKL, ein sehr gutes, optimiertes BLAS, und das erklärt die großartige Leistung, die Sie sehen.
Technische Details zur Matrixmultiplikation:
Warum ist Matlab (die MKL) so schnell
dgemm
(allgemeine Matrix-Matrix-Multiplikation mit doppelter Genauigkeit)? In einfachen Worten: weil es Vektorisierung und gutes Zwischenspeichern von Daten verwendet. In komplexeren Begriffen: siehe den Artikel von Jonathan Moore.Wenn Sie Ihre Multiplikation in dem von Ihnen bereitgestellten C ++ - Code durchführen, sind Sie grundsätzlich überhaupt nicht cachefreundlich. Da ich vermute, dass Sie ein Array von Zeigern auf Zeilenarrays erstellt haben, sind Ihre Zugriffe in Ihrer inneren Schleife auf die k-te Spalte von "matice2":
matice2[m][k]
sehr langsam. In der Tat müssen Sie beim Zugriffmatice2[0][k]
das k-te Element des Arrays 0 Ihrer Matrix erhalten. In der nächsten Iteration müssen Sie dann aufmatice2[1][k]
das k-te Element eines anderen Arrays (das Array 1) zugreifen . In der nächsten Iteration greifen Sie dann auf ein weiteres Array zu und so weiter ... Da die gesamte Matrixmatice2
nicht in die höchsten Caches passt (sie ist8*1024*1024
Bytes groß), muss das Programm das gewünschte Element aus dem Hauptspeicher abrufen und dabei viel verlieren Zeit.Wenn Sie nur die Matrix transponiert hätten, sodass die Zugriffe auf zusammenhängende Speicheradressen erfolgen würden, würde Ihr Code bereits viel schneller ausgeführt, da der Compiler jetzt ganze Zeilen gleichzeitig in den Cache laden kann. Probieren Sie einfach diese modifizierte Version aus:
So können Sie sehen, wie nur die Cache-Lokalität die Leistung Ihres Codes erheblich gesteigert hat. Jetzt echt
dgemm
Implementierungen dies auf einer sehr umfangreichen Ebene: Sie führen die Multiplikation mit Blöcken der Matrix durch, die durch die Größe des TLB definiert sind (Translation Lookaside Buffer, lange Rede, kurzer Sinn: Was kann effektiv zwischengespeichert werden), so dass sie zum Prozessor streamen genau die Datenmenge, die es verarbeiten kann. Der andere Aspekt ist die Vektorisierung. Sie verwenden die vektorisierten Anweisungen des Prozessors für einen optimalen Befehlsdurchsatz, was Sie mit Ihrem plattformübergreifenden C ++ - Code nicht wirklich tun können.Schließlich sind Leute, die behaupten, es liege am Strassen- oder Coppersmith-Winograd-Algorithmus, falsch. Beide Algorithmen sind aufgrund der oben genannten Hardware-Überlegungen in der Praxis nicht implementierbar.
quelle
Deshalb . MATLAB führt keine naive Matrixmultiplikation durch, indem jedes einzelne Element wie in Ihrem C ++ - Code durchlaufen wird.
Natürlich gehe ich davon aus, dass Sie nur
C=A*B
eine Multiplikationsfunktion verwendet haben, anstatt sie selbst zu schreiben.quelle
Matlab hat LAPACK vor einiger Zeit integriert, daher gehe ich davon aus, dass ihre Matrixmultiplikation etwas verwendet, das mindestens so schnell ist. LAPACK-Quellcode und Dokumentation sind sofort verfügbar.
Sie können sich auch Goto und Van De Geijns Artikel "Anatomy of High-Performance Matrix Multiplication" unter http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.1785&rep=rep1&type=pdf ansehen
quelle
Die Antwort lautet LAPACK und BLAS- Bibliotheken machen MATLAB bei Matrixoperationen unglaublich schnell, nicht irgendeinen proprietären Code von den Leuten bei MATLAB.
Verwenden Sie die LAPACK- und / oder BLAS- Bibliotheken in Ihrem C ++ - Code für Matrixoperationen, und Sie sollten eine ähnliche Leistung wie MATLAB erhalten. Diese Bibliotheken sollten auf jedem modernen System frei verfügbar sein, und Teile wurden über Jahrzehnte in der Wissenschaft entwickelt. Beachten Sie, dass es mehrere Implementierungen gibt, einschließlich einiger geschlossener Quellen wie Intel MKL .
Eine Diskussion darüber, wie BLAS eine hohe Leistung erzielt, finden Sie hier.
Übrigens ist es meiner Erfahrung nach ein schwerer Schmerz, LAPACK-Bibliotheken direkt von c aus aufzurufen (aber es lohnt sich). Sie müssen die Dokumentation SEHR genau lesen.
quelle
Wenn Sie eine Matrixmultiplikation durchführen, verwenden Sie eine naive Multiplikationsmethode, die einige Zeit in Anspruch nimmt
O(n^3)
.Es gibt einen Matrixmultiplikationsalgorithmus, der benötigt
O(n^2.4)
. Dies bedeutet, dass bein=2000
Ihrem Algorithmus ~ 100-mal so viel Rechenaufwand erforderlich ist wie beim besten Algorithmus.Weitere Informationen zu den effizienten Implementierungsmethoden finden Sie auf der Wikipedia-Seite zur Matrixmultiplikation.
quelle
Abhängig von Ihrer Matlab-Version wird Ihre GPU möglicherweise bereits verwendet.
Etwas anderes; Matlab verfolgt viele Eigenschaften Ihrer Matrix. ob seine Diagonale, Hermetian und so weiter, und spezialisiert seine darauf basierenden Algorithmen. Vielleicht ist es auf die Nullmatrix spezialisiert, die Sie übergeben, oder so ähnlich? Vielleicht werden wiederholte Funktionsaufrufe zwischengespeichert, was Ihre Timings durcheinander bringt? Vielleicht optimiert es wiederholte unbenutzte Matrixprodukte?
Verwenden Sie eine Matrix aus Zufallszahlen, um solche Ereignisse zu vermeiden, und stellen Sie sicher, dass Sie die Ausführung erzwingen, indem Sie das Ergebnis auf einen Bildschirm, eine Festplatte oder ähnliches drucken.
quelle
A.*B
sie. Das OP vermasselt also mit ziemlicher Sicherheit etwas.MATLAB verwendet eine hochoptimierte Implementierung von LAPACK von Intel, die als Intel Math Kernel Library (Intel MKL) bekannt ist - speziell die dgemm-Funktion . Die Geschwindigkeit Diese Bibliothek nutzt Prozessorfunktionen wie SIMD-Anweisungen und Mehrkernprozessoren. Sie dokumentieren nicht, welchen spezifischen Algorithmus sie verwenden. Wenn Sie Intel MKL von C ++ aus aufrufen, sollten Sie eine ähnliche Leistung sehen.
Ich bin nicht sicher, welche Bibliothek MATLAB für die GPU-Multiplikation verwendet, aber wahrscheinlich so etwas wie nVidia CUBLAS .
quelle
Die allgemeine Antwort auf "Warum kann matlab xxx schneller ausführen als andere Programme" lautet, dass matlab viele integrierte, optimierte Funktionen hat.
Die anderen Programme, die häufig verwendet werden, verfügen nicht über diese Funktionen, sodass Benutzer ihre eigenen kreativen Lösungen anwenden, die überraschend langsamer sind als professionell optimierter Code.
Dies kann auf zwei Arten interpretiert werden:
1) Der übliche / theoretische Weg: Matlab ist nicht wesentlich schneller, Sie machen nur den Benchmark falsch
2) Der realistische Weg: Für dieses Zeug ist Matlab in der Praxis schneller, weil Sprachen wie c ++ auf ineffektive Weise einfach zu leicht verwendet werden.
quelle
Der scharfe Kontrast ist nicht nur auf die erstaunliche Optimierung von Matlab zurückzuführen (wie bereits in vielen anderen Antworten erläutert), sondern auch auf die Art und Weise, wie Sie die Matrix als Objekt formuliert haben.
Es scheint, als hätten Sie Matrix zu einer Liste von Listen gemacht? Eine Liste von Listen enthält Zeiger auf Listen, die dann Ihre Matrixelemente enthalten. Die Positionen der enthaltenen Listen werden willkürlich zugewiesen. Während Sie Ihren ersten Index (Zeilennummer?) Durchlaufen, ist die Zeit des Speicherzugriffs sehr wichtig. Warum versuchen Sie im Vergleich nicht, die Matrix mit der folgenden Methode als einzelne Liste / Vektor zu implementieren?
Und
Der gleiche Multiplikationsalgorithmus sollte verwendet werden, damit die Anzahl der Flops gleich ist. (n ^ 3 für quadratische Matrizen der Größe n)
Ich bitte Sie, die Zeit so festzulegen, dass das Ergebnis mit dem vergleichbar ist, das Sie zuvor hatten (auf demselben Computer). Mit dem Vergleich zeigen Sie genau, wie wichtig die Speicherzugriffszeit sein kann!
quelle
In C ++ ist es langsam, weil Sie kein Multithreading verwenden. Wenn A = BC ist, wo sie alle Matrizen sind, kann die erste Reihe von A unabhängig von der zweiten Reihe usw. berechnet werden. Wenn A, B und C alle n mal n Matrizen sind, können Sie die Multiplikation um beschleunigen ein Faktor von n ^ 2, as
a_ {i, j} = sum_ {k} b_ {i, k} c_ {k, j}
Wenn Sie beispielsweise Eigen [ http://eigen.tuxfamily.org/dox/GettingStarted.html ] verwenden, ist Multithreading integriert und die Anzahl der Threads kann angepasst werden.
quelle
Denn MATLAB ist eine Programmiersprache, die zunächst für die numerische lineare Algebra (Matrixmanipulationen) entwickelt wurde und über Bibliotheken verfügt, die speziell für Matrixmultiplikationen entwickelt wurden. Und jetzt kann MATLAB auch zusätzlich die GPUs (Graphics Processing Unit) verwenden .
Und wenn wir uns Ihre Berechnungsergebnisse ansehen:
dann können wir sehen, dass nicht nur MATLAB bei der Matrixmultiplikation so schnell ist: CUDA C (Programmiersprache von NVIDIA) hat einige bessere Ergebnisse als MATLAB. CUDA C hat auch Bibliotheken, die speziell für Matrixmultiplikationen entwickelt wurden, und verwendet die GPUs.
Kurze Geschichte von MATLAB
Was ist CUDA C.
CUDA C verwendet auch Bibliotheken, die speziell für Matrixmultiplikationen wie OpenGL (Open Graphics Library) entwickelt wurden. Es verwendet auch GPU und Direct3D (unter MS Windows).
Vergleichen der CPU- und GPU-Ausführungsgeschwindigkeiten
Aus der Einführung zum CUDA C-Programmierhandbuch:
Fortgeschrittenes Lesen
Grundlegende lineare Algebra-Unterprogramme (BLAS)
Anatomie der Hochleistungsmatrixmultiplikation von Kazushige Goto und Robert A. Van De Geijn
Einige interessante Facs
quelle
"additionally"
. Es bedeutet: es kann verwendet werden. Dies bedeutet auch, dass bei der normalen Matrixmultiplikation weiterhin Softwarebibliotheken verwendet werden. Denkst du, ich muss meinen Beitrag ändern, um verständlicher zu werden? Vielen Dank für Ihre Kommentare!