Effiziente 4x4-Matrixmultiplikation (C vs Assembly)

Effiziente 4x4-Matrixmultiplikation (C vs Assembly)


Ich suche nach einer schnelleren und kniffligeren Möglichkeit, zwei 4x4-Matrizen in C zu multiplizieren. Meine aktuelle Forschung konzentriert sich auf die x86-64-Assemblierung mit SIMD-Erweiterungen. Bisher habe ich eine Funktion erstellt, die etwa 6x schneller ist als eine naive C-Implementierung, was meine Erwartungen an die Leistungsverbesserung übertroffen hat. Leider gilt dies nur, wenn keine Optimierungs-Flags für die Kompilierung verwendet werden (GCC 4.7). Mit -O2 , C wird schneller und meine Anstrengung wird sinnlos.


Ich weiß, dass moderne Compiler komplexe Optimierungstechniken verwenden, um einen nahezu perfekten Code zu erreichen, der normalerweise schneller ist als ein ausgeklügeltes Stück handgefertigter Assemblierung. Aber in einigen leistungskritischen Fällen kann ein Mensch versuchen, mit dem Compiler um Taktzyklen zu kämpfen. Vor allem, wenn etwas Mathematik, die mit einer modernen ISA unterstützt wird, erforscht werden kann (wie es in meinem Fall der Fall ist).


Meine Funktion sieht wie folgt aus (AT&T-Syntax, GNU Assembler):


    .text
.globl matrixMultiplyASM
.type matrixMultiplyASM, @function
matrixMultiplyASM:
movaps (%rdi), %xmm0 # fetch the first matrix (use four registers)
movaps 16(%rdi), %xmm1
movaps 32(%rdi), %xmm2
movaps 48(%rdi), %xmm3
xorq %rcx, %rcx # reset (forward) loop iterator
.ROW:
movss (%rsi), %xmm4 # Compute four values (one row) in parallel:
shufps $0x0, %xmm4, %xmm4 # 4x 4FP mul's, 3x 4FP add's 6x mov's per row,
mulps %xmm0, %xmm4 # expressed in four sequences of 5 instructions,
movaps %xmm4, %xmm5 # executed 4 times for 1 matrix multiplication.
addq $0x4, %rsi
movss (%rsi), %xmm4 # movss + shufps comprise _mm_set1_ps intrinsic
shufps $0x0, %xmm4, %xmm4 #
mulps %xmm1, %xmm4
addps %xmm4, %xmm5
addq $0x4, %rsi # manual pointer arithmetic simplifies addressing
movss (%rsi), %xmm4
shufps $0x0, %xmm4, %xmm4
mulps %xmm2, %xmm4 # actual computation happens here
addps %xmm4, %xmm5 #
addq $0x4, %rsi
movss (%rsi), %xmm4 # one mulps operand fetched per sequence
shufps $0x0, %xmm4, %xmm4 # |
mulps %xmm3, %xmm4 # the other is already waiting in %xmm[0-3]
addps %xmm4, %xmm5
addq $0x4, %rsi # 5 preceding comments stride among the 4 blocks
movaps %xmm5, (%rdx,%rcx) # store the resulting row, actually, a column
addq $0x10, %rcx # (matrices are stored in column-major order)
cmpq $0x40, %rcx
jne .ROW
ret
.size matrixMultiplyASM, .-matrixMultiplyASM

Es berechnet eine ganze Spalte der resultierenden Matrix pro Iteration, indem es vier Gleitkommazahlen verarbeitet, die in 128-Bit-SSE-Register gepackt sind. Die vollständige Vektorisierung ist mit ein wenig Mathematik (Umordnung von Operationen und Aggregation) und mullps möglich /addps Anweisungen zur parallelen Multiplikation/Addition von 4xfloat-Paketen. Der Code verwendet Register, die für die Übergabe von Parametern vorgesehen sind (%rdi , %rsi , %rdx :GNU/Linux ABI), profitiert vom Aufrollen der (inneren) Schleife und hält eine Matrix vollständig in XMM-Registern, um Speicherlesevorgänge zu reduzieren. Wie Sie sehen, habe ich das Thema recherchiert und mir die Zeit genommen, es so gut wie möglich umzusetzen.


Die naive C-Berechnung, die meinen Code erobert, sieht so aus:


