5

現在の形式ではシングルスレッドであり、このプログラムの外側のループの反復ごとに内側のループで同じ純粋な関数を約 10 ～ 100 回呼び出す D2 プログラムがあります。呼び出し間にデータの依存関係はありません。つまり、他の呼び出しの結果を使用する呼び出しはありません。全体として、この関数は何百万回も呼び出されており、私のプログラムの主なボトルネックになっています。パラメータはほぼ毎回一意であるため、キャッシュは役に立ちません。

一見すると、これは並列化に最適な候補のように見えます。唯一の問題は、関数が呼び出しごとに約 3 マイクロ秒しかかからず、新しいスレッドを作成する待ち時間よりもはるかに短く、タスク プールにジョブを追加するオーバーヘッド (つまり、ミューテックスの取得、メモリの割り当て) をはるかに上回っていないことです。タスクに関する情報を保持し、タスク プールのキューで起こりうる競合に対処するなど)。このきめの細かい並列処理を利用する良い方法はありますか?

4

8 に答える 8

3

作業する独自のキューを持つ複数のスレッドを作成するのはどうですか? キューの重複がないため、ロックを作成する必要はありません。

于 2009-02-24T00:33:12.860 に答える
3

単一のタスクを実行するために各スレッドを起動してから、すぐにシャットダウンしないでください。

プログラムの開始時に、キュー (パイプ、または独自に作成した何らかのメカニズム) からのデータを待機しているコアごとにスレッドを作成します。すべてのスレッドが同じキューで待機するメカニズムを考え出すことができれば、さらに良いですが、キューの get メソッドを同期する必要があります...

計算する数百または数千のプロセスのブロックがある場合は常に、ブロック全体を次の空のキューにドロップします。

実際には、1 つまたは複数のスレッドがキューにフィードし、一連のスレッドがキューからのデータを処理し、1 つまたは複数のスレッドが結果を読み取って処理することになります。

完了後に何をすべきかを判断できるように、処理中の「アイテム」に十分なデータを入れる必要がある場合があります。それらはほぼ確実にオブジェクトである必要があり、状態情報を含める必要がある場合があります。

おそらく、コアよりも多くのスレッドが処理を行うことは望ましくありません。

編集: ThreadPoolExecutorなど、いくつかの並行ライブラリも見てください。並列ライブラリを忘れがちです (私がやったように)、それはおそらくまさにあなたが探していたものです (したがって、強調されています)

于 2009-02-24T00:41:17.117 に答える
2

なんて楽しい質問でしょう...あなたが指摘したように、このためのワークキューの従来のロックに関連するオーバーヘッドを支払う余裕はありません。可能であれば、既存のきめ細かいタスクベースのプログラミング環境の1つを使用してみることをお勧めします...これについては、3つの作業バケットで考えます。

問題の最初の部分は、安全性、正確性、並列化可能性を確保することです。関数が純粋であるため、それをカバーしているように聞こえます。

次に難しい部分は並行性の説明だと思います。具体的には、この関数は何度も呼び出されるとおっしゃっています。これをパイプライン化し、関数のスケジューリングをその作業から分離できますか？これをパイプライン化できない場合、それは並列ループ、ツリートラバーサルのように見えますか、それともこれよりも構造化されていませんか。具体的には、作業を重複させることができず、同時に複数のインスタンスまたは他の何かが実行されていることを確認できない場合は、 Amdahlに従い、純粋であっても事実上シリアルになります。作業をパイプラインにリファクタリングするためにできること、再帰的なツリートラバーサル（または並列ループ）、またはタスク間の明示的な依存関係を持つより非構造化された作業が必要な場合は、使用するライブラリに関係なく、ここで役立ちます。

私が考える最後の領域は、プラットフォームで効率的に実行できるようにすることです。これには、コードとスケジューリングコードの両方でオーバーヘッドと競合を減らし、シリアルコードが可能な限り効率的になるようにすることが含まれます。既存のライブラリの1つを使用できず、独自のライブラリを構築する必要がある場合は、作業を盗むキューを確認することをお勧めしますまた、セルフガイドスケジューリングアルゴリズムは、従来のロックを使用してもメリットが見られないことを示しています。これは、コストが関数のコストを上回り、コストを削減するためにロックフリーの手法を検討する必要があるためです。使用するキューにタスクをスケジュールして削除します。また、スケジューリングアルゴリズム内と関数内の両方で共有と競合に多くの注意を払う必要があります。これは、通常のブランチの予測ミスと命令スループットの問題に加えて、このレベルの粒度では、次のことも確認する必要があるためです。共有状態で、読み取りでも競合の原因になる可能性があるため、競合が発生します。

