負載均衡和調度算法

Question

所以這裏是我的問題：

我有幾個不同的配置服務器。我有不同的計算（工作）;我可以預測每個工作大約需要多長時間才能被計算。另外，我有優先權。我的問題是如何保持99-100％的所有機器加載並以最好的方式安排工作。

每臺機器一次可以進行多次計算。作業被推送到機器上。中央機器知道每臺機器的當前負載。另外，我想在這裏分配一些機器學習，因爲我會知道每個作業的統計數據（開始，完成，CPU負載等）。

如何以最佳方式分配工作（計算），並牢記優先級？

任何建議，想法或算法？

僅供參考：我的平臺.NET。

Answer 1

看起來這與.NET很少有關。

但是將您的機器看作'工作線程'，在可用的CPU（或其他重要資源）上訂購可用機器的「池」，然後利用您對每項任務的知識將每項工作推送到最適合的機器。

如果您事先知道所有的工作，則可以使用「最佳擬合」算法在正確的機器上按正確的順序安排它們。你也可以看看'削減庫存'算法; http://en.wikipedia.org/wiki/Cutting_stock_problem ...

Answer 2

1. 看看Dryad linq。它已經在學術上發佈並且可能有用。
2. Win HPC server - Microsoft提供的分佈式計算企業解決方案。
3. 一些code samples它可以通過分析性能計數器來幫助構建負載平衡。
4. Microsoft有StockTrader示例應用程序（帶有源代碼），這是帶有手寫RoundRobin負載平衡的可分發SOA示例。

Answer 3

微軟最近在他們的quincy調度程序上發佈了一個paper。如果您只是針對CPU利用率進行優化，那麼一個非常簡單的解算器就可以找到全局最優解。如果您需要跨越多個軸進行優化，那麼顯然問題空間將更加複雜。

你的羣集有多大？你如何處理優化失敗案例？他們重要嗎？有IO嗎？數據是否具有磁盤親和力？是否有不止一個地方可以完成一項工作？所有的事情要考慮。

Answer 4

作爲一種替代方法，您可以使用每臺機器的峯值性能比率估計來安排工作。只有在考慮負載平衡系統的CPU運行時性能時，這纔會非常有效。這種方法忽略了有關I/O，集羣大小，網絡性能，存儲器模型類型等問題。看看http://dx.doi.org/10.1145/1513895.1513901

更準確的（接近負載均衡的作業分佈）方法的建議將是算法 - 計算機體系結構相關的一個。在這種情況下，可以將更高優先級的作業調度到滿足其需求的最佳服務器 - 但是您需要首先確定作業與服務器的最佳映射。您也可以在多處理器（而非單處理器）上應用一些OS調度算法的方法。希望你會發現這有幫助。