0

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

 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];

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

4

1 回答 1

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稍后在右边相乘，那么原始顺序效果更好。第二个建议将一列的副本保留到一个连续单词数组中，同时计算一个乘积以充分利用内存读取该副本。

于 2013-09-14T02:37:05.787 回答