Optimierung der Matrix-Vektor-Multiplikation für viele kleine Matrizen

Ich möchte Matrix-Vektor-Produkte beschleunigen, aber alles, was ich lese, ist, wie man es für sehr große Matrizen macht. In meinem Fall sind die Matrizen klein, aber die Häufigkeit, mit der dies durchgeführt werden muss, ist sehr groß.

Welche Methoden gibt es, um diese zu optimieren? Wäre es schneller, eine wirklich große diagonale Blockmatrix aus den kleinen Matrizen und einem großen Vektor aus den kleineren Vektoren zu konstruieren und die Techniken für die Beschleunigung der großen Matrixvektoren zu verwenden? Oder würde das Einrichten der globalen Matrix und des Vektors dort irgendeinen Nutzen bringen?

linear-algebra optimization tpg2114
quelle

Müssen Sie dieselbe Matrix mit vielen Vektoren multiplizieren oder gibt es keine Wiederverwendung der Matrizen?

Brian Borchers

Ich bezweifle, dass die Verwendung der Techniken für große Matrizen für eine große Blockdiagonale zu einer deutlichen Beschleunigung führt. Wie klein ist in Ihrem Fall "klein" und über wie viele Matrizen sprechen wir normalerweise? Wissen Sie noch etwas über diese Matrizen, z. B. beschreiben sie Rotationen usw.?

Christian Waluga

@BrianBorchers Es gibt keine Wiederverwendung der Matrix, es ist für jeden Punkt jedes Mal anders

tpg2114

@ChristianWaluga Sie sind manchmal 5x5 bis vielleicht 10x10, dicht, nicht symmetrisch und im Allgemeinen nicht diagonal dominant. Wie oft es durchgeführt werden muss,

hängt

Antworten:

Bevor Sie versuchen, Ihren Code zu optimieren, sollten Sie sich zunächst fragen, ob Sie etwas optimieren müssen. Bibliotheken, die Matrix-Vektor-Produkte optimieren, umgehen dabei zwei Probleme: Einschränkungen bei der Größe des Caches und die Latenz beim Laden von Daten aus dem Speicher. Zum einen werden die Daten, die sich derzeit im Cache befinden, in vollem Umfang für alles verwendet, wofür sie verwendet werden müssen, bevor sie durch andere Daten ersetzt werden. Zum anderen werden Daten vorab in den Cache abgerufen, bevor sie tatsächlich verwendet werden.

In Ihrem Fall haben Sie eine relativ geringe arithmetische Intensität Ihrer Daten - Sie laden Daten aus dem Speicher, verwenden sie genau einmal und fahren dann mit der nächsten Matrix fort. Damit bleibt nur der zweite Weg zur Optimierung: Vorabruf von Daten, bevor Sie sie verwenden.

Aber wie gesagt, bevor Sie versuchen, die Dinge zu optimieren, kann es sich lohnen, herauszufinden, was Sie bereits haben: Zeit, wie viele Matrixvektorprodukte Sie pro Sekunde ausführen, berechnen Sie, wie viele Bytes erforderlich sind, um aus dem Speicher auf Ihren Prozessor zu laden. und vergleichen Sie dies dann mit der Bandbreite des Prozessors, den Sie zufällig in Ihrem Computer haben. Möglicherweise stellen Sie fest, dass Sie nichts tun können, um die Dinge schneller zu machen.

Wolfgang Bangerth
quelle

Es kann nicht wirklich Angelegenheit , da Ihre Matrizen Cache bereits enthalten ist , aber Sie sollten anrufen dgemv()oder sgemv()von der besten BLAS - Bibliothek oder das Äquivalent Sie Ihre Hände bekommen. Sie sollten die Intel MKL ausprobieren, wenn Sie Zugriff darauf erhalten können, sowie BLIS oder ATLAS oder eine der vielen anderen optimierten BLAS-Bibliotheken.

Bill Barth
quelle

Interessanterweise laufen die BLAS-Routinen in Fortran langsamer als die intrinsische MATMUL-Funktion, selbst bei MKL- und hardwarespezifischen Implementierungen.

tpg2114

Das überrascht mich nicht ganz, aber ich müsste den Code sehen, um es sicher zu wissen. Es gibt eine Reihe von Problemen, über die Sie sich Sorgen machen müssen. Ich würde vorschlagen müssen, die Ausrichtung Ihrer Arrays zu überprüfen, bevor Sie die MKL abschreiben, aber bei diesen kleinen Größen ist die MKL MATVEC möglicherweise nicht stark optimiert.

Bill Barth

Bill, ein Mitarbeiter von mir, stieß auf dasselbe Problem. Die Schlussfolgerung war, dass der MKL-Aufruf entweder einen nicht zu vernachlässigenden Overhead aufwies oder ansonsten für kleine Matrizen nicht gut optimiert war. In beiden Fällen war ein handgeschriebenes Matmul bei einer sehr großen Anzahl von 5x5-Matrixmultiplikationen erheblich schneller.

Aurelius

O (N^{2})

$O(N^2)$

O (N^{3})

$O(N^3)$

Wenn die Matrizen sehr klein sind (z. B. 4x4), versuchen Sie es mit einer der Vorlagenbibliotheken. Dadurch wird möglicherweise viel Aufwand für Funktionsaufrufe vermieden. Eigen ist ein guter Kandidat.

Damien

Das Generieren von C ++ - Code und die Verwendung von Eigen / Armadillo ist möglich, dies hängt jedoch von der Anwendung ab.

$N<8$

Achten Sie auf die Speicherausrichtung Ihrer Daten (bis zu 64 Byte ausgerichtet) und beschränken Sie die Zeiger, um dem Compiler das Leben zu erleichtern. Bei diesen Matrixgrößen muss keine Multicore-Unterstützung verwendet werden. Der Overhead ist größer als die Verstärkung.

Wir verwenden Scripting, um automatisch separate Funktionen für jede mögliche Kombination zu generieren und die Funktionszeiger für aufeinanderfolgende Aufrufe zwischenzuspeichern.

$N \geq 8$

Paul
quelle