均等配分アルゴリズム

Question

ワークバランシングに関する簡単な質問。

ファイルを並列処理するプログラム。ファイルのサイズは、ファイルの処理に要する時間の目安となります。すべてのファイルは事前にわかっています。

私たちはファイルを処理できるN個のノードを持っています。どのノードにこれらのファイルを配布して、各ノードが最も多くの作業量に最も近いかを調べる方法。

アイデアはかなり些細なものですが、私はいくつかのアイデアを持っていますが、実際にはすでに存在する最良の解決策では古典的な問題のようです。
私はそれが何を呼んだか分かりません。

誰かがこれを知っていますか？

ありがとうございます！

編集： 申し訳ありませんが、私は多くの情報を省略しました。私はMPIの実装に取り​​組んでいます。標準マスタースレーブシステム。 1つのマスターノードは、ターゲットディレクトリを調べ、処理が必要なファイルを取り出し、MPIタスクをスレーブに割り当てて、並列処理できるようにします。スレーブノードの

金額は、私は、再帰的な格差に&統治アルゴリズムを使用してexperimenting with parallelising reduction functionsてきたとのノードに送信されたジョブの数を持つに定住している対象ファイルの32未満
未満の量10000

Answer 1

古典的なマルチプロセッサーのスケジューリングの問題について質問しています。ウィキペディアの記事はアルゴリズムの基本的な概要（http://en.wikipedia.org/wiki/Multiprocessor_scheduling）の良いスタートです。

Answer 2

です不平等lはジョブの数、nは元のワークロードとPの大きあなたがそれらを呼び出すために好きな「ノード」、労働者、プロセッサの数である

l >= n/P^2

を満たします。

ほとんどのコンピュータの状況では、&モバイルデバイスは、Pよりも大きな桁違いに大きくなります。個々のジョブの数がそれほど多くなく、すべての時間を費やして送信することを確認したいそれらを労働者に与える。

Answer 3

ここに考えがあります。降順で（ファイル名、サイズ）のペアをソートします。次に、最も大きなファイルから始めて、各ファイルをファイルの累積ウェイトが最も低いノードに割り当てます（ただし、好きなようにブレーク・タイします）。 "私のためのもの、あなたのためのもの"アプローチ。

O（MlogM）はMファイルレコードをソートし、O（M * N）は配布する（誰かがこれをもう一度チェックする）が、アルゴリズムは良い最適を与えると思いますか？ - 結果。

編集：他のポスターから提供されるリンクをチェックした後、これはPにありますが、平均サイズを可能な限り近づけるという点で最適ではないLPTアプローチです。

Answer 4

すべての作業単位の長さがあらかじめわかっている場合、これは基本的にビン充填問題（https://en.wikipedia.org/wiki/Bin_packing_problem）になります。これは、「ファーストフィット」アルゴリズムと「ベストフィット」アルゴリズムでヒューリスティックに解決できます（リンクを参照）。