combinatorics - 負荷分散と第 2 種スターリング数の適用

Question

たとえば、前述を使用して実行する P 個のスレッドと N > P 個のタスクがあります。各タスクには、その特定のタスクが意味する作業量を示す正の整数値が関連付けられています。

各スレッドの「作業整数」の合計を考慮すると、それらがほぼ同じになるように、N 個のタスクを P 個のスレッドに分割したいと考えています。

このような「スケジューリング」を行うための単純だが正確な方法は、S(N,P) タスク分割を考慮する必要があります。ここで、S(N,P) は第 2 種スターリング数です (実際のコンピューティングでは実用的でないほど大きくなるはずです)。 ）。

Q: そのような「負荷分散された」タスク パーティションを計算するための適切で効率的な近似アルゴリズムはありますか?

Answer 1

プロセッサが 2 つしかない場合、タスクを 2 つの等しいタスクに分割する問題は、パーティションの問題として知られています。NP困難であることが知られています。したがって、これは、最適なソリューションを見つけることがおそらく難しい問題であることを示している可能性があります。近似値だけが必要な場合は、ある種の貪欲なアルゴリズムを使用します。残りの最大のタスクを、作業の少ないスレッドに体系的に割り当てます。これにより、時間の複雑さがO（タスク数*スレッド数）のアルゴリズムを簡単に実装できます。