13

私はC++で2つの行列乗算プログラムを作成しました。通常のMM （ソース）とStrassenのMM （ソース）です。どちらもサイズ2 ^ kx 2 ^ kの正方行列（つまり、偶数サイズの正方行列）で動作します。

結果はひどいです。1024 x 1024マトリックスの場合、通常のMMは46.381 sec、を取りますが、StrassenのMMは1484.303 sec（25 minutes!!!!）を取ります。

私はコードをできるだけ単純に保つように努めました。Web上にある他のStrassenのMMの例は、私のコードとそれほど変わりません。Strassenのコードに関する1つの問題は明らかです。通常のMMに切り替わる、カットオフポイントがありません。

私のStrassenのMMコードには他にどのような問題がありますか？

ありがとう ！

ソースへの直接リンク
http://pastebin.com/HqHtFpq9http://pastebin.com/USRQ5tuy

編集1。拳、たくさんの素晴らしいアドバイス。時間を割いて知識を共有していただきありがとうございます。

変更を実装し（すべてのコードを保持）、カットオフポイントを追加しました。2048x2048マトリックスのMM、カットオフ512は、すでに良好な結果をもたらしています。通常のMM：191.49s StrassenのMM：112.179s大幅な改善。結果は、Visual Studio 2012を使用して、IntelCentrinoプロセッサーを搭載した先史時代のLenovoX61 TabletPCで取得されました。さらにチェックを行い（正しい結果が得られたことを確認するため）、結果を公開します。

4

2 に答える 2

27

Strassenのコードに関する1つの問題は明らかです。通常のMMに切り替わる、カットオフポイントがありません。

1ポイントまで繰り返すことが、（全体ではないにしても）問題の大部分であると言っても過言ではありません。これに対処せずに他のパフォーマンスのボトルネックを推測しようとすると、パフォーマンスが大幅に低下するため、ほとんど意味がありません。（言い換えれば、あなたはリンゴとオレンジを比較しているのです。）

コメントで説明されているように、キャッシュの配置は効果がある可能性がありますが、この規模ではありません。さらに、キャッシュアラインメントは、Strassenアルゴリズムよりも通常のアルゴリズムに悪影響を与える可能性があります。これは、Strassenアルゴリズムがキャッシュを無視するためです。

void strassen(int **a, int **b, int **c, int tam) {

    // trivial case: when the matrix is 1 X 1:
    if (tam == 1) {
            c[0][0] = a[0][0] * b[0][0];
            return;
    }

それは小さすぎます。Strassenアルゴリズムの複雑さは小さくなりますが、Big-O定数ははるかに大きくなります。1つは、関数呼び出しのオーバーヘッドが1つの要素に至るまであることです。

これは、マージまたはクイックソートを使用して、1つの要素まで繰り返し実行することに似ています。効率的にするには、サイズが小さくなったときに再帰を停止し、従来のアルゴリズムにフォールバックする必要があります。

O(n^2)クイック/マージソートでは、オーバーヘッドの少ない挿入または選択ソートにフォールバックします。O(n^3)ここでは、正規行列の乗算にフォールバックします。

従来のアルゴリズムにフォールバックするしきい値は、ハードウェアとコードを最適化するコンパイラーの能力に応じて変化する可能性が高い調整可能なしきい値である必要があります。

O(2.8074)利点がクラシックよりも優れているStrassen乗算のようなもののO(n^3)場合、このしきい値が非常に高いことが判明しても驚かないでください。（何千もの要素？）

一部のアプリケーションでは、それぞれが複雑さを減らしながらBig-Oを増やす多くのアルゴリズムが存在する可能性があります。その結果、複数のアルゴリズムがさまざまなサイズで最適になります。

大きな整数の乗算は、この悪名高い例です。

*これらのしきい値の例は概算であり、大幅に変動する可能性があることに注意してください。多くの場合、10倍以上変動します。

于 2012-11-26T07:41:37.053 に答える
3

したがって、これよりも多くの問題がある可能性がありますが、最初の問題は、配列へのポインタの配列を使用していることです。また、2の累乗の配列サイズを使用しているため、これは、要素を連続して割り当て、整数除算を使用して数値の長い配列を行に折りたたむよりも、特に大きなパフォーマンスヒットです。

とにかく、それは問題についての私の最初の推測です。私が言ったように、もっとあるかもしれません、そして私がそれらを発見するとき、私はこの答えに追加します。

編集：これはおそらく問題にわずかな量しか寄与しません。問題は、 LuchianGrigoreが2の累乗でキャッシュラインの競合の問題を含むことを指している可能性があります。

私の懸念が素朴なアルゴリズムに有効であることを確認しました。代わりにアレイが連続している場合、ナイーブアルゴリズムの時間はほぼ50％短縮されます。これは、pastebinに（C ++ 11に依存するSquareMatrixクラスを使用して）このためのコードです。

于 2012-11-26T07:12:27.737 に答える