C语言 增加矩阵乘法中的数据局部性

Question

在矩阵乘法中，我们做这样的事情

 for (i = 0; i < N; i = i + 1)
   for (j = 0; j < N; j = j + 1)
      A[i*N + j] = (double) random() / SOME_NUMBER;     
 for (i = 0; i < N; i = i + 1)
    for (j = 0; j < N; j = j + 1)
       B[i*N + j] = (double) random() / SOME_NUMBER;

 for (i = 0; i < N; i = i + 1)
    for (j = 0; j < N; j = j + 1)
       for (k = 0; k < N; k = k + 1)
            C[i*N + j] = C[i*N + j] + A[i*N + k]*B[k*N + j];

我们如何增加数据的局部性以优化乘法循环

Answer 1

以转置形式存储 B：

B[j*N + i] = ramdom() / SOME_NUMBER;

您还必须按该顺序访问转置数组：

C[i*N + j] = C[i*N + j] + A[i*N + k]*B[j*N + k];

如果无法做到这一点，请先重写乘法以循环 j，然后重写 B 列 j 的第一个乘积（A 的第 0 行）以将 B[*;j] 的元素提取到连续的 N 向量中，并在该列的其余产品中使用该顺序副本。

这个想法是将 B 的列放入连续的记忆字中。 转置非常自然地做到这一点，但保持这种格式可能不切实际。 （例如，如果 B 稍后在右侧相乘，则原始顺序效果更好。 第二个建议将一列的副本保留为连续单词数组，同时计算一和乘积以充分利用该副本上的内存读取。