行主序与列主序矩阵乘法

Question

行主序与列主序矩阵乘法

5

我目前在开发一个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];
    }
  }
}

我想知道这个实现中的问题访问模式是什么。什么使得行/列访问比其他方式更有效？我试图从使用缓存的逻辑角度理解这一点。请帮助我理解。非常感谢你的帮助 :)

- WoLv3rine

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Recker · Accepted Answer

如果您谈论的是缓存的使用，那么您可能想要做一些称为循环分块的事情。您将循环分成瓷砖，以便循环的内部部分存储在缓存中（这在今天相当大）。因此，如果您正在使用指针将矩阵传递到函数中，则您的循环将变成以下形式：

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的列），并使用循环分块缓存最大数量的元素以进行乘法计算。希望这有所帮助。