ルックアヘッドのないバケット間の重み付け分布

Question

私はNのデータを受信するバッチを処理する必要があります。各ワーカーは、「ワーカーX：N」であることがわかるように構成されています。

データが入ってくる各バッチには、ランダムにユニークなID（ランダムであり、一様に分布しています）というサイズがあります。処理時間はサイズに比例します。サイズは大きく変わることがあります。

データの新しいバッチが利用可能になると、N個のすべてのワーカーが利用できるようにすぐに表示されますが、を調整しないでを実際に処理するだけです。今、各作業者はID % N == Xを計算します。それは真です。作業者はバッチを自己割り当てし、他の人はそれをスキップします。これは正しく動作し、平均して各ワーカーが同じ数のバッチを処理することを確認します。残念ながら、バッチサイズは考慮されていないため、非常に大きなジョブを自己割り当てする可能性があるため、一部のワーカーは他のワーカーよりもずっと後で処理を完了できます。

各ワーカーがバッチのサイズも考慮してバッチを自己割り当てするようにアルゴリズムを変更すると、平均して各ワーカーが同じ合計サイズの仕事を割り当てることができます異なるバッチから）？

Answer 1

//Using a queue to store the workers 
//This way we can dequeue and reenqueue workers when they accept jobs 
var _queue = new Queue<Worker>[numOfWorkers]; 

void Setup() { 
    for (int i = 0;i<numOfWorkers -1;i++) { 
     _queue.Enqueue(new Worker()); 
    } 
} 

//Assigns the job to the next worker in line and puts it at the end of queue 
void AcceptJob(Job j) { 
    var w = FindNextAvailableWorker(); 
    w.AssignNewJob(j); 
    _queue.Enqueue(_queue.RemoveAt(_queue.PositionOf(w))); 
} 

//Finds the first free worker or returns the front of queue 
Worker FindNextAvailableWorker() { 
    var w = _queue.front(); 

    while (int i=0;i<_queue.length-1<i++) { 
     if (_queue[i].isWorking==false){ 
      w = _queue[i]; 
      exit loop; 
     } 
    } 

    return w; 
} 

Answer 2

一般的な考え方： すべてのノードは、各ノードのために、それは、これまで行われており、これは彼がget.Itがそのように、すべてのノードが同じ結果を得ることができます決定論的な方法で行われます仕事に影響を与える作品を保ちます、通信する必要はありません。私たちはまだモジュラスを行いますが、仕事の少ないノードはより大きな範囲の数値を持っています。

アルゴリズム：

すべてのワーカーは同じ計算を行います。 各ノードは、すべてのノードIDを保持する要素と、このノードがこれまでに行った作業の親子をすべてのノードの合計作業と比較した配列を保持します（総作業の5％、35％...） nodeProportion。

この配列は（100-nodeProportion）+ 0.001 * Node_IDでソートされます。 バッチが到着したら、HASHモジュラス100を実行し、この番号Kを1〜100の番号で呼び出します。

ソートされた配列を調べて、ゼロ以下になるまで（100ノードの割合）を減算します。私たちはそのノードに仕事を与えます。

すべてのノードで同じ計算が行われるため、話す必要はありません。

Answer 3

[OK]を、いくつかの注意事項：

• あなたは任意のメタデータホルダーを望んでいないが、等の通信ノードだから、唯一の良い方法は、いくつかの機能X = distributor(arguments)
• だろうあなたは非常に単純な種類のすでに機能を持っていますX = ID % Nしかし、大きさ、明らかに、事項
• 機能は同じワーカーに等しい（大きい）サイズが割り当てられるので、サイズSだけに依存することはできません。私たちは、
X = F(S, ID) % Nのような機能が均一な結果を生成する必要があり、最終的な剰余opが均一な負荷に

を提供することになるしようとする最も簡単な関数は

X = hash(ID * S) % N 

いくつかの良いハッシュ関数、乗算だろう何かを探していますID*Sは、ハッシュの一般的な入力としてバイトの配列を生成します。同じサイズのジョブは、均等に分散されます。試してみてください...