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

你想实现一个 work stealing algorithm . 每个工作线程都有一个双端队列,新任务被添加到最小队列的底部。工人从自己队列的顶部删除任务(顶部/底部分隔减少了争用),当工人没有更多的作业要做时,它会从最大队列的底部窃取一个作业。它很简单,而且运行良好,我相信这就是微软的并行系统.net4.0所基于的算法。

结果分配是相当好的,如果整个系统中没有更多的作业可用,工作线程将只剩下没有工作要做。

注意。如果你想把一些示例代码拆开,我的朋友为C#写了一个偷作品系统,你可以找到 here

我的倾向不是试图提前弄清楚如何分配任务,而是把它们都放到一个共同的工作队列中。任何无需其他操作的工作线程都会从队列中获取下一个任务,并在队列中检查下一个任务。

1. 对于每一个线程,我们都有est。运行时e\u n=0。
2. 对于每个任务,我找到一个线程,它有最小的e\n enque任务,e\n=e\n+p\i。

这个算法应该给你最好的结果,但与O(N M) 时间,其中N是任务数,M是线程数。解决方案的总成本为O(N logn+N

我会看一下负载平衡的算法。

http://www.ieee802.org/3/trunk_study/february98/congdon.pdf

http://publib.boulder.ibm.com/infocenter/cicstg/v6r0m0/index.jsp?topic=/com.ibm.cicstg600.doc/ccllal0292.htm

给每个线程一些“点”。让 p_i T_i . 对于每个任务,选择具有最高优先级的线程 p\u一 p\u一 . 然后您只需要跟踪按分数排序的线程,这在O(N)时间内很简单,并且可以通过平衡树在O(logn)中轻松完成。

对于连续操作,没有最小 p\u一 . 如果你想避免分数流氓走向-inf,只要定期添加一个任意数量 P 所有分数(所有分数的金额相同)。

编辑:

编辑2: 如果预先知道所有任务以及线程数,那么我认为计算最优调度类似于 knapsack problem 一般来说,它是NP完全的(所以你会在某处得到指数)。我在上面描述的一个简单的基于成本的分析将给你一个相对较好的近似值,只要所有单个任务相对于分配给每个线程的总成本有一个较小的成本。

虽然关于背包问题的建议是有帮助的,但是您说您正在尝试最小化执行的净时间。采用背包方法需要你不断增加背包的大小,直到你得到一个可行的解决方案-不是很有效。

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

看看车间作业计划。如果你只是不经常这样做,我建议使用遗传算法-如果你必须经常这样做,并以更自动化的方式,我建议做一些文献搜索确定性算法。希望这有帮助。