Multiplication efficace de la matrice 4x4 (C vs assemblage)
Je suis à la recherche d'une plus rapide et plus délicat moyen de multiplier deux matrices 4x4 dans C. Ma recherche actuelle est axée sur l'architecture x86-64 assemblée avec des extensions SIMD. Jusqu'à présent, j'ai créé une fonction qui est d'environ 6x plus rapide que le naïf C mise en œuvre, qui a dépassé mes attentes pour l'amélioration de la performance. Malheureusement, cela reste vrai que si aucune options d'optimisation sont utilisés pour la compilation (GCC 4.7). Avec -O2C est plus rapide et mon effort devient vide de sens.
Je sais que les compilateurs modernes utilisent des complexes techniques d'optimisation pour atteindre un presque parfait code, généralement plus rapide qu'un ingénieux morceau de main-crafed de l'assemblée. Mais dans une minorité de critiques des performances des cas, un homme peut essayer de se battre pour les cycles d'horloge avec le compilateur. En particulier, lorsque certains de mathématiques soutenu avec un moderne ISA peuvent être explorées (comme c'est mon cas).
Ma fonction se présente comme suit (AT&T de la syntaxe, de l'Assembleur GNU):
.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, .-matrixMultiplyASMIl calcule l'ensemble de la colonne de la matrice résultante par itération, par le traitement de quatre chars, emballés dans des 128 bits des registres SSE. Le plein de vectorisation est possible avec un peu de maths (opération de réorganisation et de regroupement) et mullps/addps instructions en parallèle de multiplication/addition de 4xfloat paquets. Le code réutilise les registres signifiait pour passer des paramètres (%rdi%rsi%rdx : GNU/Linux ABI), des avantages de (intérieure) déroulement de la boucle et est titulaire d'une matrice entièrement dans les registres XMM afin de réduire les lectures de mémoire. Vous pouvez le voir, j'ai étudié le sujet et pris mon temps pour mettre en œuvre le mieux que je peux.
Le naïf C calcul de la conquête de mon code ressemble à ceci:
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]);
}J'ai étudié l'optimisation de l'assemblée de la sortie de la ci-dessus du code C qui, tout en stockant les flotteurs dans les registres XMM, n'implique pas en parallèle des opérations de – juste scalaire des calculs, de l'arithmétique des pointeurs et des sauts conditionnels. Le compilateur de code semble être moins délibérée, mais il est encore un peu plus efficace que mon vectorisées version devrait être d'environ 4x plus rapide. Je suis sûr que l'idée générale est correcte – programmeurs de faire des choses similaires avec des résultats satisfaisants. Mais quel est le problème ici? Il n'existe aucun registre de l'allocation ou de la planification d'instructions questions, je ne suis pas au courant? Savez-vous tout x86-64 outils de montage ou des astuces pour appuyer mon combat contre la machine?
source d'informationauteur Krzysztof Abramowicz
Vous devez vous connecter pour publier un commentaire.
4x4 de multiplication de matrice est de 64 multiplications et 48 ajouts. À l'aide de l'ESS cela peut être réduite à 16 multiplications et 12 ajouts (et 16 diffusions). Le code suivant va le faire pour vous. Il exige seulement de l'ESS (
#include <xmmintrin.h>). Les tableauxABetCdoivent être de 16 octets aligné. Utilisant les instructions commehadd(SSE3) etdpps(SSE4.1) sera de moins en moins efficace (surtoutdpps). Je ne sais pas si le déroulement de la boucle de l'aide.Il y a un moyen d'accélérer le code et dominer le compilateur. Elle n'implique pas d'sophistiqué analyse du pipeline ou de la profondeur du code de la micro-optimisation (ce qui ne veut pas dire qu'il ne pouvait pas continuer à bénéficier de ces). L'optimisation utilise trois trucs simples:
La fonction est maintenant de 32 octets aligné (qui a fortement contribué à la performance),
Boucle principale va à l'inverse, ce qui réduit la comparaison à un test zéro (basé sur EFLAGS),
Niveau d'Instruction à l'adresse de l'arithmétique s'est avéré être plus rapide que les "externes" pointeur de calcul (même si elle nécessite deux fois plus d'ajouts «dans 3/4 des cas»). Il réduit le corps de la boucle par quatre des instructions et des données réduit les dépendances au sein de son chemin d'exécution. Voir la question relative à la.
En outre, le code utilise une relative sauter syntaxe qui supprime le symbole de la redéfinition de l'erreur qui se produit lors de la GCC essaie de l'inclure (après avoir été placé dans
asmdéclaration et compilé avec-O3).C'est le plus rapide x86-64 mise en œuvre que j'ai vu jusqu'à présent. Je vais apprécier, de voter et d'accepter de répondre en fournissant une plus morceau de l'assemblée à cet effet!
Je me demande si la transposition de l'une des matrices peut être bénéfique.
Demander comment multiplier deux matrices ...
Cela aurait pour conséquence ...
En faisant le produit scalaire d'une ligne et d'une colonne est une douleur.
Que faire si nous avons transposé la deuxième matrice avant nous avons multiplié?
Maintenant, au lieu de faire le produit scalaire d'une ligne et d'une colonne, nous faisons le produit scalaire de deux lignes. Cela pourrait se prêter à une meilleure utilisation des instructions SIMD.
Espère que cette aide.
Sandy Bridge au-dessus de prolonger le jeu d'instructions à l'appui de 8 élément de vecteur de l'arithmétique. Envisager cette mise en œuvre.
Évidemment, vous pouvez extraction de termes à partir de quatre matrices à un moment et multiplier les quatre matrices simultanément en utilisant le même algorithme.