c++ - 加速矩阵乘法

Question

我必须在 C++ 程序中对矩阵本身进行矩阵 bool 乘法运算，并且我想对其进行优化。矩阵是对称的，所以我想逐行乘法以减少缓存未命中。我以这种方式为矩阵分配空间:

matrix=new bool*[dimension];
for (i=0; i<dimension; i++) {
    matrix[i]=new bool[dimension];
}

乘法如下:

for (m=0; m<dimension; m++) {
    for (n=0; n<dimension; n++) {
         for (k=0; k<dimension; k++) {
                temp=mat[m][k] && mat[n][k];
                B[m][n]= B[m][n] || temp;
...

我用这个版本和另一个像这样逐列乘法的版本做了一些计算时间测试

for (m=0; m<dimension; m++) {
    for (n=0; n<dimension; n++) {
         for (k=0; k<dimension; k++) {
                temp=mat[m][k] && mat[k][n];
                B[m][n]= B[m][n] || temp;
...

我在 1000x1000 矩阵上进行了测试结果显示第二个版本(逐列)比前一个版本更快。你能告诉我为什么吗？第一个算法中的未命中数不应该更少吗？

Answer 1

在第一种乘法方法中， bool 矩阵的行连续存储在内存中并连续访问，因此预取工作完美无缺。在第二种方法中，访问元素 (n,0) 时获取的缓存行可以在访问 (n+1,0) 时被逐出。这是否真的发生取决于架构及其运行代码的缓存层次结构属性。在我的机器上，对于足够大的矩阵，第一种方法确实更快。

至于加速计算:不要使用逻辑运算符，因为它们是惰性计算的，因此可能会发生分支预测错误。一旦 B[m][n] 变为真，就可以提前退出内部循环。除了使用 bool 值，您可能还想考虑使用整数位。这样您就可以一次在内部循环中组合 32 或 64 个元素，并可能使用矢量化。如果您的矩阵相当稀疏，那么您可能需要考虑切换到稀疏矩阵数据结构。改变循环的顺序也可以帮助引入阻塞。但是，任何性能优化都是特定于架构和输入矩阵类的。