不帶前瞻的桶之間的加權分配

我有N工人需要處理傳入的批次數據。每個工作人員都配置爲知道它是「工作人員X的N」。不帶前瞻的桶之間的加權分配

每個傳入的批量數據都有一個隨機的唯一的ID（是隨機的，它是均勻分佈的），它有不同的大小;處理時間與大小成正比。大小可以大不相同。

當新的一批數據可用時，它立即顯示爲可供所有N個工人使用，但我只需要一個人實際處理它，而不需要它們之間的協調。現在，每個工人計算ID % N == X，這是真的，工人自動分配批次，而其他人則跳過它。這工作正常，並確保平均每個工作人員處理相同數量的批次。不幸的是，它沒有考慮到批量大小，所以一些工人可以比其他人完成更多的工作，因爲他們可能會自行分配非常大的工作。

如何更改算法，以便每個工人自動分配批次的方式也考慮到批次的大小，因此平均而言，每個工人將自行分配相同的總工作量（來自不同的批次）？

來源

2016-09-26 Giovanni Bajo

'N'大（20或更多），或者你不能對此做任何假設？ – dasblinkenlight

好問題。在我的情況下，它是像32或64，而不是100000. –

你知道工作分配的大小？它們是否均勻分佈？ – dasblinkenlight

//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; 
}

來源

2016-09-26 16:46:24

當你說「沒有他們之間的協調」時，我假設你的意思是沒有工人互相交談。可以有一位演員協調像上面這樣的所有工作人員。 –

總體思路：所有節點保持對每個節點它迄今所做的工作，這會影響他將get.It以確定的方式這樣做的所有節點都會得到相同的結果的工作，並且不需要進行通信。我們仍然做一個模數，但是工作量較少的節點的數字範圍更大。

算法：

所有工人做同樣的計算。每個節點都擁有一個元素數組，其中包含所有節點ID的元素，以及此節點到目前爲止完成的工作的父親身份，與所有節點的總工作量相比較（總工作量的5％，35％...），我們將稱之爲nodeProportion。

此數組按照（100-nodeProportion）+ 0.001 * Node_ID排序。當批到達我們做一個HASH模100，並獲得數1-100撥打此號碼K.

我們去數組排序結束，開始減去（100 nodeProportion），直到我們得到零以下。我們把工作交給那個節點。

所有節點都做相同的計算，所以他們不需要說話。

來源

2016-09-26 19:51:49

如果「每個節點都擁有一個數組...... ......」（100-nodeProportion）+ 0.001 * Node_ID ......我們將工作交給那個節點「，他們不需要說話」？你必須爲每個節點更新這個數組，所以他們會說話 –

@SeverinPappadeux所有節點都進行相同的計算，因此它們沒有說話就有相同的數據。它們都選擇相同的節點，並且都以相同的方式更新節點。 –

計算完成後是否更新節點比例？基本上，只有具有該職位的節點知道其是否免費。如果它是免費的，它必須告訴其他人 –

好，一些注意事項：

你不希望任何元數據夾，節點的通信等，所以，唯一的好辦法就是一些功能X = distributor(arguments)
你已經很簡單的那種功能X = ID % N，但大小顯然很重要
函數不能單獨取決於大小S，因爲那麼等於（大）的大小將被分配給同一個工人。我們正在尋找類似X = F(S, ID) % N
功能應該產生均勻的結果，所以最終取模運算將提供統一的負載

最簡單的功能，試圖將

X = hash(ID * S) % N

一些好的哈希函數，乘法ID*S應產生字節數組作爲散列的典型輸入，相同大小的作業將平均分配。試試吧......

來源

2016-09-28 16:22:22

不帶前瞻的桶之間的加權分配

回答

相關問題