Optimisé matrice de la multiplication dans C
Je suis en train de comparer les différentes méthodes de multiplication de matrice.
La première est la méthode normale:
do
{
for (j = 0; j < i; j++)
{
for (k = 0; k < i; k++)
{
suma = 0;
for (l = 0; l < i; l++)
suma += MatrixA[j][l]*MatrixB[l][k];
MatrixR[j][k] = suma;
}
}
}
c++;
} while (c<iteraciones);
Le second se composent de la transposition de la matrice B en premier et ensuite faire la multiplication par les lignes:
int f, co;
for (f = 0; f < i; f++) {
for ( co = 0; co < i; co++) {
MatrixB[f][co] = MatrixB[co][f];
}
}
c = 0;
do
{
for (j = 0; j < i; j++)
{
for (k = 0; k < i; k++)
{
suma = 0;
for (l = 0; l < i; l++)
suma += MatrixA[j][l]*MatrixB[k][l];
MatrixR[j][k] = suma;
}
}
}
c++;
} while (c<iteraciones);
La deuxième méthode censé être beaucoup plus rapide, parce que nous sommes accéder à la mémoire contiguë slots, mais je ne suis pas d'obtenir une amélioration significative de la performance. Suis-je en train de faire quelque chose de mal?
Je peux poster le code complet, mais je pense n'est pas nécessaire.
- Sauf si vous implémentez votre propre de la matrice de la multiplication des routines comme un exercice d'apprentissage, vous devriez sérieusement envisager d'utiliser un existant, de les contrôler, bibliothèque optimisée tels que BLAS ou LAPACK.
- Le premier fragment a 3
{
et 4}
. Mon impression est que le plus profond}
n'est pas voulu du tout, et la cessionMatrixR[j][k] = suma;
ne fait pas partie des intimesfor
boucle, malgré le retrait (de sorte qu'il est mis en retrait; elle doit être au même niveau quesuma = 0;
). - Cette réponse pourrait être utile: stackoverflow.com/a/54546544/3234205
Vous devez vous connecter pour publier un commentaire.
Ce Que Chaque Programmeur Doit Savoir À Propos De La Mémoire (lien pdf) par Ulrich Drepper a beaucoup de bonnes idées au sujet de l'efficacité de mémoire, mais en particulier, il utilise la multiplication de matrice comme un exemple de la façon dont savoir sur la mémoire et l'utilisation de cette connaissance peut accélérer ce processus. Regardez l'annexe A. 1 dans son livre, et lisez la section 6.2.1. Le tableau 6.2 dans le document montre qu'il pourrait obtenir les temps de fonctionnement de 10% à partir d'une implémentation naïve de temps pour 1000x1000 de la matrice.
Accordée, son code final est assez poilue et qui utilise beaucoup de choses spécifiques, et au moment de la compilation de réglage, mais encore, si vous vraiment besoin de vitesse, la lecture de ce livre et de la lecture de sa mise en œuvre est certainement la peine.
Obtenir ce droit peut être non négligeable. Une optimisation qui est d'une importance particulière pour les grandes matrices, c'est de carrelage, de la multiplication à tout garder dans le cache. Une fois, j'ai mesuré une 12x différence de performance de le faire, mais j'ai précisément choisi une matrice de taille qui ont consommé des multiples de mon cache (circa " 97 de sorte que le cache était petit).
Il y a un beaucoup de la littérature sur le sujet. Un point de départ:
http://en.wikipedia.org/wiki/Loop_tiling
Pour un plus en profondeur l'étude, les références, en particulier la Banerjee livres, peuvent être utiles:
[Ban93] Banerjee, Utpal, les Transformations de la Boucle pour la Restructuration des Compilateurs: les Fondations, Kluwer Academic Publishers, Norwell, MA, 1993.
[Ban94] Banerjee, Utpal, Boucle de Parallélisation, Kluwer Academic Publishers, Norwell, MA, 1994.
[BGS93] Bacon, David F., Susan L. Graham, et Oliver Forte, Compilateur Transformations de Calcul à Haute Performance, Ordinateur, Division des Sciences, de l'Université de Californie, Berkeley, Calif., Rapport technique No UCB/CDD-93-781.
[LRW91] Lam, Monica S., Edward E. Rothberg, et Michael E Loup. Le Cache de Performance et d'optimisation de blocage des Algorithmes, À la 4ème Conférence Internationale sur l'Appui d'Architecture pour les Langages de Programmation, a eu lieu à Santa Clara, Calif., Avril 1991, 63-74.
[LW91] Lam, Monica S., et Michael E Loup. Une Boucle de Transformation de la Théorie et de l'Algorithme afin de Maximiser le Parallélisme, Dans IEEE Transactions on Parallel and Distributed Systems, 1991, 2(4):452-471.
[PW86] Padoue, David A., et Michael J. Wolfe, Avancé les Optimisations du Compilateur pour les Supercalculateurs, Dans les Communications de l'ACM, 29(12):1184-1201, 1986.
[Wolfe89] Wolfe, Michael J. l'Optimisation de Supercompilers pour les Supercalculateurs, The MIT Press, Cambridge, MA, 1989.
[Wolfe96] Wolfe, Michael J., Haute Performance Compilateurs pour le Calcul Parallèle, Addison-Wesley, CA, 1996.
ATTENTION: Vous avez un BUG dans votre deuxième mise en œuvre
Lorsque vous ne f=0, c=1
vous écraser
MatrixB[0][1]
et perdre de la valeur! Lorsque la boucle est de f=1, c=0la valeur copiée est le même qui était déjà là.
for (f=0; f<i-1; f++) for (co=f+1; co<i; co++) swap(MatrixB[f]+co, MatrixB[co]+f);
Si la matrice n'est pas assez grand ou vous n'avez pas répéter les opérations qu'un grand nombre de fois, vous ne verrez pas de différences appréciables.
Si la matrice est, disons, 1,000x1,000 vous allez commencer à voir des améliorations, mais je dirais que si il est en dessous de 100x100 vous devriez vous inquiétez pas à ce sujet.
Aussi, toute "amélioration" peut être de l'ordre de quelques millisecondes, sauf en glissement annuel travaillent avec de très grandes matrices ou de renouveler l'opération des milliers de fois.
Enfin, si vous changez d'ordinateur que vous utilisez pour une plus rapide, les différences sont encore plus étroit!
Vous ne devriez pas écrire la matrice de multiplication. Vous devriez dépendent de bibliothèques externes. En particulier, vous devez utiliser le
GEMM
de routine de laBLAS
de la bibliothèque. GEMM fournit souvent les optimisations suivantesBlocage
Efficace de Multiplication de Matrice repose sur le blocage de votre matrice et l'exécution de plusieurs petites bloqué multiplie. Idéalement, la taille de chaque bloc est choisi afin de s'intégrer parfaitement dans le cache améliorant considérablement les performances.
Tuning
L'idéal de la taille du bloc dépend de la sous-jacentes de hiérarchie mémoire (quelle est la taille du cache?). Comme un résultat, les bibliothèques devraient être à l'écoute et compilées pour chaque machine. C'est fait, entre autres, par la
ATLAS
mise en œuvre deBLAS
.Niveau De L'Assemblée Optimisation
Matrice multiplicaiton est si commune que les développeurs d'optimiser à la main. En particulier, ce qui est fait dans
GotoBLAS
.Hétérogène(GPU) de Calcul
Multiplier la matrice est très FLOP/calcul intensif, faisant de lui un candidat idéal pour être exécuté sur les Gpu.
cuBLAS
etMAGMA
sont de bons candidats pour cette.En bref, de la densité de l'algèbre linéaire est un bien étudié le sujet. Les gens consacrent leur vie à l'amélioration de ces algorithmes. Vous devez utiliser leur travail, il fera heureux.
Comment de grandes améliorations que vous recevrez dépendra:
Pour les petites matrice tailles et les processeurs modernes, il est hautement probable que les données de deux
MatrixA
etMatrixB
sera conservé presque entièrement dans le cache après avoir touché la première fois.Juste quelque chose pour vous d'essayer (mais cela ne faire une différence pour les grandes matrices): ventilation de votre plus logique de la multiplication logique dans l'intérieur de la boucle comme ceci:
C'est parce que, en fin de caler votre pipeline lorsque vous écrivez à la suma. Accordé, une grande partie de cela est pris en charge dans le registre de renommer et de la forme, mais avec ma compréhension limitée de matériel, si je voulais serrer chaque once de performance du code, je le ferai, parce que maintenant vous n'avez pas à bloquer le pipeline d'attendre pour l'écriture de la suma. Depuis la multiplication est plus cher qu'ailleurs, vous souhaitez laisser la machine paralleliz autant que possible, afin d'épargner vos stands pour les plus signifie que vous passerez moins de temps à attendre dans l'ajout de la boucle que vous le feriez dans la multiplication de la boucle.
C'est juste ma logique. D'autres avec plus de connaissances dans le domaine sont en désaccord.
sums
tableau et lesuma
variables en dehors de la portée de lafor
boucle. Également envisager de déplacer les variables de l'indicel
ets
trop. Quand ils sont à l'intérieur de l'extérieurfor
boucle qu'ils seront créés et détruits pour chaque itération de l'extérieurfor
boucle. Supprimant les instructions seront également accélérer l'exécution.Pouvez-vous poster quelques données de comparaison sur vos 2 approches pour une gamme de matrice tailles ? Il se peut que vos attentes sont irréalistes et que votre 2ème version est plus rapide, mais vous n'avez pas fait les mesures encore.
N'oubliez pas, lorsque l'on mesure le temps d'exécution, afin d'inclure le temps de transposer matrixB.
Autre chose que vous pourriez vouloir essayer est de comparer les performances de votre code avec celui de l'équivalent de l'opération à partir de votre bibliothèque BLAS. Cela peut ne pas répondre directement à votre question, mais il vous donnera une meilleure idée de ce à quoi vous pouvez vous attendre à partir de votre code.
Le calcul de la complexité de la multiplication de deux N*N est la matrice O(N^3). La performance va être considérablement améliorée si vous utilisez O(N^2.73) algorithme qui a probablement été adopté par MATLAB. Si vous avez installé un MATLAB, essayez de multiplier deux 1024*1024 matrice. Sur mon ordinateur, MATLAB remplir à 0,7 s, mais C\C++ mise en œuvre de l'algorithme naïf comme la vôtre prend 20s. Si vous vous souciez vraiment de la performance, reportez-vous à l'angle inférieur des algorithmes complexes. J'ai entendu dire qu'il y existe O(N^2.4) l'algorithme, cependant il a besoin d'une très grande matrice de sorte que d'autres manipulations peuvent être négligées.
pas de si spécial, mais mieux :
Si vous travaillez sur de petits nombres, puis l'amélioration que vous mentionner est négligeable. Aussi, les performances varient et dépendent du Matériel sur lequel vous êtes en cours d'exécution. Mais si vous travaillez sur le nombre, en millions, alors il va effectuer.
À venir pour le programme, vous pouvez coller le programme que vous avez écrit.
Très vieille question, mais voici mon actuel de la mise en œuvre de mon opengl projets:
Où N est remplacée par la taille de la matrice. Donc, si vous êtes en multipliant les matrices 4x4, puis vous utilisez:
Cette fonction principalement minimise les boucles, mais le module peut être éprouvant... Sur mon ordinateur cette fonction à peu près 50% plus rapide qu'un triple boucle pour la multiplication de la fonction.
Contre:
Beaucoup de code nécessaire (ex. différentes fonctions pour mat3 x mat3, mat5 x mat5...)
Réglages nécessaires pour irréguliers de multiplication (ex. mat3 x mat4).....
Une manière générale, la transposition B devrait finissent par être beaucoup plus rapide que l'implémentation naïve, mais au détriment de perdre une autre NxN la valeur de la mémoire. Je viens de passer une semaine de creuser autour de la multiplication de matrice d'optimisation, et jusqu'à présent, l'absolu mains vers le bas le gagnant est: est-ce
C'est encore mieux que Drepper de la méthode mentionné dans un commentaire précédent, qu'il fonctionne de manière optimale quel que soit le cache des propriétés du sous-jacent de l'UC. L'astuce réside dans la réorganisation de la boucle, de sorte que tous les trois matrices sont accessibles en ligne ordre majeur.