负载均衡和调度算法

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调度算法的方法。希望你会发现这有帮助。