4

我目前正在开发一个试图计算矩阵乘法的 C 程序。我已经通过循环遍历第二个矩阵的每一列来完成这项任务，如下所示。

我已将大小设置为 1000。

for(i=0;i<size;i++)
{
  for(j=0;j<size;j++)
  {
    for(k=0;k<size;k++)
    {
      matC[i][j]+=matA[i][k]*matB[k][j];
    }
  }
}

我想知道这个实现中有什么问题的访问模式。是什么让行/列访问比另一个更有效？我试图从使用缓存的逻辑方面理解这一点。请帮助我理解这一点。非常感谢您的帮助 ：）

4

1 回答 1

9

如果您正在谈论缓存的使用，那么您可能想要做一些称为循环平铺的事情。您将循环分成小块，以便循环的内部部分存储在缓存中（这些天相当大）。所以你的循环会变成类似的东西（如果你使用指针将矩阵传递给函数）

for(j=0;j<size;j+=t)
    for(k=0;k<size;k+=t)
       for(i=0;i<size;i+=t)
          for(ii=i;ii<MIN(i+t,size);ii++)
             for(jj=j;jj<MIN(j+t,size);jj++)
        {       
          var=*(c+ii * size+jj);    //Var is a scalar variable                     
          for(kk=k;kk<MIN(k+t,size);kk++)
              {                      
         var = var + *(a+ii *size +kk) * *(bt +jj * size+ kk);          
              }
          *(c+ii *size +jj) = var;
        }

t 的值取决于您获得的加速比。它可以 t = 64,128,256 等等。您可以在这里使用许多其他技术。循环平铺只是一种有效利用缓存的技术。此外，您可以在发送到乘法函数之前转置 B 矩阵。这样，您将获得矩阵 B 元素的线性访问。为了向您解释更多考虑 

          A  --------   and B | | | |
             --------         | | | |
             --------         | | | | 
             --------         | | | |

在这里，您将始终考虑将 A 的第一行与 B 的第一列相乘。而且由于您使用的是C我相信，CPU 需要额外的努力才能在内存中一个接一个地读取矩阵 B 的所有列。为了简化这些工作，您可以转置矩阵并获取矩阵的行B'（本质上只是列B）并使用循环平铺缓存最大数量的元素以进行乘法运算。希望这会有所帮助。

于 2012-10-11T03:51:29.057 回答