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

Question

我用C++写了两个矩阵乘法程序:常规MM (源)和Strassen的MM (源),它们都在大小为2 ^ kx 2 ^ k的矩形矩阵上运算(换句话说,是偶数大小的方阵).

结果很可怕.对于1024 x 1024矩阵,常规MM需要46.381 sec,而Strassen的MM需要1484.303 sec(25 minutes!!!!).

我试图让代码尽可能简单.在网上找到的其他Strassen的MM示例与我的代码没有太大的不同.Strassen代码的一个问题显而易见 - 我没有切换点,切换到常规MM.

我的Strassen的MM代码有哪些其他问题？

谢谢 !

直接链接到源
http://pastebin.com/HqHtFpq9
http://pastebin.com/USRQ5tuy

EDIT1.拳头,很多很棒的建议.感谢您抽出宝贵时间和分享知识.

我实施了更改(保留了我的所有代码),添加了截止点.具有截止512的2048x2048矩阵的MM已经给出了良好的结果.常规MM:191.49s Strassen的MM:112.179s显着改善.使用英特尔迅驰处理器,使用Visual Studio 2012,在史前联想X61 TabletPC上获得了结果.我将进行更多检查(以确保我得到正确的结果),并将发布结果.

Answer 1

Strassen代码的一个问题显而易见 - 我没有切换点,切换到常规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)矩阵乘法.

您回退经典算法的阈值应该是可调阈值,可能会根据硬件和编译器优化代码的能力而变化.

对于像Strassen乘法这样的优势,只有O(2.8074)经典的优势O(n^3),如果这个门槛非常高,不要感到惊讶.(成千上万的元素？)

在一些应用中,可以存在许多算法,每个算法具有降低的复杂度但增加Big-O.结果是多种算法在不同大小下变得最佳.

大整数乘法是一个臭名昭着的例子:

• 小学倍增:O(N ^ 2)最优<~100位*
• Karatsuba乘法:O(N ^ 1.585)比上述速度快~100位*
• Toom-Cook 3路:O(N ^ 1.465)比Karatsuba快~3000位*
• 浮点FFT:O(> N log(N))比Karatsuba/Toom-3快〜700位*
• Schönhage-Strassen算法(SSA):O(N log(n)loglog(n))比FFT快〜十亿个数字*
• 固定宽度数 - 理论变换:O(N log(n)比SSA快〜几十亿位？*

_{*请注意,这些示例阈值是近似值,可能会有很大差异 - 通常超过10倍.}