4

C++ で行列乗算用のStrassen アルゴリズムを実装しようとしましたが、期待どおりの結果が得られませんでした。ご覧のとおり、strassen は常に標準の実装よりも時間がかかり、次元が 2 の累乗の場合のみ、標準の実装と同じくらい高速です。何が悪かったのか？ 代替テキスト

matrix mult_strassen(matrix a, matrix b) {
if (a.dim() <= cut)
    return mult_std(a, b);

matrix a11 = get_part(0, 0, a);
matrix a12 = get_part(0, 1, a);
matrix a21 = get_part(1, 0, a);
matrix a22 = get_part(1, 1, a);

matrix b11 = get_part(0, 0, b);
matrix b12 = get_part(0, 1, b);
matrix b21 = get_part(1, 0, b);
matrix b22 = get_part(1, 1, b);

matrix m1 = mult_strassen(a11 + a22, b11 + b22); 
matrix m2 = mult_strassen(a21 + a22, b11);
matrix m3 = mult_strassen(a11, b12 - b22);
matrix m4 = mult_strassen(a22, b21 - b11);
matrix m5 = mult_strassen(a11 + a12, b22);
matrix m6 = mult_strassen(a21 - a11, b11 + b12);
matrix m7 = mult_strassen(a12 - a22, b21 + b22);

matrix c(a.dim(), false, true);
set_part(0, 0, &c, m1 + m4 - m5 + m7);
set_part(0, 1, &c, m3 + m5);
set_part(1, 0, &c, m2 + m4);
set_part(1, 1, &c, m1 - m2 + m3 + m6);

return c; 
}

プログラム
matrix.h http://pastebin.com/TYFYCTY7
matrix.cpp http://pastebin.com/wYADLJ8Y
main.cpp http://pastebin.com/48BSqGJr

g++ main.cpp matrix.cpp -o matrix -O3.

4

5 に答える 5

8

いくつかの考え：

  • 2 のべき乗でないサイズの行列がゼロで埋められることを考慮するように最適化しましたか? アルゴリズムは、これらの項を乗算する必要がないことを前提としていると思います。これが、実行時間が 2^n と 2^(n+1)-1 の間で一定である平坦な領域を取得する理由です。ゼロであることがわかっている用語を掛けないことで、これらの領域を改善できるはずです。または、Strassen は 2^n サイズの行列でのみ動作することを意図しています。
  • 「大きな」行列は任意であり、アルゴリズムは単純なケース O(N^3) と O(N^2.8) よりもわずかに優れているだけであると考えてください。より大きなマトリックスを試すまで、測定可能な利益が得られない場合があります。たとえば、10,000x10,000 の行列が「小さい」と見なされる有限要素モデリングを行ったことがあります。グラフから判断するのは難しいですが、511 の場合は Stassen の場合の方が速いようです。
  • 最適化をまったく行わないなど、さまざまな最適化レベルでテストしてみてください。
  • このアルゴリズムは、乗算は加算よりもはるかにコストがかかると想定しているようです。これは 40 年前に最初に開発されたときは確かに真実でしたが、最近のプロセッサでは加算と乗算の差が小さくなっていると思います。これにより、乗算を減らして加算を増やすように見えるアルゴリズムの有効性が低下する可能性があります。
  • アイデアを得るために、他の Strassen 実装をいくつか調べましたか? 既知の優れた実装をベンチマークして、どれだけ高速化できるかを正確に確認してください。
于 2010-11-29T14:57:17.183 に答える
2

わかりました。私はこの分野の専門家ではありませんが、処理速度以外の問題が発生している可能性があります。まず、strassenメソッドは、はるかに多くのスタックを使用し、より多くの関数呼び出しを持ち、メモリの移動を追加します。OSからより大きなフレームを要求する必要があるため、スタックが大きくなると、一定のペナルティが発生します。さらに、動的割り当てを使用する場合、これも問題になります。

固定サイズ（テンプレートパラメータ付き）の行列クラスを使用してみますか？これにより、少なくとも割り当ての問題は解決されます。

注：イベントがコードで正しく機能するかどうかはわかりません。行列クラスはポインターを使用しますが、コピーコンストラクターまたは代入演算子はありません。デストラクタがないため、最後にメモリリークも発生します...

于 2010-11-29T15:01:59.553 に答える
2

Strassen の大きな O は、通常の O(N ^ 3) と比較して O(N ^ log 7) です。つまり、3 よりわずかに小さい log 7 底 2 です。

それはあなたがする必要がある乗算の数です。

それはあなたが持っている他のものにコストがかからないことを前提としており、Nが十分に大きくなったときにのみ「高速」になるはずです。

あなたの実装の多くは多くのサブマトリックスを作成しています。私の推測では、これを行うたびにメモリを割り当ててコピーする必要があるそれらを保存する方法です。プロセスのおそらく最も遅い部分を最適化するのに役立つ場合は、ある種の「スライス」マトリックスと論理転置マトリックスを用意してください。

于 2010-11-29T15:09:56.327 に答える
1

私の Stassen 掛け算の実装がどれほど高速であるかに、私は実際にショックを受けています。

http://ezekiel.vancouver.wsu.edu/~cs330/lectures/linear_algebra/mm/mm.c

n=1024 の場合、私のマシンではほぼ 16 倍のスピードアップが得られます。これほどの高速化を説明できる唯一の方法は、私のアルゴリズムがよりキャッシュに適しているということです。つまり、アルゴリズムは行列の小さな断片に焦点を当てているため、データがよりローカライズされています。

C++ 実装のオーバーヘッドが高すぎる可能性があります。コンパイラは、実際に必要なものよりも多くの一時変数を生成します。私の実装では、可能な限りメモリを再利用することでこれを最小限に抑えようとしています。

于 2011-10-19T20:20:38.333 に答える
0

ロングショットですが、標準の乗算はコンパイラによって最適化される可能性があると考えましたか？最適化をオフに切り替えてもらえますか？

于 2010-11-29T14:26:56.143 に答える