私は [;N;] 個のワークユニット [;w_n;] を持っています。それぞれに、事前にわかっている一定の時間 [;t_n;] がかかります。
ワークユニットの一部のサブセットを処理する必要がある場合があり、最大 [;P;] プロセスをそれぞれ別の CPU で使用できるという制約がある場合、ワークユニットを事前に効率的に分散するにはどうすればよいですか?すべてのプロセスが互いに (時間内に) できるだけ近く終了するようにプロセスを変更しますか?
質問する
69 次
1 に答える
2
A) それらがすべて統計的に同じ期間であり、それらのいずれかが実行される時間を制御できない場合、平均して、「ワークユニットを終了するプロセッサは、任意の未完成のワークユニットを完了まで実行します。」平均実行時間は Sum(1..N,t_n)/P になります。
B) ある程度予測可能な時間があれば、各プロセスに、推定時間が最も長い残りの作業単位を選択して実行するように依頼したくなるでしょう。これにより、すべての高価な作業が最初に実行され、残りの時間を埋め戻すために多くの小さなジョブが残されます。
C) 事前に選択した静的なスケジュールに固執する場合は、アルゴリズム B) をオフラインで実行し、作業単位を順番にプロセスに事前に割り当てます。これにより、実際の変動をある程度考慮できる動的スケジュールよりも合計実行時間が長くなる可能性があります。
于 2013-03-01T20:39:45.143 に答える