1

作为一个实验，我实现了 Strassen 矩阵乘法算法，看看是否真的可以为大 n 带来更快的代码。

https://github.com/wcochran/strassen_multiplier/blob/master/mm.c

令我惊讶的是，大 n的速度要快得多。例如，n=1024 的情况使用传统方法耗时 17.20 秒，而使用 Strassen 方法（2x2.66 GHz Xeon）仅需 1.13 秒。什么——15 倍加速！？它应该只是稍微快一点。事实上，即使是小的 32x32 矩阵，它似乎也一样好！？

我可以解释这么多加速的唯一方法是我的算法对缓存更友好——即，它专注于小块矩阵，因此数据更加本地化。也许我应该尽可能地做我所有的矩阵算术。

关于为什么这么快的任何其他理论？

4

3 回答 3

3

Strassen 的递归性质具有更好的内存局部性，因此这可能是图片的一部分。递归正则矩阵乘法可能是一个比较合理的东西。

于 2012-03-17T02:44:39.170 回答
1

第一个问题是“结果是否正确？”。如果是这样，您的“常规”方法可能不是一个好的实现。

常规方法是不使用 3 个嵌套的 FOR 循环按照您在数学课中学习的顺序扫描输入。一个简单的改进是在右侧转置矩阵，使其位于内存中，列是连贯的，而不是行。修改乘法循环以使用这种替代布局，它将在大型矩阵上运行得更快。

标准矩阵库实现了更多考虑数据缓存大小的缓存友好方法。

您还可以实现标准矩阵乘积的递归版本（细分为一半大小的 2x2 矩阵）。这将提供更接近最佳缓存性能的东西，这是 strassen 从递归中获得的。

所以要么你做错了，要么你的常规代码没有优化。

于 2011-10-19T21:20:14.073 回答
0

传统乘法中的循环顺序是什么？如果你有

for (int i = 0; i < new_height; ++i)
{
    for (int j = 0; j < new_width; ++j)
    {
        double sum = 0.0;
        for (int k = 0; k < common; ++k)
        {
            sum += lhs[i * common + k] * rhs[k * new_width + j];
        }
        product[i * new_width + j] = sum;
    }
}

那么您对缓存不是很好，因为您以非连续方式访问右侧矩阵。重新订购后

for (int i = 0; i < new_height; ++i)
{
    for (int k = 0; k < common; ++k)
    {
        double const fixed = lhs[i * common + k];
        for (int j = 0; j < new_width; ++j)
        {
            product[i * new_width + j] += fixed * rhs[k * new_width + j];
        }
    }
}

在最内层循环中访问两个矩阵是连续的，一个甚至是固定的。一个好的编译器可能会自动执行此操作，但我选择显式将其拉出以进行演示。

您没有指定语言，但对于 C++，高级编译器甚至可以识别某些配置中不友好的循环顺序并重新排序。

于 2014-11-18T09:44:12.430 回答