4

私は現在、行列の乗算を計算しようとしているCプログラムに取り組んでいます。以下に示すように、2番目の行列の各列をループすることでこのタスクに取り組みました。

サイズを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などになります。ここで使用できるテクニックは他にもたくさんあります。ループタイリングは、キャッシュを効率的に利用するための1回限りの手法です。さらに、乗算関数に送信する前に、B行列を転置することができます。そうすれば、行列Bの要素に線形にアクセスできるようになります。 

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

ここでは、Aの最初の行にBの最初の列を掛けることを常に検討します。またC、CPUは、メモリ内のマトリックスBのすべての列を1つずつ読み取るために、余分な労力を必要とします。これらの作業を容易にするために、行列を転置して行列の行B'（本質的には列にすぎないB）を取得し、ループタイリングを使用して乗算用の要素の最大量をキャッシュできます。これが役立つことを願っています。

于 2012-10-11T03:51:29.057 に答える