OpenMP：深さ優先探索のための良い戦略

Question

私は、ブルートフォース検索のclosed Knight's toursを行うC++プログラムを書いています。コードはhereです。

OpenMPを使用してこれを並列化したいと思います。私の問題は、十分な程度の並列性を作り出す方法でこれを行うことです。現在、私のコードのthe relevant portionこの

#pragma omp parallel for reduction(+:count) if (depth==4) 
    for (size_t i=0;i<g.neighbours[last].size();i++){ 
    auto n = g.neighbours[last][i]; 
    // See if n can be used to extend or complete the tour 

if (depth==4)のように見えることはわからない、あまりにも多くの並列タスクが作成されていることが、十分に忙しいすべてのプロセッサを維持するために作成されている一方で作るために私の試みです。 depth==2を設定しても、プログラムのランタイムは変更されません。

これはうまくいかないようです。 3x12問題の場合、私のデュアルコアプロセッサでは、OpenMPバージョンで消費される合計CPU時間は約130秒ですが、OpenMPのないシングルスレッドバージョンでは約40秒のCPU時間がかかります。

OpenMPの使い方の良さや、なぜこの問題には適していないのかをお聞かせください。

更新：@ Zulanのおかげで、私はnewer versionが、はるかに高速な順次パフォーマンスと優れた並列化を備えたOpenMPタスクを使用しています。

Answer 1

まず、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スレッドまで高速化します。