8

キャッシュに適した方法を使用して2つの行列を乗算する予定です（これにより、ミスの数が少なくなります）

これは、キャッシュに適した転置関数で実行できることがわかりました。

しかし、私はこのアルゴリズムを見つけることができません。これを達成する方法を知ることができますか?

4

2 に答える 2

7

あなたが探している言葉はスラッシングです。Googleでスラッシング行列の乗算を検索すると、より多くの結果が得られます。

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のアクセスパターンはまさにそれを行っています。したがって、メモリ内をジャンプする代わりに、最も内側のループが行列の2番目のアクセスインデックスでのみ動作するように演算を再配置できます。

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;
        }
   }
}
于 2013-01-26T17:56:34.530 に答える
1

@Cesarの答えは正しくありません。たとえば、内側のループ

for (int k = 0; k < n; k++)
   s += a[i,k] * Bcolj[k];

a の i 番目の列を通過します。

次のコードは、常に行ごとにデータにアクセスすることを保証する必要があります。

void multiply(const double (&a)[I][K], 
              const double (&b)[K][J], 
              double (&c)[I][J]) 
{
    for (int j=0; j<J; ++j) {
       // iterates the j-th row of c
       for (int i=0; i<I; ++i) {
         c[i][j] = 0;
       } 

       // iterates the j-th row of b
       for (int k=0; k<K; ++k) {
          double t = b[k][j];
          // iterates the j-th row of c
          // iterates the k-th row of a
          for (int i=0; i<I; ++i) {
            c[i][j] += a[i][k] * t;
          } 
       }
    }
}
于 2015-10-21T23:41:09.983 に答える