Multiplication de la matrice: Strassen vs. Standard

Question

J'ai essayé d'implémenter le Strassen algorithm pour la multiplication matricielle en C++, mais le résultat n'est pas celui-là, ce à quoi je m'attendais. Comme vous pouvez le voir, strassen prend toujours plus de temps que l'implémentation standard et seulement avec une dimension d'une puissance de 2 est aussi rapide que l'implémentation standard. Qu'est ce qui ne s'est pas bien passé?

matrix mult_strassen(matrix a, matrix b) { 
if (a.dim() <= cut) 
    return mult_std(a, b); 

matrix a11 = get_part(0, 0, a); 
matrix a12 = get_part(0, 1, a); 
matrix a21 = get_part(1, 0, a); 
matrix a22 = get_part(1, 1, a); 

matrix b11 = get_part(0, 0, b); 
matrix b12 = get_part(0, 1, b); 
matrix b21 = get_part(1, 0, b); 
matrix b22 = get_part(1, 1, b); 

matrix m1 = mult_strassen(a11 + a22, b11 + b22); 
matrix m2 = mult_strassen(a21 + a22, b11); 
matrix m3 = mult_strassen(a11, b12 - b22); 
matrix m4 = mult_strassen(a22, b21 - b11); 
matrix m5 = mult_strassen(a11 + a12, b22); 
matrix m6 = mult_strassen(a21 - a11, b11 + b12); 
matrix m7 = mult_strassen(a12 - a22, b21 + b22); 

matrix c(a.dim(), false, true); 
set_part(0, 0, &c, m1 + m4 - m5 + m7); 
set_part(0, 1, &c, m3 + m5); 
set_part(1, 0, &c, m2 + m4); 
set_part(1, 1, &c, m1 - m2 + m3 + m6); 

return c; 
} 

---

PROGRAMME
matrix.h http://pastebin.com/TYFYCTY7
http://pastebin.com/wYADLJ8Y
matrix.cpp main.cpp http://pastebin.com/48BSqGJr

g++ main.cpp matrix.cpp -o matrix -O3.

Answer 1

Quelques réflexions:

• Avez-vous optimisé pour considérer qu'une non-puissance de matrice à deux dimensions est remplie avec des zéros? Je pense que l'algorithme suppose que vous ne vous embêtez pas à multiplier ces termes. C'est pourquoi vous obtenez les zones plates où le temps de fonctionnement est constant entre 2^n et 2^(n + 1) -1. En ne multipliant pas les termes que vous connaissez sont zéro, vous devriez être en mesure d'améliorer ces domaines. Ou peut-être que Strassen n'est destiné qu'à travailler avec des matrices de 2^n. Considérons qu'une «grande» matrice est arbitraire et que l'algorithme n'est que légèrement meilleur que le cas naïf, O (N^3) vs O (N^2.8). Vous ne pouvez pas voir des gains mesurables jusqu'à ce que des matrices plus grandes soient essayées. Par exemple, j'ai fait une modélisation par éléments finis où 10 000 x 10 000 matrices étaient considérées comme «petites». C'est difficile à dire à partir de votre graphique, mais il semble que l'affaire 511 pourrait être plus rapide dans l'affaire Stassen. Essayez les tests avec différents niveaux d'optimisation, y compris aucune optimisation.
• Cet algorithme semble supposer que les multiplications sont beaucoup plus chères que les additions. C'était certainement vrai il y a 40 ans quand il a été développé, mais je crois que dans les processeurs plus modernes, la différence entre ajouter et multiplier a diminué. Cela peut réduire l'efficacité de l'algorithme qui semble réduire les multiplications mais augmenter les ajouts.
• Avez-vous regardé d'autres implémentations de Strassen pour trouver des idées? Essayez de comparer une implémentation connue pour voir exactement combien vous pouvez obtenir plus rapidement.

Answer 2

Plan à long, mais avez-vous considéré que la multiplication standard peut être optimisée par le compilateur? Pourriez-vous désactiver les optimisations?

Answer 3

Ok Je ne suis pas un expert dans ce domaine, mais il pourrait y avoir d'autres problèmes au travail ici que la vitesse de traitement. D'abord, la méthode strassen utilise beaucoup plus de pile et a plus d'appels de fonctions, ce qui ajoute un mouvement de mémoire. Vous avez une certaine pénalité, plus votre pile est grande, car elle doit demander des images plus grandes à partir du système d'exploitation. De plus, vous utilisez l'allocation dynamique, c'est aussi un problème. Essayez d'utiliser une classe de matrice de taille fixe (avec paramètre de modèle)? Cela permettra au moins de résoudre le problème d'allocation.

Remarque: Je ne suis pas sûr que cet événement fonctionne correctement avec votre code. Votre classe de matrice utilise des pointeurs mais n'a pas de constructeur de copie ou d'opérateur d'affectation. Vous perdez aussi de la mémoire à la fin, puisque vous n'avez pas de destructeur ...

Answer 4

Le grand O de Strassen est O (N^log 7) comparé à O (N^3) régulier, c.-à-d.log 7 base 2 qui est légèrement inférieur à 3.

C'est le nombre de multiplications que vous devez faire.

Il suppose que tout ce que vous avez est gratuit et ne devrait être "plus rapide" que lorsque N devient assez grand, ce qui n'est probablement pas le cas.

Une grande partie de votre implémentation crée beaucoup de sous-matrices et je suppose que c'est la façon dont vous les stockez que vous devez allouer de la mémoire et copier chaque fois que vous faites cela. Avoir une sorte de «tranche» de matrice et de matrice de transposition logique, si vous le pouvez, vous aiderait à optimiser ce qui est probablement la partie la plus lente de votre processus.

Answer 5

Je suis vraiment choqué par la façon beaucoup plus vite mon Stassen multiplcation mise en œuvre est la suivante:

http://ezekiel.vancouver.wsu.edu/~cs330/lectures/linear_algebra/mm/mm.c

Je reçois un presque 16x sur ma machine speedup lorsque n = 1024. La seule façon que je peux expliquer autant d'une accélération est que mon algorithme est plus facile à mettre en cache - c'est-à-dire, il se concentre sur les petites pièces des matrices et donc les données sont plus localisées. Le surcoût dans votre implémentation C++ est probablement trop élevé - le compilateur génère plus de temporaires que ce qui est vraiment nécessaire. Ma mise en œuvre essaie de minimiser cela en réutilisant la mémoire chaque fois que cela est possible .