47

私は1つの行列乗算を実装しましたboost::numeric::ublas::matrix（私の完全な作業ブーストコードを参照してください）

Result result = read ();

boost::numeric::ublas::matrix<int> C;
C = boost::numeric::ublas::prod(result.A, result.B);

標準アルゴリズムを使用した別のもの (完全な標準コードを参照):

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
                                    vector< vector<int> > B) {
    int n = A.size();

    // initialise C with 0s
    vector<int> tmp(n, 0);
    vector< vector<int> > C(n, tmp);

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

これは私が速度をテストする方法です：

time boostImplementation.out > boostResult.txt
diff boostResult.txt correctResult.txt

time simpleImplementation.out > simpleResult.txt
diff simpleResult.txt correctResult.txt

どちらのプログラムも、2 つの 2000 x 2000 行列を含むハードコードされたテキスト ファイルを読み取ります。両方のプログラムは、次のフラグを使用してコンパイルされました。

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic

実装に15 秒、ブーストの実装に4 分以上かかりました。

編集：それをコンパイルした後

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out

ikjアルゴリズムで 28.19秒、Boost で60.99 秒でした。そのため、Boost は依然としてかなり低速です。

ブーストが私の実装よりもずっと遅いのはなぜですか?

4

3 に答える 3

51

TJD が指摘したように、uBLAS バージョンのパフォーマンスの低下は、後者のデバッグ機能によって部分的に説明できます。

デバッグをオンにした uBLAS バージョンの所要時間は次のとおりです。

real    0m19.966s
user    0m19.809s
sys     0m0.112s

デバッグをオフにした uBLAS バージョンの所要時間は次のとおりです (-DNDEBUG -DBOOST_UBLAS_NDEBUGコンパイラ フラグが追加されています)。

real    0m7.061s
user    0m6.936s
sys     0m0.096s

したがって、デバッグをオフにすると、uBLAS バージョンはほぼ 3 倍高速になります。

残りのパフォーマンスの違いは、uBLAS FAQの次のセクション「Why is uBLAS so much slow than (atlas-BLAS)」を引用することで説明できます。

ublas の重要な設計目標は、可能な限り一般的なものにすることです。

この一般性には、ほとんどの場合、代償が伴います。特に、prod関数テンプレートは、疎行列や三角行列など、さまざまな種類の行列を処理できます。幸いなことに、uBLAS は密な行列乗算、特にaxpy_prodとblock_prod. さまざまな方法を比較した結果は次のとおりです。

ijkalgorithm   prod   axpy_prod  block_prod
   1.335       7.061    1.330       1.278

ご覧のとおり、axpy_prodとの両方block_prodが実装よりもいくらか高速です。I/O を使用せずに計算時間だけを測定し、不要なコピーを削除し、ブロック サイズを慎重に選択するblock_prod(私は 64 を使用) ことで、違いはさらに大きくなります。

uBLAS FAQおよび効果的な uBlas と一般的なコードの最適化も参照してください。

于 2012-06-19T23:36:57.100 に答える
13

あなたのコンパイラは十分に最適化していないと思います。uBLAS コードはテンプレートを多用し、テンプレートは最適化を多用する必要があります。1000x1000 行列のリリース モードで MS VC 7.1 コンパイラを介してコードを実行しました。

10.064s for uBLAS

7.851ベクトルの s

違いはまだありますが、決して圧倒的ではありません。uBLAS のコア コンセプトは遅延評価であるためprod(A, B)、必要な場合にのみ結果を評価します。たとえばprod(A, B)(10,100)、実際にはその 1 つの要素のみが計算されるため、すぐに実行されます。そのため、実際には、最適化できる行列全体の乗算専用のアルゴリズムはありません(以下を参照)。しかし、宣言して、図書館を少し助けることができます

matrix<int, column_major> B;

実行時間を s に短縮し4.426ます。これは、片手を縛った状態で関数を打ち負かします。この宣言により、行列を乗算するときにメモリへのアクセスがよりシーケンシャルになり、キャッシュの使用が最適化されます。

PS uBLAS のドキュメントを最後まで読むと、行列全体を一度に乗算するための専用関数が実際にあることに気付くはずです。2つの機能 -axpy_prodとopb_prod. そう

opb_prod(A, B, C, true);

最適化されていない row_major B 行列でも数8.091秒で実行され、ベクトル アルゴリズムと同等です

PPS さらに多くの最適化があります:

C = block_prod<matrix<int>, 1024>(A, B);

4.4B が column_ または row_ major であるかどうかに関係なく、s で実行されます。「関数 block_prod は、大規模な密行列用に設計されています」という説明を検討してください。特定のタスクには特定のツールを選択してください。

于 2012-06-21T11:23:50.883 に答える
2

小さなウェブサイトMatrix-Matrix Product Experiments with uBLASを作成しました。これは、マトリックス マトリックス製品の新しい実装を uBLAS に統合することです。すでにブースト ライブラリをお持ちの場合は、追加の 4 つのファイルのみで構成されます。そのため、ほとんど自己完結型です。

他の人がさまざまなマシンで簡単なベンチマークを実行できるかどうかに興味があります.

于 2016-01-22T22:45:32.113 に答える