私は、長さが異なるタスクを実行するワーカースレッドが多数あるマルチスレッドプログラムに取り組んでいます。タスクがほぼ同じ量の作業を行うように、タスクの負荷を分散したいと考えています。各タスク T iには 、そのタスクに必要な作業量の適切な近似値を提供する 数値 c iがあります。
私は効率的な (O(N) N = タスク数以上) アルゴリズムを探しています。これは、 c iの値が与えられた場合に「おおよそ」適切な負荷バランスを提供します。最適である必要はありませんが、結果として得られる割り当てがどれほど悪いかについて、理論的な境界を設定できるようにしたいと考えています。
何か案は？
仕事を盗むアルゴリズムを実装したい。各ワーカースレッドには両端キューがあり、最小のキューの一番下に新しいタスクが追加されます。ワーカーは自分のキューの一番上からタスクを削除し（上下の分離により競合が減少します）、ワーカーが実行するジョブがなくなると、最大のキューの一番下からジョブを盗みます。これは単純でうまく機能します。これは、.net4.0に付属しているMicrosoft並列システムが基づいているアルゴリズムであると私は信じています。
結果として得られる割り当ては非常に良好です。システム全体で使用可能なジョブがなくなった場合にのみ、ワーカースレッドに実行する作業がなくなります。
Nb。いくつかのサンプルコードを分解したい場合は、私の友人がC＃用の作業盗用システムを作成しました。これはここにあります。
私の傾向としては、タスクの割り当て方法を前もって把握しようとするのではなく、それらすべてを共通の作業キューに投入することです。他に何もすることがないワーカー スレッドは、キューから次のタスクを取得して作業を行い、次のタスクのキューをチェックします。
最も簡単な方法は、ジョブを p_i (ただし、これは O(n log n)) で降順に並べ替え、次のようにすることです。
このアルゴリズムは最良の結果をもたらすはずですが、N はタスク数、M 数のスレッドで O(N M) 時間かかります。ソリューションの総コストは O(N log N + N M) であるため、M << N の場合は O(N log N) であり、N に近い M の場合は O(n^2) です。
ナップザックの問題に関する提案は役に立ちますが、実行の正味時間を最小限に抑えようとしているとおっしゃいました。ナップザックのアプローチを取ると、実行可能な解決策が得られるまでナップザックのサイズを増やし続ける必要があり、あまり効率的ではありません。
実行の正味時間が、並列に動作しているすべてのスレッドの中で最長の完了時間によって制限されている場合、タスクを割り当てたいので、すべてのスレッドで最大作業時間を最小化します。これを行うと、多くの作業を行わない 1 つ以上のスレッドが発生する可能性があるため、実際には作業の「バランス」を取っているわけではありません。仕事のバランスを取りたい場合、それは別の目的関数です。たとえば、スレッド間の作業の差異を最小限に抑えたい場合があります。
ジョブショップスケジューリングの領域を見てください。これをあまり頻繁に行わない場合は、遺伝的アルゴリズムを使用することをお勧めします。より自動化された方法で頻繁に行う必要がある場合は、決定論的アルゴリズムについて文献を少し検索することをお勧めします。お役に立てれば。
O(N) では、これは簡単に思えます。
各スレッドにいくつかの「ポイント」を与えます。ポイントp_iをスレッドに割り当てますT_i。タスクごとに、 が最も高いスレッドを選択し、p_iからタスク コストを引きますp_i。次に、スコアで並べ替えられたスレッドを追跡するだけで済みます。これは、O(N) 時間で簡単であり、バランスの取れたツリーを使用して O(log N) で簡単に実行できます。
連続運転の場合、 に最小値はありませんp_i。スコアが -inf に向かって不正になるのを避けたい場合は、定期的にすべてのスコアに任意の量Pを追加してください (すべてのスコアで同じ量)。
編集：間違ったNを取得しました。上記のNは、質問とは反対にスレッドの数です。N = タスク数、T = スレッド数の場合、これは O(N*log T) のコストにつながります。T が「小さい」場合、これは O(N) に近くなります。
編集2：すべてのタスクとスレッド数が事前にわかっている場合、最適なスケジューリングの計算はナップザック問題に似ており、一般的にNP完全であると思います（したがって、指数関数が得られますどこか）。各スレッドに割り当てられる総コストに関して、すべての個々のタスクのコストが小さい限り、上記で何らかの方法で説明した単純なコストベースの分析により、比較的適切な概算が得られます。
ロードバランシングのアルゴリズムを見てみたい