Sto cercando un modo più veloce e più complicato per moltiplicare due matrici 4x4 in C. La mia ricerca attuale si concentra sull'assemblaggio x86-64 con estensioni SIMD. Finora, ho creato una funzione che è circa 6 volte più veloce di un'ingenua implementazione C, che ha superato le mie aspettative per il miglioramento delle prestazioni. Sfortunatamente, questo rimane vero solo quando non vengono utilizzati flag di ottimizzazione per la compilazione (GCC 4.7). Con -O2 , C diventa più veloce e il mio sforzo diventa insignificante.
So che i compilatori moderni fanno uso di complesse tecniche di ottimizzazione per ottenere un codice quasi perfetto, di solito più veloce di un ingegnoso pezzo di assemblaggio artigianale. Ma in una minoranza di casi critici per le prestazioni, un essere umano può provare a lottare per i cicli di clock con il compilatore. Soprattutto quando è possibile esplorare alcune matematiche supportate da un moderno ISA (come nel mio caso).
La mia funzione ha il seguente aspetto (sintassi AT&T, 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
Calcola un'intera colonna della matrice risultante per iterazione, elaborando quattro float impacchettati in registri SSE a 128 bit. La vettorializzazione completa è possibile con un po' di matematica (operazione di riordino e aggregazione) e mullps /addps istruzioni per la moltiplicazione/addizione parallela di pacchetti 4xfloat. Il codice riutilizza i registri destinati al passaggio dei parametri (%rdi , %rsi , %rdx :GNU/Linux ABI), beneficia dello srotolamento del ciclo (interno) e mantiene una matrice interamente nei registri XMM per ridurre le letture della memoria. Come puoi vedere, ho studiato l'argomento e mi sono preso il mio tempo per implementarlo al meglio.
L'ingenuo calcolo C che conquista il mio codice è simile a questo:
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]);
}
Ho studiato l'output di assembly ottimizzato del codice C di cui sopra che, mentre memorizza i float nei registri XMM, non implica alcuna operazione parallela – solo calcoli scalari, aritmetica del puntatore e salti condizionali. Il codice del compilatore sembra essere meno deliberato, ma è comunque leggermente più efficace della mia versione vettorializzata che dovrebbe essere circa 4 volte più veloce. Sono sicuro che l'idea generale è corretta:i programmatori fanno cose simili con risultati gratificanti. Ma cosa c'è che non va qui? Ci sono problemi di allocazione del registro o di programmazione delle istruzioni di cui non sono a conoscenza? Conoscete strumenti o trucchi per l'assemblaggio x86-64 per supportare la mia battaglia contro la macchina?
Risposte:
C'è un modo per accelerare il codice e superare il compilatore. Non comporta alcuna sofisticata analisi della pipeline o una profonda microottimizzazione del codice (il che non significa che non possa trarne ulteriore vantaggio). L'ottimizzazione utilizza tre semplici trucchi:
-
La funzione è ora allineata a 32 byte (che ha notevolmente migliorato le prestazioni),
-
Il ciclo principale va inversamente, il che riduce il confronto a un test zero (basato su EFLAGS),
-
L'aritmetica degli indirizzi a livello di istruzione si è rivelata più veloce del calcolo del puntatore "esterno" (anche se richiede il doppio delle addizioni «in 3/4 casi»). Ha accorciato il corpo del ciclo di quattro istruzioni e ridotto le dipendenze dei dati all'interno del suo percorso di esecuzione. Vedi domanda correlata.
Inoltre, il codice utilizza una sintassi di salto relativo che sopprime l'errore di ridefinizione del simbolo, che si verifica quando GCC tenta di integrarlo (dopo essere stato inserito all'interno di asm dichiarazione e compilato con -O3 ).
.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
Questa è l'implementazione x86-64 più veloce che ho visto finora. Apprezzerò, voterò e accetterò qualsiasi risposta che fornisca un montaggio più rapido a tale scopo!