4

私は操作を実行しています。CalculateSomeData と呼びましょう。CalculateSomeData は、1..x の番号が付けられた連続する「世代」で動作します。実行全体の世代数は、CalculateSomeData への入力パラメーターによって固定され、先験的に知られています。1 つの世代が完了するまでに 30 分から 2 時間かかります。その変動性の一部は入力パラメータによるものであり、制御することはできません。ただし、その変動の一部は、ハードウェアの容量、他のプロセスからの CPU 負荷、ネットワーク帯域幅の負荷などによるものです。世代ごとに制御できるパラメーターの 1 つは、CalculateSomeData が使用するスレッドの数です。現在、それは修正されており、最適ではない可能性があります。私' 各世代にかかる時間を追跡し、スレッドの数を微調整して、連続する各世代が前の世代の計算時間を改善する (時間を最小化する) アルゴリズムを用意したいと考えています。どのようなアプローチを使用する必要がありますか? 遺伝的アルゴリズムはどの程度適用可能ですか? 直感的には、この範囲はかなり狭くなることがわかります。おそらく、デュアル クアッド コア プロセッサ マシンでは 1 ～ 16 スレッドです。

ポインタ、疑似コードなどは大歓迎です。

4

3 に答える 3

2

計算が完全に CPU バウンドの場合、スレッドの数はマシンのコアの数と同じにする必要があります。そうすれば、コンテキスト スイッチの数を最小限に抑えることができます。

計算に I/O、ネットワーク、同期、または実行をブロックする何かが含まれる場合は、制限リソースを見つけて使用率を測定する必要があります。使用率を監視し、使用率が 100% に近づくまでゆっくりとスレッドを追加する必要があります。限られたリソースを飽和させるために、スレッドはできるだけ少なくする必要があります。

于 2010-09-21T17:14:17.613 に答える
2

進化的アルゴリズムはどうですか。

推測から始めます。CPU コアごとに 1 スレッドが適切に思えますが、実行中のタスクによって異なります。

世代内の各タスクの平均時間を測定します。前の世代の所要時間と比較してください。(実質的に無限の時間とジェネレーション 0 のスレッドが 0 であると仮定します)。

最新世代のタスクの平均時間が前の世代よりも優れている場合は、最後の手順と同じ方向にスレッド数を変更し続けます (したがって、最後の世代のスレッドが前のスレッドよりも多くのスレッドを持っている場合は、次のスレッドを追加します)。新しい世代ですが、それより少ない場合は、1 つ少ないスレッドを使用します (明らかに、下限は 1 スレッドです)。

最新の世代のタスクが前の世代よりも平均して時間がかかる場合は、反対方向にスレッド数を変更します (したがって、スレッド数を増やした結果時間が悪化した場合は、次回は使用するスレッドを 1 つ減らします)。

最適なスレッド数が 1 に近すぎない限り、最適にかなり近い 3 つの値の間で変動する可能性があります。処理する世代が多数ある場合は、このケースを明示的に検出し、中心値に自分自身を固定することをお勧めします。

于 2010-09-22T11:00:30.833 に答える
1

世代を多くの小さなタスクに分割し、それらをキューに入れる必要があります。コアごとに 1 つのスレッドを生成し、各スレッドに実行するタスクを取得させ、完了するまで実行して繰り返します。

生成の最後に 1 つのタスクだけが実行され、他のすべてのスレッドがアイドル状態になることがないように、コアよりも多くのタスクが必要です。これは、アルビンが提案するように #tasks = #threads = #cores を設定した場合に発生する可能性が高いものです (すべてのタスクに正確に同じ時間がかかることを保証できない場合)。

また、コアよりも多くのスレッドを必要としないこともあります。コンテキストの切り替えはそれほど高価ではありませんが、 #cores を超えるタスクを同時にアクティブにすることに伴うキャッシュのフットプリントが大きくなるため、問題が生じる可能性があります (タスクがほとんどメモリを使用しない場合を除きます)。

于 2010-09-21T20:05:38.070 に答える