考慮延遲和效率的最佳分配任務的方法

假設我有一箇中心任務生產者和一些客戶消費者。生產者生成任務，消費者接受任務（對於初學者，一次一個），處理它們，當它們完成時，接受新任務（我已經有一個任務隊列）。

問題是，如果考慮從生產者到消費者的任務延遲，將任務組合在一起可能是有意義的。例如，假設我們共有10項任務和2個消費者。如果每個任務需要5毫秒才能處理，並且網絡延遲也是5毫秒，則向每個消費者發送2組5個任務，每個任務需要5ms + 5 * 5ms = 30ms，而單獨發送任務需要5 * 5ms + 5 * 5ms = 50ms，因爲每個任務都會出現延遲開銷。

它不像分組那樣簡單，因爲某些任務可能需要更長時間，因此將它們分開發送以讓其他消費者並行處理花費較短時間的其他任務是有意義的。我打算做一些關於任務類型的統計。消費者的數量也不是恆定的。

任何一個好的算法或好的閱讀，可以幫助我實現這個想法？

來源

2011-11-09 Luchian Grigore

爲什麼不開始在當前開始工作時預取下一個任務？ – CAFxX

@CAFxX可能效率低下，已經完成的消費者可能已經開始處理它，而是等待當前的消費者完成。 –

通過預取，我顯然是指從任務隊列中彈出下一個任務，以便潛在地隱藏。由於該任務已從隊列中移除，因此其他消費者無法開始處理該任務。 – CAFxX

目前，製作人生成一個任務，不立即發送它只會增加該任務的延遲。因此，我將假定任務調度器在當前任務隊列的快照上工作：它將隊列中的所有任務，立即發送到各個方向，返回隊列，再次獲取在此期間累積的所有任務，泡沫，沖洗，重複。

調度員維護每個消費者完成時間的估計。它根據增加的完成時間來命令消費者，並以最早的完成時間向消費者的批次添加任務。然後它將平均任務時間添加到該消費者完成時間估計值，從而獲得新的估計值，然後根據新的估計值對消費者進行重新排序（在O(log n)中使用堆），然後轉到下一個任務。在處理完當前快照的所有任務後，將批次發送給消費者並創建新快照。

此政策將實現平均消費負荷平均。它可以改善：

如果每個消費者能夠提供有關預計完成時間一些反饋：它的平均任務時間乘以在消費者尚未完成的任務數。這更精確，因爲消費者將使用完成任務的實際時間而不是平均值，如果處理每個任務的時間是已知的或者可以按任務進行估計，那麼調度員將使用每個任務的時間來平均執行完成的任務，而不使用平均值
，任務估計而不是平均值。

編輯：忘了提：

的完成時間估計爲start-time + average-task-time * number-of-tasks-sent-to-a-consumer + latency * number-of-batches-sent-to-a-consumer。

來源

2011-11-09 15:38:10 chill

這是一個非常好的答案，謝謝。但我確實有一些注意事項......該系統確實傳遞了隊列中的大量任務，所以當消費者啓動時，可以安全地假設隊列中有足夠的任務可以執行。其次，這與消費者的處理能力無關，因爲這些消費者或多或少都是相同的，而是關於任務類型（有不同類型的任務，有些需要更長時間，有些更慢）。我會嘗試一下你的建議的改編版本。 –

看起來，簡單方法的主要問題是，消費者將停止獲取下一個任務所花費的時間。在攤位期間沒有有用的工作完成。

由於等待時間 - 而不是帶寬 - 是主要問題，因此一種解決方案是在多個任務之間分攤攤位，例如通過將任務分組爲批次。爲了做到這一點，您需要清楚每個任務需要處理多長時間。

另一種方法是在處理當前任務的同時取出下一個任務。這可以通過兩個線程輕鬆完成：處理當前任務的線程A和獲取下一個任務的線程B。當A完成當前任務時，線程可以切換角色或將下一個任務從B傳遞到A。這是一種管道並行性。

來源

2011-11-09 13:46:53 NPE

這就是我所說的 - 分批分組任務。但問題真的是......怎麼樣？根據消費者數量，等待時間，平均任務處理時間等，每個批次應該分組多少個任務？預取也不是有效的，因爲不同的消費者可能已經準備好取出任務，但它是由尚未處理它的消費者提取的。 –

@LuchianGrigore：我認爲你需要擺脫這樣一個想法：算法應該在每一個可能的（角落）情況下做最佳的事情。更重要的是平均表現*，因爲這是總體上重要的。 – NPE

當然，但我仍然不知道如何進行分組，考慮給定類型任務的**平均**次數或**平均**延遲。我知道分組是一條路，但我仍然需要知道如何去做。 –

-1

如果您可以將延遲的定義擴展到2維，則意味着消費者可以有不同的延遲，那麼您可以嘗試一個空間填充曲線。 sfc將2d細分，並將複雜度降至1維a。所以你從f（x，y）計算一個數字。然後，您可以對此號碼進行分類並按照該順序將號碼發送給消費者。當然，你必須寫一個證監會，才能使用它我不會爲你做，但如果你有問題，我可以幫你。

來源

2011-11-09 14:09:26 Bytemain

爲什麼downvote？你能解釋一下嗎？ – Bytemain

我沒有倒下，但我看到兩個原因：你的回答寫得很差，你沒有解釋證監會如何幫助解決問題，只是可以創建一個SFC。 – Iterator

我寫道，他可以對這些數字進行排序，並按照此順序將數字發送給消費者。有什麼不清楚呢？ – Bytemain

爲了澄清我的評論你的問題，讓我們假設你在你的消費下面的循環：

while (keepConsuming) { 
    Task t = Task::get(); 
    t.process(); 
}

你可以重寫它像這樣（假設我們可以使用OpenMP的）：

Task cur=NULL, next; 
do { 
    #pragma omp sections 
    { 
     #pragma omp section 
     if (cur != NULL) cur.process(); 
     #pragma omp section 
     next = keepConsuming ? Task::get() : NULL; 
    } 
    cur = next; 
} while (cur != NULL);

這樣，while中的process（）和get（）並行執行（顯然，假設這兩個函數不共享任何狀態）。

來源

2011-11-09 16:03:50 CAFxX

Ahhh ...細粒度並行性（提供更好的負載平衡但相對較高的同步開銷）與粗粒度並行性（顯然給出相反）之間的經典決策。很抱歉，但有沒有簡單的答案...

的幾點思考：

做大量的分析，那就是找到任務組的適當數量在一起的好方法。只是很好的舊的試驗和錯誤:)
考慮在每個客戶端做一個本地任務隊列。這可以實現某種預取，例如，當任務n結束時，請求任務n + 5並開始任務n + 1。不知道您是否正在使用多線程，或者如果任務n + 1將被中斷以接受任務n + 5。
儘量壓縮任務表示。這可能意味着使用char而不是int（這對數組有影響）。也許某些部分的任務可以在到達消費者時重新計算。
考慮在每個消費者身上使用某種計時器作爲反饋，以調整下次要作爲一個組使用的任務數量。如果你花費太多時間，那麼下一次抓取更少的任務。注意花哨的啓發式可能會有一些不平凡的開銷。

來源

2011-11-10 04:15:17 Jason

考慮延遲和效率的最佳分配任務的方法

回答

相關問題