このソルバーコードをどのように並列化できますか

Question

リンクとノードを持つグラフ構造でシミュレーションを行うコードを最適化して並列化しようとしています。私は、各スレッド場所のため、このクラスのインスタンスを作成します

class myDemoClass 
{  
    bool volatile *isDone; 
public: 

    void ExecuteSlice() 
    { 
     for(long i = TotalCount() - mThreadIndex; i >= 1; i -= threadCount) 
     { 
      long k = linkOrder[i]; 
      Execute(k); 
     } 
    } 

    void Execute(long k) 
    { 
     long link = firstLink[k]; 
     if (link == 0) 
     { 
      isDone[k] = true; 
      return; 
     } 
     double d = 0.; 
     for(; link != 0; link = nextLink[link]) 
     { 
      long kk = getNode(link); 

      for(int x = 0; ! isDone[kk]; x++) 
       {} // Wait until data is ready. Time too short for sleep or event 

      d += fak[link]*res[kk]; 
     } 
     d += res[k]; 
     double d2 = d/fak2[k]; 
     res[k] = d2; 
     res2[k] += d2; 

     isDone[k] = true; 
    } 
} 

：

void ExecuteAll() 
{ 
    for(long i = TotalCount(); i >= 1; i--) 
    { 
     long k = linkOrder[i]; 
     long link = firstLink[k]; 
     if (link == 0) 
      continue; 

     double d = 0.; 
     for(; link != 0; link = nextLink[link]) 
     { 
      long kk = getNode(link); 
      d += fak[link]*res[kk]; 
     } 
     d += res[k]; 
     double d2 = d/fak2[k]; 
     res[k] = d2; 
     res2[k] += d2; 
    } 
} 

私はこのようなクラスを実装することにより、複数のスレッドで動作するようにこれを作り直さ：メインのホットスポットは、このようなループがあります各スレッドはiのすべての値のスライスで動作します。私は新しい配列bool volatile *isDoneを導入しました。処理されていないノードの結果を使用してはならないからです。 for(;...;){}ループの代わりにスリープまたはイベントを挿入しようとしましたが、待機状態がこれに対して短すぎることが判明しました。

これはうまくいくようです。グラフが開始点からますます展開し、結果が正しいので、Execute（）へのすべての呼び出しの10％だけが待機ループに入る必要があります。

しかし、驚くべきことに、8つのスレッドで新しいコードを使用すると、8コアのXEONマシンで測定可能なパフォーマンスの向上（または損失）はありません。私はこのコードがキャッシュ無効化に関して最適ではなく、主にisDoneとresが複数のコアから書き込まれて読み込まれることを知っています。しかし、ほとんどの場合、逆参照されたインデックスは互いにかなり離れています。グラフには約1.000.000のノードとリンクがあります。

このコードの並列性を改善するにはどうすればよいですか？

Answer 1

volatileのようにコードをスレッドセーフにすることはできません。 volatileは、値を常に再読み込みすることによって変数を外部デバイスにマップするシングルスレッドのアプリケーションで役立ちますが、スレッドに対しては、ステートメントがコンパイラによって並べ替えられるだけでなく、プロセッサによって並べ替えられるため不十分です。ライブラリやコンパイラ固有の実装（Win32ではインターロック関数、gccではAtomic Builtinsなど）によって提供される適切なマルチスレッドプリミティブを使用する必要があります。同様に、あなたの他のデータ構造がマルチスレッドの変更に対して安全であることは明らかではありません。

パフォーマンスに関しては、グラフ構造についてわからないし、コードがあまりにも抽象的すぎて問題を解決することができないため、問題の原因を特定するのは難しいです。ただし、まだ処理されていないリンクを繰り返し処理するのに多くの時間を費やしているようです。理想的には、それを逆にして、依存関係のないリンクを処理し、それが完了したら、このリンクに依存するリンクを開始するなど、待機しないことを意味します。おそらくトポロジカルな並べ替えのようなものがここで助けになるでしょう。

Answer 2

OpenMPがあるデファクト標準、あなたは、単にスレッド管理についてはあまり気にせずに、複数のコアで実行したい構造的に同一のタスクに配列処理コードの並列化のために、現在のコンパイラではよくサポートされています。それを見て、それはあなたの考えを明確にするのに役立ち、問題を解決するかもしれません。

これは純粋なCPUバウンドタスクに最適です。データが到着するのを待っているので、それが当てはまるかどうかはわかりません。その場合、ロジックをマルチスレッド化することは、期待しているか、または望みどおりには役に立たないかもしれません。有用である可能性が

Answer 3

いくつかの考え：

• 私は（何もすぐに一例として、心に来ることはありません）も並列化することが知られているいくつかの計算を使用してテストするだろうと、あなたのスレッドコードの作品を​​作ること。次に、シングルスレッド実装とマルチスレッド実装をテストし、スレッド化されたアプリケーション全体が期待通りに動作することを確認できます。
• アルゴリズムが正しく並列化されていることを確認してください。 Steveは、CPUとCPUの混在のように見えますが、CPUのバウンド計算は並列処理に最適です。どのようなgetNode()に依存するIOバインドされる可能性がありますマルチスレッドアルゴリズムを使用して得ることができます制限します。コードのプロファイリングとベンチマークを行うことで、最適化の効果を最大限に引き出すことができます。
• 他のポスターと同様にマルチスレッド同期にvolatileを使用しないでください。それは確かに今あなたのために働くかもしれませんが、将来それが壊れないという保証はありません。今から数ヶ月後に微妙に壊れた最悪のシナリオを考えてみましょう。すべてのシミュレーション結果をわずかに破壊しますが、明らかにするには十分ではありません。
• for "wait"ループも疑わしいので、適切なスレッド待機のために変更する必要があります。スレッドがこのループで「待機」しているときには、別のスレッドで実際の作業を行うことで、CPU時間を浪費してしまいます。この待機ループが10％の時間しか使用されていない場合は、利益は小さくなりますが、その使用量は常に小さくなるという保証はありません。