c++ - 如何加快 C++ 中的矩阵乘法？

Question

我正在使用这个简单的算法执行矩阵乘法。为了更加灵活，我将对象用于包含动态创建的数组的矩阵。

将此解决方案与我的第一个使用静态数组的解决方案进行比较，速度要慢 4 倍。我可以做些什么来加快数据访问速度？我不想改变算法。

 matrix mult_std(matrix a, matrix b) {
 matrix c(a.dim(), false, false);
 for (int i = 0; i < a.dim(); i++)
  for (int j = 0; j < a.dim(); j++) {
   int sum = 0;
   for (int k = 0; k < a.dim(); k++)
    sum += a(i,k) * b(k,j);
   c(i,j) = sum;
  }

 return c;
}

---

编辑

---

我更正了我的问题!我在下面添加了完整的源代码并尝试了您的一些建议:

• 交换了 k和 j循环迭代 -> 性能提升
• 声明 dim()和 operator()()作为 inline -> 性能提升
• 通过 const 引用传递参数 -> 性能损失! 为什么？所以我不使用它。

现在的表现几乎与旧 porgram 中的表现相同。也许应该有更多的改进。

但我还有一个问题:函数 mult_strassen(...) 出现内存错误.为什么？
terminate called after throwing an instance of 'std::bad_alloc' <br/>
what(): std::bad_alloc

---

旧程序
main.c http://pastebin.com/qPgDWGpW

c99 main.c -o matrix -O3

---

新计划
矩阵.h http://pastebin.com/TYFYCTY7
矩阵.cpp http://pastebin.com/wYADLJ8Y
main.cpp http://pastebin.com/48BSqGJr

g++ main.cpp matrix.cpp -o matrix -O3 .

---

编辑

---

以下是一些结果。标准算法 (std)、j 和 k 循环的交换顺序 (swap) 和 block 大小为 13 (block) 的阻塞算法之间的比较。

Answer 1

说到加速，如果你交换 k 和 j 循环迭代的顺序，你的函数将更加缓存友好:

matrix mult_std(matrix a, matrix b) {
 matrix c(a.dim(), false, false);
 for (int i = 0; i < a.dim(); i++)
  for (int k = 0; k < a.dim(); k++)
   for (int j = 0; j < a.dim(); j++)  // swapped order
    c(i,j) += a(i,k) * b(k,j);

 return c;
}

这是因为最内层循环上的 k 索引会在每次迭代时导致 b 中的缓存未命中。使用 j 作为最内层索引，c 和 b 都被连续访问，而 a 保持不变。