algorithm - 线程间负载均衡的启发式算法

Question

我正在开发一个多线程程序，其中有许多工作线程执行长度不等的任务。我想对任务进行负载平衡，以确保它们完成大致相同的工作量。对于每个任务 T _i 我都有一个数字 c _i ，它提供了该任务所需工作量的良好近似值。

_{我正在寻找一种有效的（O(N) N = 任务数或更好的）算法，考虑到 c i}的值，它会给我“大致”一个良好的负载平衡。它不一定是最优的，但我希望能够对结果分配的糟糕程度有一些理论界限。

有任何想法吗？

score 7 · Accepted Answer

你想实现一个工作窃取算法。每个工作线程都有一个双端队列，新任务被添加到最小队列的底部。工作人员从他们自己的队列顶部删除任务（顶部/底部分离减少了争用），当工作人员没有更多工作要做时，它会从最大队列的底部窃取一个工作。它很简单，而且效果很好，我相信这是.net4.0附带的微软并行系统所基于的算法。

结果分配非常好，只有当整个系统中没有更多可用的作业时，工作线程才会无事可做。

NB。如果你想拆开一些示例代码，我的朋友为 C# 编写了一个工作窃取系统，你可以在这里找到

score 3 · Accepted Answer

我的倾向不是试图提前弄清楚如何分配任务，而是将它们全部放入一个共同的工作队列中。任何无事可做的工作线程都会从队列中获取下一个任务来完成工作并检查队列中的下一个任务。

score 2 · Accepted Answer

最简单的方法是按 p_i 降序对作业进行排序（但这是 O(n log n)）并执行以下操作：

这个算法应该给你最好的结果，但时间为 O(N M)，其中 N 是任务数和 M 线程数。解决方案的总成本是 O(N log N + N M)，所以对于 M << N 是 O(N log N)，对于 N 附近的 M 是 O(n^2)。

score 1 · Accepted Answer

在 O(N) 中，这似乎很容易。

给每个线程一些“点”。让p_i分给线程T_i。对于每个任务，选择最高的线程p_i，然后从中减去任务成本p_i。然后，您只需要跟踪按分数排序的线程，这在 O(N) 时间内是微不足道的，并且可以使用平衡树在 O(log N) 中轻松完成。

对于连续操作，没有最小值p_i。如果您想避免分数流向-inf，只需定期P向所有分数添加任意数量（所有分数的数量相同）。

编辑：我弄错了 N。上面，N 是线程数，与提出的问题相反。N = 任务数，T = 线程数，这会导致 O(N*log T) 成本。如果 T 为“小”，则接近 O(N)。

编辑2：如果事先知道所有任务以及线程数，那么我认为计算最佳调度类似于背包问题，总的来说，它是NP完全的（所以你会得到指数某处）。我上面描述的一个简单的基于成本的分析会给你一个相对较好的近似值，只要所有单个任务在分配给每个线程的总成本方面都有一个小的成本。

score 1 · Accepted Answer

我会看看负载平衡的算法，例如

score 1 · Accepted Answer

虽然关于背包问题的建议很有帮助，但您说您正在尝试最小化执行的净时间。采用背包方法将需要您不断增加背包的尺寸，直到找到可行的解决方案——效率不高。

如果执行的净时间受到所有并行工作线程中最长完成时间的限制，我想分配任务，因此我最小化所有线程的最大工作时间。这样做可能会导致一个或多个线程不做很多工作，所以我们并没有真正“平衡”工作。如果你想平衡工作，那么这是一个不同的目标函数。例如，您可能希望最小化线程之间的工作差异。

查看作业车间调度区域。如果您只是不经常这样做，我建议您使用遗传算法 - 如果您必须经常以更自动化的方式执行此操作，我建议您对确定性算法进行一些文献搜索。希望这可以帮助。

6 回答 6