为什么在矩阵乘法运算期间，用于存储累加和的变量比直接访问结果单元格更快？

Question

我对算法和内存优化非常陌生，正在努力提高我对它的一般理解。我敢肯定这是一个非常基本的问题，但是我自己找不到答案，希望有人能帮助我阐明这个问题。

在 C 中实现矩阵乘法时，假设矩阵存储为 2D NxN 数组，此任务的最简单和最基本的方法可以写为：

for (i=0; i<N; i++)
    for (j=0; j<N; j++)
        for (k=0; k<N; k++)
            c[i][j] += a[i][k] * b[k][i];

然而，另一种简单的方法是引入一个变量来存储第三个循环的每个循环的累加和，即i_th行中的元素与j_th行中的元素的乘积之和。 ] 列（逐项），然后将其分配给产品矩阵。如以下代码所写：

for (i=0; i<N; i++) {
    for (j=0; j<N; j++) {
        int sum = 0;
        for (k=0; k<N; k++) {
            sum += a[i][k]*b[k][j];
        }
        c[i][j] = sum;
    }
}

我不明白为什么第二个代码被认为运行比第一个基本代码快一点？

提前感谢您的帮助

Answer 1

当子程序被传递指针a、b和c时，编译器通常不知道它们指向哪里。因此，在 c[i][j] += a[i][k] * b[k][i] 中，编译器必须考虑到 c[i][j] 的更新可能会更改将在循环的未来迭代中使用的 a 和 b 的元素的可能性。它通常这样做的方式是将每个更新写入 c[i][j].

的内存

与sum += a[i][k] * b[k][i]，编译器知道sum不能与a或b重叠，因为sum是本地创建的。因此，它可以通过将总和保存在寄存器中并仅在执行 c[i][j] = sum; 时写入内存一次来优化此代码。

为什么在矩阵乘法运算期间，用于存储累加和的变量比直接访问结果单元格更快？

Why during a matrix multiplication operation does a variable for storing the accumulating sum is faster then directly accessing the resulting cell?

c

memory

matrix-multiplication