Matrice rapide 4x4 en C Multiplication
https://stackoverflow.com/questions/1674005
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en train de trouver une implémentation C ou Assembleur optimisé d'une fonction qui multiplie deux matrices 4x4 avec l'autre. La plate-forme est un ARM6 ou ARM7 base iPhone ou iPod.
À l'heure actuelle, je suis en utilisant une approche assez classique -. Juste un peu en boucle déroula
#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)));
};
Est-ce que je peux bénéficier d'utiliser le Strassen- ou l'algorithme Chaudronnier-Winograd?
La solution
Non, l'algorithme Strassen ou Chaudronnier-Winograd ne changerait pas grand-chose ici. Ils commencent à payer pour les matrices plus grandes seulement.
Si votre matrice multiplication est vraiment un goulot d'étranglement, vous pouvez réécrire l'algorithme en utilisant des instructions SIMD NEON. Cela ne ferait qu'aider pour ARMv7 que ARMv6 ne possède cette extension bien.
J'attends un facteur 3 sur le C speedup-code compilé pour votre cas.
EDIT: Vous pouvez trouver une bonne implémentation dans ARM NEON ici: http: // Code .google.com / p / math-néon /
Pour votre code C, il y a deux choses que vous pouvez faire pour accélérer le code:
-
Ne pas la fonction inline. Votre multiplication matricielle génère un peu de code tel qu'il est déroulé, et l'ARM ne dispose que d'un cache d'instructions très petit. inline excessive peut rendre votre code plus lent parce que le CPU sera le code de chargement occupé dans le cache au lieu de l'exécuter.
-
Utilisez le mot-clé restreindre pour indiquer au compilateur que les pointeurs et la destination source-ne se chevauchent pas en mémoire. Actuellement, le compilateur est obligé de recharger chaque valeur source de la mémoire à chaque fois qu'un résultat est écrit parce qu'il doit supposer que la source et la destination peuvent se chevaucher ou même pointer vers la même mémoire.
Autres conseils
Juste tatillonne. Je me demande pourquoi les gens font qu'embrouiller encore leur code voluntarly? C est déjà difficile à lire, pas besoin d'y ajouter.
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];
};
Êtes-vous sûr que votre code est plus rapide que déroulé l'approche de la boucle explicite? L'esprit que les compilateurs sont généralement mieux que les humains d'effectuer des optimisations!
En fait, je parie qu'il ya plus de chances pour un compilateur d'émettre des instructions automatiquement SIMD d'une boucle bien écrit que d'une série de déclarations « non reliés » ...
Vous pouvez également spécifier les tailles de matrices dans la déclaration d'arguments. Ensuite, vous pouvez utiliser la syntaxe de support normale pour accéder aux éléments, et il pourrait aussi être un bon indice pour le compilateur de faire ses Optimisations aussi.
sont ces matrices arbitraires ou ils n'ont des symétries? Si oui, ces symétries peuvent souvent exploitées pour améliorer les performances (par exemple dans des matrices de rotation).
En outre, je suis d'accord avec Fortran ci-dessus, et courraient des tests chronométrés pour vérifier que votre code de main est déroula plus rapide qu'un compilateur optimisé peut créer. Au moins, vous pourriez être en mesure de simplifier votre code.
Paul
Votre produit traditionnel entièrement sorti probablement assez rapide.
Votre matrice est trop faible pour surmonter la Overheard de gérer une multiplication Strassen sous sa forme traditionnelle avec des indices explicites et le code de partitionnement; vous auriez probablement perdre aucun effet sur l'optimisation pour que les frais généraux.
Mais si vous voulez rapidement, j'utiliser des instructions SIMD si elles sont disponibles. Je serais surpris si les puces ARM ces jours-ci ne les ont pas. Si oui, vous pouvez gérer tous les produits en ligne / Colum en une seule instruction; si le SIMD est 8 large, vous pouvez gérer 2 multiplications ligne / colonne dans une seule instruction. Réglage des opérandes jusqu'à faire cette instruction pourrait nécessiter un peu de danse autour; instructions SIMD seront facilement récupérer vos lignes (valeurs adjacentes), mais ne seront pas ramasser les colonnes (non contiguës). Et il peut prendre un certain effort pour calculer la somme des produits dans une ligne / colonne.
