为什么我的斯特拉森的矩阵乘法很慢？
我用C ++编写了两个矩阵乘法程序：普通MM（源程序）和Strassen的MM程序（源程序），它们都在大小为2 ^ kx 2 ^ k的矩阵上运作（换句话说，即大小均匀的矩阵）。
结果非常糟糕。 对于1024 x 1024矩阵，普通MM需要46.381 sec ，而斯特拉森的MM需要1484.303 sec （ 25 minutes !!!!）。
我试图尽可能简化代码。 网上发现的其他Strassen的MM例子与我的代码没有多大区别。 斯特拉森的代码的一个问题很明显 - 我没有切入点，切换到常规MM。
我的Strassen的MM代码还有哪些其他问题？
谢谢 ！
直接链接到来源
http://pastebin.com/HqHtFpq9
http://pastebin.com/USRQ5tuy
EDIT1。 拳头，很多伟大的建议。 感谢您花时间分享知识。
我实施了更改（保留了我的所有代码），并添加了截止点。 MM的2048x2048矩阵，截止512已经给出了很好的结果。 普通MM：191.49s斯特拉森MM：112.179s显着改善。 使用Visual Studio 2012获得带有英特尔迅驰处理器的史前联想X61平板电脑的结果。我将进行更多检查（以确保我获得了正确的结果），并将发布结果。
斯特拉森的代码的一个问题很明显 - 我没有切入点，切换到常规MM。
公平地说，递归到1点是大部分（如果不是全部的话）问题。 试图猜测其他性能瓶颈而不解决这个问题几乎没有实际意义，因为它带来了巨大的性能打击。 （换句话说，你在比较苹果和橘子。）
正如评论中所讨论的那样，缓存对齐可能会产生影响，但不会影响到这种规模。 此外，高速缓存对齐可能会比Strassen算法更多地损害常规算法，因为后者是缓存无关的。
void strassen(int **a, int **b, int **c, int tam) {
// trivial case: when the matrix is 1 X 1:
if (tam == 1) {
c[0][0] = a[0][0] * b[0][0];
return;
}
这太小了。 虽然Strassen算法具有较小的复杂度，但它具有更大的Big-O常量。 首先，你的函数调用开销一直降到1个元素。
这类似于使用合并或快速排序并递归到一个元素。 为了高效，当大小变小并回退到经典算法时，需要停止递归。
在快速/合并排序中，您将回退到低开销的O(n^2)插入或选择排序。 在这里你会回到正常的O(n^3)矩阵乘法。
您退回经典算法的阈值应该是一个可调阈值，可能会因硬件和编译器优化代码的能力而异。
对于像斯特拉森乘法这样的优势，在经典的O(n^3) ，优势只有O(2.8074) O(n^3) ，如果这个门槛非常高，不要感到惊讶。 （数千个元素？）
在一些应用中，可以有许多算法，每个算法都具有降低的复杂性，但增加了Big-O。 结果是多种算法在不同的尺寸下变得最优。
大整数乘法就是这样一个臭名昭着的例子：
*请注意，这些示例阈值是近似值，可能会发生显着变化 - 通常超过10倍。
所以，这可能会有更多的问题，但是你的第一个问题是你正在使用指向数组的指针数组。 而且，由于您使用的是2的幂的数组大小，因此这对于连续分配元素并使用整数除法将长数字数组折叠成行来说尤其重要。
无论如何，这是我对一个问题的第一次猜测。 正如我所说的，可能还有更多，我会在发现它们时加入这个答案。
编辑：这可能只会造成一小部分问题。 这个问题很可能是Luchian Grigore提到的缓存线争用问题的两个幂。
我证实了我的担心对于朴素算法是有效的。 如果数组是连续的，那么朴素算法的时间减少将近50％。 这里是关于pastebin的代码（使用C ++ 11相关的SquareMatrix类）。
链接地址: http://www.djcxy.com/p/15083.html上一篇: Why is my Strassen's Matrix Multiplication slow?
下一篇: Why is a naïve C++ matrix multiplication 100 times slower than BLAS?