交叉点:Strassen算法

Question

就效率而言，Strassen算法应该停止递归并应用乘法的最佳交叉点是什么？

我知道这与具体的实现和硬件密切相关，但对于一般情况，应该有某种指导方针或某人的一些实验结果。

在网上搜索一下，问一些人，他们倾向于认为这是

n = 64; 

或

 n = 32;

任何人都可以验证/拒绝这些结果吗？

Answer 1

这应该在每台机器的基础上进行调优(有点像ATLAS )。对于非常大的矩阵，这种优化是值得的:如果你自己编码，并将其与eg进行比较。一个供应商的BLAS实现，那么你会发现一个相当大的n。

Strassen算法的内存需求也需要权衡。

Answer 2

在我的双核心2.66 Mac Pro上，使用我的实现，交叉小到n= 16。事实上，我的实现比处理大矩阵的传统算法要快得多--我不确定为什么--我认为它对缓存更友好，因为它专注于较小的本地化数据。事实上，我正要发布一个关于这方面的问题。

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

Answer 3

经过大量测试，我得出的结论是，至少对于我的处理器来说，Strassen算法的最佳交叉点是n = 128。

我的处理器是: Intel Core i5-430M。此外，有趣的是，对于4线程的CPU，我的实现在numberOfProcesses = 8上比在numberOfProcesses = 4上工作得更好一些。我不知道这是怎么发生的或者为什么会发生。我猜，由于通过通道进行更多的通信，它会有更大的开销，而且由于它们不能同时工作，它肯定会慢一点。显然我错了。如果任何人能解释这一点，顺便说一句，请写信给我，以便记录在案。

谢谢。