为什么我的Strassen矩阵乘法很慢？

Question

我用C++编写了两个矩阵乘法程序:常规的MM (source)和Strassen的MM (source)，这两个程序都对大小为2^k x 2^k的方阵(换句话说，偶数大小的方阵)进行运算。

结果太糟糕了。对于1024x1024矩阵，常规MM采用46.381 sec，而Strassen的MM采用1484.303 sec (25 minutes！)。

我试图使代码尽可能简单。在网上找到的其他Strassen的MM示例与我的代码没有太大不同。Strassen的代码有一个明显的问题--我没有截止点，它会切换到常规MM.。

我的Strassen's MM代码还有什么问题？

谢谢！

直接链接到源文件

http://pastebin.com/HqHtFpq9

http://pastebin.com/USRQ5tuy

Edit1。首先，有很多很棒的建议。感谢您抽出时间与我们分享知识。

我实现了更改(保留了我所有的代码)，添加了截止点。MM的2048x2048矩阵，截止到512已经给出了很好的结果。常规MM: 191.49s Strassen's MM: 112.179s显着提高。结果是使用Visual Studio 2012在配备英特尔迅驰处理器的史前联想X61 TabletPC上获得的。我会做更多的检查(以确保我得到了正确的结果)，并发布结果。

Answer 1

所以，可能会有更多的问题，但是你的第一个问题是，你使用了指向数组的指针数组。由于您使用的数组大小是2的幂，因此在连续分配元素并使用整数除法将长数字数组折叠成行时，这会对性能造成特别大的影响。

无论如何，这是我对一个问题的第一个猜测。正如我所说的，可能还有更多，当我发现它们时，我会补充这个答案。

编辑：这可能只会对问题造成很小的影响。这个问题很可能就是Luchian Grigore提到的涉及cache line contention issues with powers of two的问题。

我验证了我的担忧对于朴素算法是有效的。如果数组是连续的，则朴素算法的时间减少了近50%。这是the code for this (using a SquareMatrix class that is C++11 dependent) on pastebin。