Clever Geek Handbook

タスクの並列化。 「完全な並列化」の場合。 パート1

依存関係のないコード並列化



はじめに


この記事の第1部では、個々の反復間に依存関係がなく、正しく並列実行できる場合の成功例でのループの並列処理へのアプローチについて説明します。 第2部では、このような並列化を管理するために.NET 4.0で登場したメカニズムを検討し、これらのメカニズムの複雑さを明らかにします。







データが処理されるサイクルを検討してください。

  1. for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }



  2. for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }



  3. for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }



  4. for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }





サイクルの本体のロジックが、特定の反復での計算の結果が他の反復の計算の結果に依存しないようなものである場合、すべての反復を並列で実行できるため、このサイクルは「完全に並列」です。プロセッサ上のこのコア。



同じ定義を同様のforeachループに適用できます。 それから、反復計算の順序は重要ではありません。



並列ループのアプローチ


メソッド自体を実装してサイクルを並行して実行し、どのような困難に遭遇するかを見てみましょう。



そのため、次のようなメソッドを作成します。



  1. public static void ParallelFor （ int from、 int to、Action < int > body ） ;




toからtoまでのすべての値（後者は含まない）に対してbodyを実行し、最大のパフォーマンスを達成するために複数のスレッド間で実行を並列化する必要があります。 並列化はどのくらい可能ですか？



並列度の決定


このマシンのプロセッサにあるコアと同じ数のスレッドを使用するのが論理的であるという妥当な判断があります。 この決定により、各コアが完全にロードされます。 スレッドが増えると、スレッド間の切り替えのオーバーヘッドが少なくなり、コアの一部がアイドル状態になります。



このアプローチ-多くの場合、コアへのフローの観点からは、すべてのスレッドがプロセッサ上の計算のみに従事している理想的な計算モデルに基づいていますが、本当です。 ただし、スレッドを増やすと便利な場合があります。 たとえば、スレッドが作業の半分をリソースの待機に費やしている場合、この時点ではプロセッサはまだアイドル状態であり、ワーカースレッドの数が増えるとパフォーマンスが向上する可能性があります。



したがって、「コアごとに1つのスレッド」という単純なオプションから開始する価値がありますが、他の戦略を検討する準備ができていることがわかります。



使用可能なコアの数を取得するには、System.Environment.ProcessorCountプロパティを使用できます。 ハイパースレッディングを考慮に入れたコアの数が返されることに注意してください。つまり、存在する場合、すでに2倍になった「論理的な」コアの数が返されます。



上記に基づいて、論理的な（やや単純ですが）実装を次に示します。

  1. public static void ParallelFor （ int from、 int to、Action < int > body ）
  2. {
  3. //スレッドの数と各スレッドのデータブロックのサイズを決定します
  4. intサイズ= to - from ;
  5. int numProcs =環境。 ProcessorCount
  6. int range = size / numProcs ;
  8. //データを分割し、すべてのスレッドを開始して完了を待ちます
  9. var threads = new List < Thread > （ numProcs ） ;
  10. for （ int p = 0 ; p < numProcs ; p ++ ）
  11. {
  12. int start = p * range + from ;
  13. int end = （ p == numProcs - 1 ） ？
  14. to ： start + range ;
  15. スレッド。 追加 （ 新しいスレッド（ （ ） => {
  16. for （ int i = start ; i < end ; i ++ ） body （ i ） ;
  17. } ） ） ;
  18. }
  19. foreach （スレッド内の var thread ）スレッド。 開始 （ ） ;
  20. foreach （スレッド内の var thread ）スレッド。 参加 （ ） ;
  21. }




このバージョンの重要な欠点は、毎回新しいスレッドが作成/完了することです。これはかなり高価な操作であるためです（特に、現在実行されている関数がない場合でも、各スレッドは1Mのメモリをスタックに予約します）。



別の問題は、新しいスレッドの作成からも発生します。 本文には、ParallelFor呼び出しも含むコードが与えられているとします。 この場合、実行プロセス中に作成されるスレッドはnumProcsを超えず、2倍になり、スレッド間の切り替えのコストが高すぎる状況が発生する可能性があります（「過剰なマルチスレッド」）。



静的反復分布


したがって、スレッドを手動で作成する代わりに、スレッドプールを使用することをお勧めします。

  1. public static void ParallelFor （ int from、 int to、Action < int > body ）
  2. {
  3. intサイズ= to - from ;
  4. int numProcs =環境。 ProcessorCount
  5. int range = size / numProcs ;
  7. int remaining = numProcs ;
  9. //同期オブジェクト。作業の完了を判断します
  10. 使用 （ ManualResetEvent mre = new ManualResetEvent （ false ） ）
  11. {
  12. //すべてのタスクを作成します
  13. for （ int p = 0 ; p < numProcs ; p ++ ）
  14. {
  15. int start = p * range + from ;
  16. int end = （ p == numProcs - 1 ） ？ to ： start + range ;
  18. スレッドプール QueueUserWorkItem （ デリゲート {
  19. for （ int i = start ; i < end ; i ++ ）
  20. ボディ（ i ） ;
  21. //最後のタスクが完了したかどうかを確認します
  22. if （インターロック。 減少 （ ref remaining ） == 0 ）
  23. mre。 セット （ ） ;
  24. } ） ;
  25. }
  26. //すべてのタスクが完了するまで待ちます
  27. mre。 WaitOne （ ） ;
  28. }
  29. }


