缓存友好方法乘以两个矩阵

Question

我打算使用缓存友好的方法将2个矩阵相乘(这将导致更少的未命中)

我发现这可以通过缓存友好的转置函数来完成.

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

Answer 1

您正在寻找的词是thrashing。在 Google 中搜索 thrashing matrix multiplication 会产生更多结果。

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 , j] 中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;
        }
   }
}