仕事のバランスについての簡単な質問。
並列処理ファイルをプログラムします。ファイルのサイズが、ファイルの処理にかかるおおよその時間であるとしましょう。すべてのファイルは事前にわかっています。
ファイルを処理できるノードがN個あります。各ノードが平均作業量に最も近くなるようにこれらのファイルを配布する方法。
アイデアは非常に些細なもので、私にはいくつかのアイデアがありますが、それは実際には、すでに存在する最良の解決策を伴ういくつかの古典的な問題のようです。
私はそれが何と呼ばれるのか分かりません。
誰かがこれを知っていますか？
ありがとう！
編集：わかりました、申し訳ありませんが、私は多くの情報を省略しました。私はMPIの実装に取り組んでいます。標準のマスタースレーブシステム。1つのマスターノードがターゲットディレクトリを調べ、処理が必要なファイルを取得してから、スレーブのMPIタスクにファイルを割り当てて、スレーブがその役割を並行して実行できるようにします。
スレーブノードの数が32未満です。
ターゲットファイルの数が10000未満です。
古典的なマルチプロセッサのスケジューリングの問題について質問しています。ウィキペディアの記事は、アルゴリズムの基本的な概要を理解するための良い出発点です ( http://en.wikipedia.org/wiki/Multiprocessor_scheduling )。
ここに考えがあります。(ファイル名、サイズ) ペアを降順で並べ替えます。次に、最大のファイルから始めて、ファイルの累積重みが最も低いノードに各ファイルを割り当てます (好きなようにタイを壊してください)。「私に一つ、あなたに一つ」というアプローチ。
O(MlogM) を使用して M ファイル レコードを並べ替え、O(M*N) を配布します (誰かがこれを再確認してください)。- 結果。
編集:他のポスターによって提供されたリンクをチェックした後、これは P にあるが、平均サイズをできるだけ近づけるという点で最適ではない LPT アプローチであることがわかりました。
私は再帰的な分割と征服アルゴリズムを使用してリダクション関数を並列化して実験しており、ノードに送信されたジョブの数が不等式を満たすことに落ち着きました
l >= n / P^2
ここで、l はジョブの数、n は元のワークロードのサイズ、P は「ノード」、ワーカー、プロセッサなどの呼び方です。
ほとんどのコンピューターとモバイル デバイスの状況では、n は P よりも桁違いに大きくなります。個々のジョブの数が多すぎて、ジョブを分割してワーカーに送信することにすべての時間を費やさないようにする必要があります。
すべての作業単位の長さが事前にわかっている (推定可能) 場合、これは基本的にビン パッキング問題 ( https://en.wikipedia.org/wiki/Bin_packing_problem ) になります。これは、「最初の適合」アルゴリズムと「最適な適合」アルゴリズムを使用してヒューリスティックに解決できます (リンクを参照)。