このソリューションは、すでに過度のマルチスレッド化やスレッド作成のコストから解放されています。 この状況でこのサイクルの可能な限り速い開発を防ぐことができるものは他にありますか？



すべての反復が時間的に短く、ほぼ同等のコストがかかる場合、上記のアプローチは最適に近いです。



そして、いくつかの反復が迅速に完了し、何倍も長くなると想像すると、プールからのスレッドは、「長い」反復の実行者として幸運ではなかったが、他のスレッドよりも数倍長く動作します。 同時に、並列動作全体の動作時間は最も遅いコンポーネントの動作時間によって決定されるため、結果として、残りのスレッドはすべての「作業」を行ってアイドル状態になり、一方「不運な」スレッドは全員を遅延させます。



このような状況での最小稼働時間を確保するために、

動的反復分布


静的な分離から動的に移行することができます。つまり、各スレッドに特定の「部分」の作業を行い、それを行った後、元に戻す作業がまだ残っている場合は次の部分を受け取ります。



このアプローチは、次のコードで説明できます。



  1. public static void ParallelFor （ int from、 int to、Action < int > body ）
  2. {
  3. int numProcs =環境。 ProcessorCount
  4. //残りの数
  5. int remainingWorkItems = numProcs ;
  6. int nextIteration = from ;
  8. 使用 （ ManualResetEvent mre = new ManualResetEvent （ false ） ）
  9. {
  10. //タスクを作成します
  11. for （ int p = 0 ; p < numProcs ; p ++ ）
  12. {
  13. スレッドプール QueueUserWorkItem （ デリゲート
  14. {
  15. intインデックス;
  16. //実行ごとに1つの要素を選択します
  17. while （ （ index = Interlocked。Increment （ ref nextIteration ） -1 ） < to ）
  18. {
  19. ボディ（インデックス） ;
  20. }
  21. if （インターロック。 デクリメント （ ref remainingWorkItems ） == 0 ）
  22. mre。 セット （ ） ;
  23. } ） ;
  24. }
  25. //すべてのタスクが完了するまで待つ
  26. mre。 WaitOne （ ） ;
  27. }
  28. }




このコードは、予測不可能なランタイムでの長い反復には適していますが、高速の反復では同期コストが多すぎます。



バランスの取れたアプローチ


したがって、並列化されたサイクルの性質によっては、スレッド間のタスクを静的に分離する戦略と動的な戦略の両方が有利であることがわかります。 いくつかのバランスの取れた戦略が中間の場合に成功するかもしれないと仮定することは論理的です。



以下はそのコードの変形です。 アイデアは、「部分」を1つの要素だけではなく、静的分布の場合よりも幾分多くすることです。



  1. public static void ParallelFor （ int from、 int to、Action < int > body ）
  2. {
  3. int numProcs =環境。 ProcessorCount
  4. int remainingWorkItems = numProcs ;
  5. int nextIteration = from ;
  6. //データの「部分」のサイズ
  7. const int batchSize = 3 ;
  8. 使用 （ ManualResetEvent mre = new ManualResetEvent （ false ） ）
  9. {
  10. for （ int p = 0 ; p < numProcs ; p ++ ）
  11. {
  12. スレッドプール QueueUserWorkItem （ デリゲート {
  13. intインデックス;
  14. while （ （ index = Interlocked。Add （ ref nextIteration、batchSize ） -batchSize ） < to ）
  15. {
  16. int end = index + batchSize ;
  17. if （ end > = to ）
  18. end = to ;
  19. for （ int i = index ; i < end ; i ++ ）
  20. ボディ（ i ） ;
  21. }
  22. if （インターロック。 デクリメント （ ref remainingWorkItems ） == 0 ）
  23. mre。 セット （ ） ;
  24. } ） ;
  25. }
  26. mre。 WaitOne （ ） ;
  27. }
  28. }




ここで、データ部分のサイズは定数によって設定され、それを変更して、タスクの静的分散と動的分散の間で必要なレベルを選択します。



おわりに


いずれにしても、特定のケースの最適な設定は、計算の性質によって決まります。 しかし、ほとんどの場合、多かれ少なかれ大規模な「サービス」の動的な分散との妥協はまったく受け入れられるかもしれません。 これが、.NET 4での並列ループ実行のためのライブラリメソッドの実装方法です。これについては、記事の第2部で説明します。



PSこの記事は、「 並列プログラミングのパターン：.NET FRAMEWORK 4およびVISUAL C＃を使用した並列パターンの理解と適用 」という本の影響を受けて書かれたもので、処理を伴う無料翻訳と見なすことができます。



______________________

テキストは©SoftCoder.ruによってブログエディターで作成されます。




UPD：第二部-実用的： habrahabr.ru/blogs/net/104103


More articles:


All Articles