logo标签列表

为什么 Strassen 矩阵乘法比标准矩阵乘法慢得多？

c++performancematrixmultiplicationstrassen
20

我曾经用C++、Python和Java编写程序来进行矩阵乘法，并测试了它们在两个2000 x 2000的矩阵相乘方面的速度（参见文章）。标准的ikj-implentation实现如下图所示：enter image description here，其用时如下：

现在，我已经按照维基百科上的方法，用Python和C++实现了Strassen算法，其中Python的实现如下图所示：enter image description here，它们的用时如下：

为什么Strassen矩阵乘法比标准矩阵乘法慢得多？

可能的原因：

  • 某些缓存效应
  • 实现问题：
    • 错误（结果为2000 x 2000的矩阵是正确的）
    • null-multiplication（对于 2000 x 2000 -> 2048 x 2048 不应该那么重要）

这尤其令人惊讶，因为它似乎与其他人的经验相矛盾：

编辑：在我这种情况下 Strassen 矩阵乘法较慢的原因是：

  • 我将其全部递归化（请参见 tam）
  • 我有两个函数 strassen 和 strassenRecursive。第一个如果需要则将矩阵调整大小到二的幂，并调用第二个函数。但是 strassenRecursive 没有递归调用自身，而是调用了 strassen。
3
我尚未检查，但有许多新向量正在被分配。我想内存分配时间是导致问题的原因。 - Vaughn Cato
Voo的回答基本上也涵盖了内存分配问题，因为更早地停止递归将减少分配数量。顺便说一下，在我的电脑上，我发现截止值大约为250是一个不错的选择。 - Vaughn Cato
顺便说一下，你发布的源代码无法被任何人实验，因为你没有发布数据文件。这意味着除了猜测之外，没有人能做任何事情。 - Puppy
1
@DeadMG：实际上数据文件在那里，只是在测试目录的上面几个级别。 - Vaughn Cato
4个回答
17
基本问题是您的Strassen实现递归到叶子大小为1。 Strassen算法具有更好的大O复杂度，但常数在实际中非常重要，这意味着对于较小的问题大小，使用标准的n^3矩阵乘法会更好。因此，为了大大改善您的程序，而不是执行：
if (tam == 1) {
        C[0][0] = A[0][0] * B[0][0];
        return;
    }

使用 if (tam == LEAF_SIZE) // 迭代解决方案。 LEAF_SIZE 应该是一个常数，需要根据你的特定架构通过实验来确定。根据架构的不同，它可能会更大或更小 - 在一些架构中，斯特拉森算法的常数因子非常大，以至于对于合理的矩阵大小，它基本上总是比简单的 n^3 实现更差。这完全取决于具体情况。

你是对的。我已经在这个脚本中添加了LEAF_SIZE：https://github.com/MartinThoma/matrix-multiplication/blob/master/C%2B%2B/strassen-mixed.cpp。对于叶子大小为10，时间降至66.50秒，对于20则为29.96秒，对于50则为18.80秒。我如何更好地（更有结构化、自动化地）测试`LEAF_SIZE`的好值，而不是改变代码中的值，重新编译，测试和尝试其他值？你知道一个简单的可能性来绘制它吗？（我应该问另一个问题，因为这似乎与我的先前问题方向不同？） - Martin Thoma
@moose 好的，让程序将叶子大小作为输入参数。个人建议如下：对于每个叶子大小运行程序十次（更多次数效果更好，但10次已经相当准确），并将所有值存储在文本文件中（例如64.txt、128.txt等）- 这显然是一个shell脚本任务。之后使用一个简单的脚本（我喜欢Python），该脚本获取运行时间，丢弃最快/最慢的2个值，并计算其余值的平均值，并将该数据输出为CSV格式。CSV具有很大的优势，即Excel/OpenOffice等软件都可以读取它，并用两个点击生成漂亮的图表。 - Voo
2
谢谢您的帮助。我刚刚绘制了结果：http://cloud.github.com/downloads/MartinThoma/matrix-multiplication/charts.pdf - Martin Thoma
另外一点需要注意的是：你的Java程序可能会解释执行相当大部分的代码（或使用OSR），这会增加运行时间。如果你主要关心Java程序在JIT编译后的运行速度，你需要稍微改变一下基准测试（不使用time命令，而是在一些预热之后打印矩阵的运行时间）。虽然使用正确的编译器选项，速度差异可能会降至C语言中的向量化/自动并行处理水平，但可惜的是JVM无法做到这一点，因此你可能看不到太大的差异。 - Voo
在基于ARM Cortex A9的平台上进行测试，结果发现对于512x512矩阵，叶大小为32是最优的。相比于叶大小为1的情况，时间差异为5秒和193秒！ - ysap
显示剩余3条评论
6

好的，“算术运算”并不是唯一需要考虑的事情。并不像其他所有东西都是免费的。

我天真的猜测是，所有这些内存分配和复制操作比减少算术运算所获得的收益更大...

特别是当内存访问超出缓存范围时，它可能非常昂贵。相比之下，算术运算可以被认为是免费的 :-)

1
而对于C ++，一种优化可能是在预先分配的足够大的内存块上使用placement new。 - Desmond Hume
1
同意，我认为这里发生的所有内存机制都是减速的主要原因。 - Puppy
1
我记得在大学时也做过同样的事情。我的实现是用Java完成的。我还编写了一个脚本来测试代码，我有超过10000个不同大小（22）~（81928192）的随机矩阵测试用例。我没有让递归到标量级别，我使用所有2的幂作为停止点。我发现Strassen算法更有效的范围和比朴素算法更差的范围。
我没有调查缓存、内存或JVM（垃圾回收）。
当我在班上展示时，我将这些发现归因于Strassen算法渐进复杂度是以乘法次数为单位衡量的事实。它是在计算机执行加法比乘法快的时代设计的。
现在的CPU乘法速度与加法一样快（循环次数）。 如果检查这两种算法，你会发现只有当大小小于2^10时，Strassen算法的算术操作次数才比朴素算法少（如果我没记错的话）。
0

尽管 Strassen 算法具有更小的大 O 符号，但为了利用它，您需要将矩阵相乘，这些矩阵对于大多数标准计算机甚至超级计算机来说都太大而无法解决。

可以这样想

一个问题是 x^3，另一个问题是 X^1.6734 + 8x^(1/2) +x ......

不完全是这样。在现代计算机上，Strassen通常会得到数百的截止值。而且，在当今这个时代，600x600矩阵才算是小型的。哪怕是50k x 50k矩阵的问题在今天也不值得一提（9GB内存？现在有16GB+的台式机）。 - Voo
您可能在提到Coppersmith-Winograd算法：http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm - ysap
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接