Schnell 4x4 Matrixmultiplikation in C
https://stackoverflow.com/questions/1674005
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, eine optimierte C oder Assembler Implementierung einer Funktion zu finden, die zwei 4x4 Matrizen miteinander multipliziert. Die Plattform ist eine ARM6 oder ARM7 basierte iPhone oder iPod.
Derzeit bin ich ein ziemlich Standard-Ansatz -. Nur ein wenig schlaufen abgerollt
#define O(y,x) (y + (x<<2))
static inline void Matrix4x4MultiplyBy4x4 (float *src1, float *src2, float *dest)
{
*(dest+O(0,0)) = (*(src1+O(0,0)) * *(src2+O(0,0))) + (*(src1+O(0,1)) * *(src2+O(1,0))) + (*(src1+O(0,2)) * *(src2+O(2,0))) + (*(src1+O(0,3)) * *(src2+O(3,0)));
*(dest+O(0,1)) = (*(src1+O(0,0)) * *(src2+O(0,1))) + (*(src1+O(0,1)) * *(src2+O(1,1))) + (*(src1+O(0,2)) * *(src2+O(2,1))) + (*(src1+O(0,3)) * *(src2+O(3,1)));
*(dest+O(0,2)) = (*(src1+O(0,0)) * *(src2+O(0,2))) + (*(src1+O(0,1)) * *(src2+O(1,2))) + (*(src1+O(0,2)) * *(src2+O(2,2))) + (*(src1+O(0,3)) * *(src2+O(3,2)));
*(dest+O(0,3)) = (*(src1+O(0,0)) * *(src2+O(0,3))) + (*(src1+O(0,1)) * *(src2+O(1,3))) + (*(src1+O(0,2)) * *(src2+O(2,3))) + (*(src1+O(0,3)) * *(src2+O(3,3)));
*(dest+O(1,0)) = (*(src1+O(1,0)) * *(src2+O(0,0))) + (*(src1+O(1,1)) * *(src2+O(1,0))) + (*(src1+O(1,2)) * *(src2+O(2,0))) + (*(src1+O(1,3)) * *(src2+O(3,0)));
*(dest+O(1,1)) = (*(src1+O(1,0)) * *(src2+O(0,1))) + (*(src1+O(1,1)) * *(src2+O(1,1))) + (*(src1+O(1,2)) * *(src2+O(2,1))) + (*(src1+O(1,3)) * *(src2+O(3,1)));
*(dest+O(1,2)) = (*(src1+O(1,0)) * *(src2+O(0,2))) + (*(src1+O(1,1)) * *(src2+O(1,2))) + (*(src1+O(1,2)) * *(src2+O(2,2))) + (*(src1+O(1,3)) * *(src2+O(3,2)));
*(dest+O(1,3)) = (*(src1+O(1,0)) * *(src2+O(0,3))) + (*(src1+O(1,1)) * *(src2+O(1,3))) + (*(src1+O(1,2)) * *(src2+O(2,3))) + (*(src1+O(1,3)) * *(src2+O(3,3)));
*(dest+O(2,0)) = (*(src1+O(2,0)) * *(src2+O(0,0))) + (*(src1+O(2,1)) * *(src2+O(1,0))) + (*(src1+O(2,2)) * *(src2+O(2,0))) + (*(src1+O(2,3)) * *(src2+O(3,0)));
*(dest+O(2,1)) = (*(src1+O(2,0)) * *(src2+O(0,1))) + (*(src1+O(2,1)) * *(src2+O(1,1))) + (*(src1+O(2,2)) * *(src2+O(2,1))) + (*(src1+O(2,3)) * *(src2+O(3,1)));
*(dest+O(2,2)) = (*(src1+O(2,0)) * *(src2+O(0,2))) + (*(src1+O(2,1)) * *(src2+O(1,2))) + (*(src1+O(2,2)) * *(src2+O(2,2))) + (*(src1+O(2,3)) * *(src2+O(3,2)));
*(dest+O(2,3)) = (*(src1+O(2,0)) * *(src2+O(0,3))) + (*(src1+O(2,1)) * *(src2+O(1,3))) + (*(src1+O(2,2)) * *(src2+O(2,3))) + (*(src1+O(2,3)) * *(src2+O(3,3)));
*(dest+O(3,0)) = (*(src1+O(3,0)) * *(src2+O(0,0))) + (*(src1+O(3,1)) * *(src2+O(1,0))) + (*(src1+O(3,2)) * *(src2+O(2,0))) + (*(src1+O(3,3)) * *(src2+O(3,0)));
*(dest+O(3,1)) = (*(src1+O(3,0)) * *(src2+O(0,1))) + (*(src1+O(3,1)) * *(src2+O(1,1))) + (*(src1+O(3,2)) * *(src2+O(2,1))) + (*(src1+O(3,3)) * *(src2+O(3,1)));
*(dest+O(3,2)) = (*(src1+O(3,0)) * *(src2+O(0,2))) + (*(src1+O(3,1)) * *(src2+O(1,2))) + (*(src1+O(3,2)) * *(src2+O(2,2))) + (*(src1+O(3,3)) * *(src2+O(3,2)));
*(dest+O(3,3)) = (*(src1+O(3,0)) * *(src2+O(0,3))) + (*(src1+O(3,1)) * *(src2+O(1,3))) + (*(src1+O(3,2)) * *(src2+O(2,3))) + (*(src1+O(3,3)) * *(src2+O(3,3)));
};
Würde ich profitiere von dem Strassen- oder über den Kupferschmied-Winograd-Algorithmus?
Lösung
Nein, die Strassen oder Kupferschmiede-Winograd-Algorithmus würde hier nicht machen viel Unterschied. Sie beginnen nur für größere Matrizen zu tilgen.
Wenn Sie Ihre Matrix-Multiplikation ist wirklich ein Engpass Sie den Algorithmus unter Verwendung von NEON SIMD-Befehle umschreiben könnte. Das würde nur für ARMv7 helfen als ARMv6 diese Erweiterung nicht jedoch hat.
würde ich einen Faktor 3 Speedup über die kompilierte C-Code für Ihren Fall erwarten.
EDIT: Sie können eine schöne Umsetzung in ARM-NEON finden Sie hier: http: // Code .google.com / p / math-Neon /
Für Ihren C-Code gibt es zwei Dinge, die Sie den Code zu beschleunigen tun könnten:
-
Sie nicht die Funktion inline. Ihre Matrix-Multiplikation erzeugt ein ziemlich viel Code, wie es abgerollt ist, und die ARM hat nur einen sehr kleinen Befehlscache. Übermäßige inlining kann Ihr Code langsamer machen, da die CPU beschäftigt Ladecode in den Cache sein wird, anstatt sie auszuführen.
-
Mit dem beschränken Schlüsselwort den Compiler zu sagen, dass die Quell- und Zielzeiger nicht überlappen im Speicher. Zur Zeit der Compiler gezwungen ist, jeden Quellwert aus dem Speicher zu laden, wenn ein Ergebnis geschrieben wird, weil es diese Quelle zu übernehmen hat und das Ziel kann auf den gleichen Speicher überlappen oder zeigen sogar.
Andere Tipps
Just Erbsenzählerei. Ich frage mich, warum Menschen immer noch voluntarly ihren Code zu verschleiern? C schon schwer zu lesen ist, keine Notwendigkeit, etwas hinzufügen.
static inline void Matrix4x4MultiplyBy4x4 (float src1[4][4], float src2[4][4], float dest[4][4])
{
dest[0][0] = src1[0][0] * src2[0][0] + src1[0][1] * src2[1][0] + src1[0][2] * src2[2][0] + src1[0][3] * src2[3][0];
dest[0][1] = src1[0][0] * src2[0][1] + src1[0][1] * src2[1][1] + src1[0][2] * src2[2][1] + src1[0][3] * src2[3][1];
dest[0][2] = src1[0][0] * src2[0][2] + src1[0][1] * src2[1][2] + src1[0][2] * src2[2][2] + src1[0][3] * src2[3][2];
dest[0][3] = src1[0][0] * src2[0][3] + src1[0][1] * src2[1][3] + src1[0][2] * src2[2][3] + src1[0][3] * src2[3][3];
dest[1][0] = src1[1][0] * src2[0][0] + src1[1][1] * src2[1][0] + src1[1][2] * src2[2][0] + src1[1][3] * src2[3][0];
dest[1][1] = src1[1][0] * src2[0][1] + src1[1][1] * src2[1][1] + src1[1][2] * src2[2][1] + src1[1][3] * src2[3][1];
dest[1][2] = src1[1][0] * src2[0][2] + src1[1][1] * src2[1][2] + src1[1][2] * src2[2][2] + src1[1][3] * src2[3][2];
dest[1][3] = src1[1][0] * src2[0][3] + src1[1][1] * src2[1][3] + src1[1][2] * src2[2][3] + src1[1][3] * src2[3][3];
dest[2][0] = src1[2][0] * src2[0][0] + src1[2][1] * src2[1][0] + src1[2][2] * src2[2][0] + src1[2][3] * src2[3][0];
dest[2][1] = src1[2][0] * src2[0][1] + src1[2][1] * src2[1][1] + src1[2][2] * src2[2][1] + src1[2][3] * src2[3][1];
dest[2][2] = src1[2][0] * src2[0][2] + src1[2][1] * src2[1][2] + src1[2][2] * src2[2][2] + src1[2][3] * src2[3][2];
dest[2][3] = src1[2][0] * src2[0][3] + src1[2][1] * src2[1][3] + src1[2][2] * src2[2][3] + src1[2][3] * src2[3][3];
dest[3][0] = src1[3][0] * src2[0][0] + src1[3][1] * src2[1][0] + src1[3][2] * src2[2][0] + src1[3][3] * src2[3][0];
dest[3][1] = src1[3][0] * src2[0][1] + src1[3][1] * src2[1][1] + src1[3][2] * src2[2][1] + src1[3][3] * src2[3][1];
dest[3][2] = src1[3][0] * src2[0][2] + src1[3][1] * src2[1][2] + src1[3][2] * src2[2][2] + src1[3][3] * src2[3][2];
dest[3][3] = src1[3][0] * src2[0][3] + src1[3][1] * src2[1][3] + src1[3][2] * src2[2][3] + src1[3][3] * src2[3][3];
};
Sind Sie sicher, dass Ihr abgerollt Code schneller ist als die explizite Schleife basierten Ansatz? Beachten Sie, dass die Compiler sind in der Regel besser als die Menschen durchführen Optimierungen!
In der Tat, würde ich wette, es gibt mehr Chancen für einen Compiler aus einer gut geschrieben Schleife automatisch SIMD-Befehle zu emittieren als aus einer Reihe von „unabhängigen“ -Aussagen ...
Sie können auch die Matrizen Größen in der Argumentdeklaration angeben. Dann könnten Sie die normale Klammer-Syntax verwenden, um die Elemente zuzugreifen, und es könnte auch ein guter Hinweis für den Compiler zu auch seine Optimierungen zu machen.
Sind diese willkürlichen Matrizen oder haben sie keine Symmetrien? Wenn ja, können diese Symmetrien oft genutzt für eine verbesserte Leistung (zum Beispiel in Drehmatrizen).
Auch stimme ich oben mit Fortran, und würde einige Timing-Tests laufen, um sicherzustellen, dass Ihre Hand abgerollt Code ist schneller als ein optimierenden Compiler erstellen können. Zumindest können Sie in der Lage sein, Ihren Code zu vereinfachen.
Paul
Ihr vollständig abgerollt traditionelles Produkt ist wahrscheinlich ziemlich schnell.
Ihre Matrix ist zu klein, die eine Strassen Multiplikation in ihrer traditionellen Form der Verwaltung mit expliziten Indizes und Trenncodes belauscht zu überwinden; Sie würden wahrscheinlich keine Auswirkungen auf die Optimierung auf diese Overhead verlieren.
Aber wenn Sie schnell wünschen, würde ich SIMD-Befehle verwenden, wenn sie verfügbar sind. Ich wäre überrascht, wenn die ARM-Chips in diesen Tagen nicht in Anspruch genommen haben. Wenn sie das tun, können Sie alle Produkte in der Reihe / colum in einem einzigen Befehl verwalten; wenn der SIMD 8 breit ist, können Sie verwalten 2 Zeilen / Spalten-Multiplikationen in einem einzigen Befehl. Einstellen der Operanden auf, dass der Befehl tun könnte einige Tanzen benötigen um; SIMD-Befehle werden Ihre Reihen leicht abholen (benachbarte Werte), aber nicht die Spalten (nicht zusammenhängende) abholen. Und es kann einige Mühe, um die Summe der Produkte in einer Zeile / Spalte zu berechnen.