これがあまり具体的でなかったら申し訳ありませんが、それが役に立ったことを願っています。

于 2009-02-24T07:05:23.607 に答える
2

上記のように、この関数に入るたびにスレッドを開始しないでください。さらに、ジョブ作成のオーバーヘッドが十分に償却されるように、内部関数の 1 つの操作よりも大きな「ジョブ」粒度を使用してください。元のルーチンを次のように説明します。

void OuterFunction( Thingy inputData[N] )
{
  for ( int i = 0 ; i < N ; ++i )
    InnerFunction( inputData[i] );
}

問題を解決するには (ジョブ キュー システムが存在すると仮定します):

void JobFunc( Thingy inputData[], int start, int stop )
{
  for ( int i = start ; i < stop ; ++i )
    InnerFunction( inputData[i] );  
}
void OuterFunction( Thingy inputData[N], int numCores )
{
   int perCore = N / numCores; // assuming N%numCores=0 
                               // (omitting edge case for clarity)
   for ( int c = 0 ; c < numCores ; ++c )
     QueueJob( JobFunc, inputData, c * perCore, (c + 1) * perCore );
}

元の質問で言うように、入力データが完全に独立している限り、ロックする必要はありません。同期は、スレッド間に依存関係があり、ここでは依存関係がない場合にのみ必要です。

また、このレベルのパフォーマンスでは、マイクロ最適化が適切になり始めます。最も重要なのは、キャッシュの局所性です。プリフェッチは、驚くほど長い道のりを歩むことができます。

次に、SIMD をベクトル化して、1 つのレジスターで 4 つの入力ポイントを同時に実行できる可能性を検討します。4 つのコアと 4 幅の SIMD を使用すると、理論的には 16 倍のスピードアップを得ることができますが、これは、InnerFunction が行っている作業のほとんどが固定の数学関数であると想定しています。

于 2009-02-24T02:01:41.977 に答える
1

これは、SIMD命令が役立つもののように聞こえます。自動ベクトル化コンパイラを使用している場合は、4つの値を同時に操作するように関数を書き直すことができ、コンパイラはそれを適切なSSE命令に凝縮できます。これは、関数呼び出しのオーバーヘッドを削減するのに役立ちます。コンパイラがコードの自動ベクトル化に長けていない場合は、SSE組み込み関数を使用して、関数の本体をプログラムするためにアセンブリレベルにほぼ到達できる可能性があります。

于 2009-02-24T01:35:11.947 に答える
1

プログラムの構造によっては、呼び出しのグループを常に 1 つのタスクに結合できます。各タスクが 50 回の関数呼び出しを行う場合、タスク管理のオーバーヘッドはそれほど大きな要因ではなくなります。

于 2009-02-24T00:36:21.340 に答える
0

Compare-and-Swap を使用してループを裏返しにして、アトミックなロック フリー インクリメントを取得できる場合があります。

void OuterFunction()
{
  for(int i = 0; i < N; i++)
    InnerFunction(i);
}

に行く：

void OuterFunction()
{
   int i = 0, j = 0;

   void Go()
   {
      int k;
      while((k = atomicInc(*i)) < N)
      {
         InnerFunction(k);

         atomicInc(*j);
      }
   }

   for(int t = 0; t < ThreadCount - 1; t++) Thread.Start(&Go);

   Go(); // join in

   while(j < N) Wait(); // let everyone else catch up.
}

編集:私のスレッドは錆びているため、名前がすべて間違っているためコンパイルできません

于 2009-02-24T17:50:29.233 に答える
0

呼び出し間にデータの依存関係はありません。つまり、他の呼び出しの結果を使用する呼び出しはありません。

これは並列化に役立ちますが、関数に副作用がまったくないことを絶対に確認してください。関数がデータ構造を更新している場合、それはスレッドセーフですか? IO を実行している場合、関数の実行を並列化すると、IO がボトルネックになってしまうのでしょうか?

これらの質問に対する答えが「はい」の場合は、前の提案で問題ありません。関数の実行をスレッドごとにできるだけ多く割り当てて、アプリの粒度を最大化してみてください。

それでも、おそらく大規模な並列処理から何のメリットも得られないでしょうが、もう少しスピードアップできるかもしれません...

于 2009-06-25T20:33:21.037 に答える