まず、perf
を使用することにより、アプリケーションがその時間を費やしている場所で超簡単に見てみましょう:
perf record ./knights_tour_omp 3 12
perf report
# Overhead Command Shared Object Symbol
# ........ ............... ................... .................................................................................................
#
53.29% knights_tour_om libc-2.19.so [.] malloc
23.16% knights_tour_om libc-2.19.so [.] _int_free
10.31% knights_tour_om libc-2.19.so [.] _int_malloc
4.78% knights_tour_om knights_tour_omp [.] _Z13continue_tourIZ4mainEUlRKSt6vectorIiSaIiEEE_EmRK5GraphS4_RKS0_IcSaIcEEiiRT_.constprop.119
2.64% knights_tour_om libc-2.19.so [.] __memmove_ssse3_back
1.48% knights_tour_om libc-2.19.so [.] malloc_consolidate
あなたのアプリケーションは、それが時間の割り当てとメモリを解放しますすべてを費やしています。 malloc
is is not fully lockedという報告がありますが、うまく並列化していないようです。
これは、繰り返しのたびにとpath
個のベクトルをコピーすることによって発生することがわかります。
visited[n] = 1;
path.emplace_back(n);
count += continue_tour(g, path, visited, depth+1,remain-1, cb);
visited[n] = 0;
path.pop_back();
しかし、並列ループのために、あなたは、スレッドごとに作業コピーを作成する必要があります。幸いなことにDFSを使用すると、必ずしも、それをする必要はありませんあなたは状態を再利用し、それを復元することができ、素晴らしい特性を持っていますこのため、元の動作で別のパスを作成する必要があります。
この小さな変更により、シリアルランタイムが22秒から2.65秒に短縮されました。さらに2つのスレッドを使用すると、2.0秒になります。スピードアップはありますが、それほど良くありません - なぜですか?これを説明するために、私は大規模なシステムで4つのスレッドを使用しました。ここでは、score-pと記録されたアプリケーションの実行をVampirに示します。
赤青のスレッドが空転している意味、暗黙のバリアで、実際の作業です。常に3つまたは1つのアクティブスレッドがあるようです。理由は簡単です:ボード上のポジションのほとんどは、4つまたは2つのネイバーを持っていますが、そのうちの1つはすでに訪問されているため、このループの繰り返しは即座に完了します。したがって、実際の作業はループの3回または1回の繰り返しです。これは2つのスレッドの特に悪いマッチです。 3スレッドの場合、実行時間は1.7秒に短縮されます
注:g5.3のE5-2690 @ 2.90 GHzではターボは常にありません。ランタイムの差異を補償するための配慮はありませんでした。
1つのループでその問題の並列性が非常に悪くなることを考慮すると、並列ループをネストすることができます。私はあなたがそれを試してみることをお勧めしますが、私はそれがうまくいくとは思わない。タスクは他のタスクを生成できるので、このコンテキストではタスクがうまくいくと思います。したがって、各再帰的なステップをタスクとして生成し、OMPランタイムに適切なスケジューリングを把握させることができます。しかし、タスクがあまりに短くならないように、特定のdepth
に制限するようにしてください。
ツールを使用することの重要性を強調したい:パフォーマンス分析ツールを使用しないでパフォーマンスの問題を理解しようとすると、デバッガなしでバグを把握するようなものになります。 perf
はLinuxですぐに利用でき、基本的な使い方は非常に簡単です。しかし、それは非常に強力です(高度な使い方にはいくつかの落とし穴があります)。
追加の注釈:OpenMPでは、さまざまなコンパイラを試す価値があります。たとえば(固定)タスキングコードでは、gccは4スレッドを超えて拡張することはできませんが、intelコンパイラ/ ompランタイムは24スレッドまで高速化します。
詳細な分析をいただきありがとうございます。私はパスをコピーして訪問したパラレルレベルと、それらを突然変異させるシーケンシャルレベルを分けました。 OpenMPのバージョンは、OpenMP以外のバージョンよりわずかに多くなりました。新しいコードはhttps://gist.github.com/jmoy/2151e6d7070a6ce18aa9298fbe050062 –
です。@JyotirmoyBhattacharyaは、再帰の外側で 'omp parallel' /' omp single'を移動します。私はネストされたタスク/パラレル/単一のwoudlのためのセマンティクスが何であるかも分かりません。それはタスクランタイムを混乱させる。 – Zulan
BTW:gccでは、小さな例ではまだ4スレッドを超えて拡張できませんが、intelコンパイラ/ ompランタイムは24スレッドまで拡張できます。 – Zulan