3

行列乗算演算のキャッシュ ミスを減らすために行列を転置する割り当てに取り組んでいます。何人かのクラスメートから聞いた話によると、私は 8 倍上達しているはずです。しかし、私は2倍しか得ていません...何が間違っているのでしょうか?

GitHub の完全なソース

void transpose(int size, matrix m) {
    int i, j;
    for (i = 0; i < size; i++) 
        for (j = 0; j < size; j++) 
            std::swap(m.element[i][j], m.element[j][i]);
}

void mm(matrix a, matrix b, matrix result) {
    int i, j, k;
    int size = a.size;
    long long before, after;

    before = wall_clock_time();
    // Do the multiplication
    transpose(size, b); // transpose the matrix to reduce cache miss
    for (i = 0; i < size; i++)
        for (j = 0; j < size; j++) {
            int tmp = 0; // save memory writes
            for(k = 0; k < size; k++)
                tmp += a.element[i][k] * b.element[j][k];
            result.element[i][j] = tmp;
        }
    after = wall_clock_time();
    fprintf(stderr, "Matrix multiplication took %1.2f seconds\n", ((float)(after - before))/1000000000);
}

これまでのところ、私は正しいことをしていますか?

参考までに: 次に行う必要がある最適化は、SIMD/Intel SSE3 を使用することです

4

2 に答える 2

11

これまでのところ、私は正しいことをしていますか?

いいえ、転置に問題があります。パフォーマンスについて心配する前に、この問題を確認しておく必要があります。最適化のために何らかのハッキングを行っている場合は、単純ではあるが最適ではない実装をテストとして使用することをお勧めします。100 倍のスピードアップを達成する最適化は、正しい答えが得られなければ意味がありません。

役立つもう 1 つの最適化は、参照渡しです。あなたはコピーを渡しています。実際、あなたmatrix resultはコピーを渡しているので、決して出てこないかもしれません。もう一度、テストする必要があります。

高速化に役立つさらに別の最適化は、いくつかのポインターをキャッシュすることです。これはまだかなり遅いです:

for(k = 0; k < size; k++)
    tmp += a.element[i][k] * b.element[j][k];
result.element[i][j] = tmp;

オプティマイザーはポインターの問題を回避する方法を見つけるかもしれませんが、おそらくそうではありません。__restrict__少なくとも、行列が重複していないことをコンパイラに伝えるために非標準キーワードを使用しない場合はそうではありません。a.element[i]ポインターをキャッシュして、b.element[j]、 、およびを行う必要がないようにしますresult.element[i]。__restrict__また、これらの配列がキーワードと重複していないことをコンパイラに伝えると、それでも役立つ場合があります。

補遺
コードを調べた後、助けが必要です。最初にマイナーなコメント。あなたはC++を書いていません。あなたのコードは C で、C++ のヒントが少しあります。C++ヘッダーではなく、Cヘッダーではなく、Cヘッダーを使用しstructてclassいます。mallocnewtypedef structstruct

あなたの の実装のためstruct matrix、コピー コンストラクターによる速度低下に関する私のコメントは正しくありませんでした。それが間違っていたことはさらに悪いことです！暗黙的に定義されたコピー コンストラクターを、ネイキッド ポインターを含むクラスまたは構造体と組み合わせて使用​​すると、火遊びになります。m(a, a, a_squared)行列 の 2 乗を取得するために誰かが呼び出しを行うと、やけどを負うことになりますa。2m(a, a, a)のインプレース計算を行うことを期待する人がいると、さらにひどいことになります 。a

数学的には、コードは行列乗算の問題のごく一部しかカバーしていません。100x1000 の行列に 1000x200 の行列を掛けたい場合はどうすればよいでしょうか? それは完全に有効ですが、コードは正方行列でのみ機能するため、コードはそれを処理しません。一方、あなたのコードでは、誰かが 100x100 の行列に 200x200 の行列を掛けることができますが、これはあまり意味がありません。

構造的には、不規則な配列を使用しているため、コードが遅くなることがほぼ 100% 保証されています。mallocメモリ全体に行列の行をスプライトできます。行列が連続した配列として内部的に表されているが、NxM 行列であるかのようにアクセスされる場合、パフォーマンスが大幅に向上します。C++ には、まさにそれを行うための優れたメカニズムがいくつか用意されています。

于 2012-10-03T04:32:43.883 に答える
3

割り当てが転置しなければならないことを示唆している場合は、もちろん、転置手順を修正する必要があります。現状では、転置は2回行われるため、転置はまったく行われません。j=loopは読み取るべきではありません

j=0; j<size; j++

しかし

j=0; j<i; j++

因子行列の1つの要素を「間違った」順序で処理することを避けるために、転置は必要ありません。jループとkループを入れ替えるだけです。（その他の）パフォーマンス調整はさておき、基本的なループ構造は次のようになります。

  for (int i=0; i<size; i++)
  {
    for (int k=0; k<size; k++)
    {
      double tmp = a[i][k];
      for (int j=0; j<size; j++)
      {
        result[i][j] += tmp * b[k][j];
      }
    }
  }
于 2012-10-03T20:43:06.893 に答える