缓存友好的方法，以将两个矩阵相乘

Question

我打算乘以使用缓存友好的方法2点矩阵（这将导致较少的未命中的数目）

我发现，这可以与高速缓存友好转置函数来完成。

但我无法找到这个算法。我可以知道如何实现这一目标吗？

Answer 1

你正在寻找的词是颠簸。在Google yields more results中搜索颠簸矩阵乘法。

对于C的标准乘算法= A * B看起来像

void multiply(double[,] a, double[,] b, double[,] c) 
{ 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      for (int k = 0; k < n; k++) 
       C[i, j] += a[i, k] * b[k, j]; 
} 

基本上，在大步骤快速度导航存储器是不利的性能。 B中的k的访问模式正在完成该操作。因此，而不是在存储跳来跳去，我们可能会重新安排操作，使得最内环仅在矩阵的第二存取操作指数：

void multiply(double[,] a, double[,] B, double[,] c) 
{ 
    for (i = 0; i < n; i++) 
    { 
     double t = a[i, 0]; 
     for (int j = 0; j < n; j++) 
     c[i, j] = t * b[0, j]; 

     for (int k = 1; k < n; k++) 
     { 
     double s = 0; 
     for (int j = 0; j < n; j++) 
      s += a[i, k] * b[k, j]; 
     c[i, j] = s; 
     } 
    } 
} 

这是该网页上给出的例子。但是，另一种方法是事先将B [k，*]的内容复制到数组中，并在内部循环计算中使用该数组。这种方法通常比替代方案快，即使它涉及复制数据。即使这看起来可能与直觉相反，请随时尝试一下。

void multiply(double[,] a, double[,] b, double[,] c) 
{ 
    double[] Bcolj = new double[n]; 
    for (int j = 0; j < n; j++) 
    { 
     for (int k = 0; k < n; k++) 
      Bcolj[k] = b[k, j]; 

     for (int i = 0; i < n; i++) 
     { 
      double s = 0; 
      for (int k = 0; k < n; k++) 
       s += a[i,k] * Bcolj[k]; 
      c[j, i] = s; 
     } 
    } 
} 

Answer 2

@ Cesar的回答不正确。例如，内部循环

for (int k = 0; k < n; k++) 
    s += a[i,k] * Bcolj[k]; 

经过a的第i列。

以下代码应确保我们总是按行访问数据。

void multiply(const double (&a)[I][K], 
       const double (&b)[K][J], 
       const double (&c)[I][J]) 
{ 
    for (int j=0; j<J; ++j) { 
     // iterates the j-th row of c 
     for (int i=0; i<I; ++i) { 
     c[i][j] = 0; 
     } 

     // iterates the j-th row of b 
     for (int k=0; k<K; ++k) { 
      double t = b[k][j]; 
      // iterates the j-th row of c 
      // iterates the k-th row of a 
      for (int i=0; i<I; ++i) { 
      c[i][j] += a[i][k] * t; 
      } 
     } 
    } 
}