相互依存スレッドの並列計算時間の測定

Question

並列プログラムで実行時測定に関する質問があります（私はC++を使用しましたが、より一般的です）。

いくつかの短い説明：3つのスレッドが並列（pthread）に実行され、同じ問題がさまざまな方法で解決されています。各スレッドは、自身の計算における自分自身の状態/利用可能な情報に応じて、他のスレッドをスピードアップするために、他のスレッドに情報を渡すことができる（例えば、一方のスレッドによって得られた部分解は、最初のスレッドの準備が整うとすぐに、プロセス全体が停止します。 私は、問題が解決されるまで、ランタイムを最初から評価するための独自の時間測定をしたいと考えています。 （最終的には、並列計算による相乗効果を使用する方が速いのか、単一スレッドで計算するのかを判断したい）

私の目では、（オペレーティングシステムが単一スレッドを一時停止/一時停止しているため）、プロセス内で情報が渡される時点は、各プロセスの状態で決定的ではありません。つまり、ある情報はスレッド1のCPU時間のxxx単位の後に取得されますが、スレッド2がyyyの後にこの情報を受け取るか、CPU時間のzzz単位が計算に費やされたかどうかは制御できません。この情報がいずれの場合にもスレッド2の計算を終了したと仮定すると、スレッド2の実行時間はオペレーティングシステムの動作に応じてyyyまたはzzzのいずれかであった。

ランタイム比較のための確定的な動作を得るにはどうすればよいですか？各スレッドを「妨げられない」（マルチコアマシン上で）実行するようにオペレーティングシステムを命令することはできますか？実装（C++）に基づいて何かできることはありますか？

また、そのような実装のランタイム（時間の利得）を評価するための他の概念がありますか？

敬具 マーティン

Answer 1

誰かが同じ文で用語「決定論」と「マルチコア」を使用して任意の時間は、それが鳴って警鐘を設定します:-)あなたのプログラムで非決定論の二つの大きな源がある

：1）オペレーティングシステムは、OSのジッタとスケジューリングの決定を通じてスレッドのタイミングにノイズを追加します。 2）アルゴリズムは、（部分解の）通信が起こる順序に応じて、プログラムが異なる経路をたどるためである。

プログラマとしては、OSノイズについてはあまりありません。標準OSは、専用の（休止状態の）ノード上で実行されているプログラムに対しても、多くのノイズを追加します。計算ノードのための特別な目的のオペレーティングシステムは、このノイズを減らすために何らかの方法、例えばBlue Gene systems exhibit significantly less OS noise and therefore less variation in timingsに行きます。

アルゴリズムに関しては、同期を追加することでプログラムに確定性を導入することができます。 2つのスレッドが同期して、例えば部分解を交換する場合、同期の前後の計算の順序は決定論的です。現在のコードは非同期で、あるスレッドが部分的な解決策を「送信」するが、それが「受信」されるのを待つことはありません。計算をステップに分割し、各ステップの後にスレッド間を同期させることで、これを確定的なコードに変換することができます。例えば、スレッドごとに：

1. 計算ワンステップ
2. 録音部分解（もしあれば）
3. バリア - 他のすべてのスレッドのために他のスレッドから
4. 読み出した部分解を待つ
5. 繰り返し1 -4

もちろん、このコードは他のすべてのスレッドが完了するのを待たなければならないので次のステップに進む前に計算してください。

おそらく、非決定論を受け入れ、統計的方法を使用してタイミングを比較するのが最もよい方法です。与えられた数のスレッドに対して何度もプログラムを実行し、タイミングの範囲、平均および標準偏差を記録します。あなたが知っているほど十分かもしれません。特定の数のスレッドに対するすべての実行の最大計算時間、または「4スレッドから8スレッドへの増加がランタイムをどのくらい減らすか」などのより複雑な質問に答えるために、Student's t-testなどの統計テストが必要な場合があります。 DanielKOが述べているように、タイミングの変動は実際にユーザーが経験するものなので、これらを測定して統計的に数値化するのは理にかなっています。

Answer 2

このような測定を使用することは何ですか？

OSスケジューラを（キャッシュ、MMUなどを使用する他のプロセスのような間接的なイベントによっても）混乱を生じさせないように設定すると、実際の並列プログラムの使用？

現代のOSは、あなたが金属に直接話をしている場合を除き、あなたの決定論的測定は唯一の非現実的ではありませんアプリケーション等の一般的な取り扱い割り込み、メモリ管理、スレッドのスケジューリング、オーバー制御を取るようにするためにそれは、かなり稀ですがあなたのプログラムのユーザーは、あなたが測定したときと同じように金属に近い場合を除き、それらを経験することはありません。

私の質問は、なぜあなたのプログラムを測定するために厳しい条件が必要なのですか？一般的なケースでは、ユーザーが最もよく見るように、変動を受け入れてください。特定のアルゴリズム/実装のスピードアップがバックグラウンドノイズと区別できないほど重要でない場合、それは実際のスピードアップの分数を知るよりも、私にとってはより有用な情報です。