行主要与列主要矩阵乘法

Question

我正在研究一个试图计算矩阵乘法的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];
    }
  }
}

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

Answer 1

如果您正在谈论使用Caches,那么您可能想要做一些称为循环平铺的事情.你将循环分解为tile,这样循环的内部部分就会存储在缓存中(这些天很大).所以你的循环会变成类似的东西(如果你使用指针将矩阵传递给函数)

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基本上只有列),并使用循环切片来缓存乘法的最大元素数量.希望这会有所帮助.