Dのこの並列コードはなぜひどくスケールされますか？

Question

C++とDの並列性を比較した実験です。同じデザインを使用して、両方の言語でアルゴリズム（ネットワークでのコミュニティ検出のための並列ラベル伝播スキーム）を実装しました。並列反復子はハンドル関数クロージャ）、それをグラフのすべてのノードに適用します。ここ

はDでイテレータで、std.parallelismからtaskPoolを使用して実装：

/** 
* Iterate in parallel over all nodes of the graph and call handler (lambda closure). 
*/ 
void parallelForNodes(F)(F handle) { 
    foreach (node v; taskPool.parallel(std.range.iota(z))) { 
     // call here 
     handle(v); 
    } 
} 

これは渡されたハンドル関数である：C++ 11の実装がほぼ同一である

auto propagateLabels = (node v){ 
     if (active[v] && (G.degree(v) > 0)) { 
      integer[label] labelCounts; 

      G.forNeighborsOf(v, (node w) { 
       label lw = labels[w]; 
       labelCounts[lw] += 1; // add weight of edge {v, w} 
      }); 

      // get dominant label 
      label dominant; 
      integer lcmax = 0; 
      foreach (label l, integer lc; labelCounts) { 
       if (lc > lcmax) { 
        dominant = l; 
        lcmax = lc; 
       } 
      } 

     if (labels[v] != dominant) { // UPDATE 
      labels[v] = dominant; 
      nUpdated += 1; // TODO: atomic update? 
      G.forNeighborsOf(v, (node u) { 
       active[u] = 1; 
      }); 
     } else { 
      active[v] = 0; 
     } 

     } 
    }; 

並列化にはOpenMPを使用します。スケーリング実験は何を示していますか？ここ

Iはまた、スレッドの数を2倍にし、実行時間を測定しながら、入力グラフのサイズを倍増、弱いスケーリングを調べます。理想は直線ですが、もちろん並列処理のためのオーバーヘッドがあります。私はdefaultPoolThreads(nThreads)を主な機能として使用して、Dプログラムのスレッド数を設定します。 C++のカーブはよく見えますが、Dのカーブは驚くほど悪く見えます。私は間違ったことをしていますか？ D並列性、またはこれはパラレルDプログラムのスケーラビリティに悪影響を及ぼしますか？

p.s.コンパイラフラグD用

：C++用rdmd -release -O -inline -noboundscheck

：-std=c++11 -fopenmp -O3 -DNDEBUG

PPS。 Dの実装が順次より並列に遅いので何かが、本当に間違っている必要があります。

のPPP。好奇心のために、ここでは両方の実装のためのMercurialのクローンURLです：私は完全にあなたのアルゴリズムが動作するようになっているか理解していないので、

• http://algohub.iti.kit.edu/parco/Prototypes/PLPd
• http://algohub.iti.kit.edu/parco/Prototypes/PLPcpp

Answer 1

は、それは言うのは難しいですが、コードがスレッドセーフではないように見えます。これは、アルゴリズムが必要以上に反復を実行する原因となります。

私はPLP.runの終わりにこれを追加しました：

writeln(nIterations); 

100件のスレッド​​3210

で10件のスレッドnIterations = 34
で1つのスレッドnIterations = 19
であなたが見ることができるように、それは長くはない取っていますstd.parallelismに関するいくつかの問題のために、より多くの作業をしているからです。

コードがスレッドセーフではないのはなぜですか？

あなたが並行して実行機能は共有、非同期labelsへのアクセス、nUpdated、およびactiveを有し、propagateLabelsです。これが引き起こしている奇妙な行動は誰に分かっているのですが、それは良いことではありません。

プロファイリングを開始する前に、スレッドセーフであるようにアルゴリズムを修正する必要があります。

Answer 2

Peter Alexanderが指摘するように、アルゴリズムはスレッドセーフではないようです。スレッドセーフにするには、異なるスレッドで同時に発生する可能性のあるイベントまたは定義されていない順序で発生する可能性のあるイベント間のすべてのデータ依存関係を排除する必要があります。これを行う1つの方法は、WorkerLocalStorage（std.parallelismで提供される）を使用していくつかの状態をスレッドに複製し、アルゴリズムの最後に比較的安いループで結果をマージすることです。

いくつかのケースでは、この状態を複製するプロセスが減少するようなアルゴリズムを書き込み、重労働を行うために（おそらくstd.algorithm.map又はstd.parallelism.mapと組み合わせて）std.parallelism.reduceを使用して自動化することができます。