void matrixMultiplyNormal(mat4_t *mat_a, mat4_t *mat_b, mat4_t *mat_r) {
for (unsigned int i = 0; i < 16; i += 4)
for (unsigned int j = 0; j < 4; ++j)
mat_r->m[i + j] = (mat_b->m[i + 0] * mat_a->m[j + 0])
+ (mat_b->m[i + 1] * mat_a->m[j + 4])
+ (mat_b->m[i + 2] * mat_a->m[j + 8])
+ (mat_b->m[i + 3] * mat_a->m[j + 12]);
}

Ich habe die optimierte Assembly-Ausgabe des obigen C-Codes untersucht, der zwar Floats in XMM-Registern speichert, aber keine parallelen Operationen beinhaltet – nur skalare Berechnungen, Zeigerarithmetik und bedingte Sprünge. Der Code des Compilers scheint weniger absichtlich zu sein, aber er ist immer noch etwas effektiver als meine vektorisierte Version, die ungefähr 4x schneller sein sollte. Ich bin sicher, dass die allgemeine Idee richtig ist – Programmierer machen ähnliche Dinge mit lohnenden Ergebnissen. Aber was ist hier falsch? Gibt es irgendwelche Registerzuordnungs- oder Unterrichtsplanungsprobleme, die mir nicht bekannt sind? Kennen Sie x86-64-Assembler-Tools oder -Tricks, um meinen Kampf gegen die Maschine zu unterstützen?


Antworten:


Es gibt eine Möglichkeit, den Code zu beschleunigen und den Compiler auszuspielen. Es beinhaltet keine ausgefeilte Pipeline-Analyse oder Deep-Code-Mikrooptimierung (was nicht bedeutet, dass es nicht weiter davon profitieren könnte). Die Optimierung nutzt drei einfache Tricks:



  1. Die Funktion ist jetzt auf 32 Byte ausgerichtet (was die Leistung erheblich steigerte),


  2. Die Hauptschleife verläuft umgekehrt, was den Vergleich auf einen Nulltest (basierend auf EFLAGS) reduziert,


  3. Die Adressarithmetik auf Befehlsebene erwies sich als schneller als die "externe" Zeigerberechnung (obwohl sie «in 3/4 Fällen» doppelt so viele Additionen erfordert). Es verkürzte den Schleifenkörper um vier Anweisungen und reduzierte Datenabhängigkeiten innerhalb seines Ausführungspfads. Siehe verwandte Frage.



Darüber hinaus verwendet der Code eine relative Sprungsyntax, die den Symbolneudefinitionsfehler unterdrückt, der auftritt, wenn GCC versucht, es einzubetten (nachdem es in asm platziert wurde -Anweisung und mit -O3 kompiliert ).


    .text
.align 32 # 1. function entry alignment
.globl matrixMultiplyASM # (for a faster call)
.type matrixMultiplyASM, @function
matrixMultiplyASM:
movaps (%rdi), %xmm0
movaps 16(%rdi), %xmm1
movaps 32(%rdi), %xmm2
movaps 48(%rdi), %xmm3
movq $48, %rcx # 2. loop reversal
1: # (for simpler exit condition)
movss (%rsi, %rcx), %xmm4 # 3. extended address operands
shufps $0, %xmm4, %xmm4 # (faster than pointer calculation)
mulps %xmm0, %xmm4
movaps %xmm4, %xmm5
movss 4(%rsi, %rcx), %xmm4
shufps $0, %xmm4, %xmm4
mulps %xmm1, %xmm4
addps %xmm4, %xmm5
movss 8(%rsi, %rcx), %xmm4
shufps $0, %xmm4, %xmm4
mulps %xmm2, %xmm4
addps %xmm4, %xmm5
movss 12(%rsi, %rcx), %xmm4
shufps $0, %xmm4, %xmm4
mulps %xmm3, %xmm4
addps %xmm4, %xmm5
movaps %xmm5, (%rdx, %rcx)
subq $16, %rcx # one 'sub' (vs 'add' & 'cmp')
jge 1b # SF=OF, idiom: jump if positive
ret

Dies ist die schnellste x86-64-Implementierung, die ich bisher gesehen habe. Ich werde jede Antwort schätzen, abstimmen und akzeptieren, die eine schnellere Montage für diesen Zweck ermöglicht!