启发式算法线程之间的负载均衡 [英] Heuristic algorithm for load balancing among threads

问题描述

我工作的一个多线程程序在那里我有很多表演不等长的任务的工作线程。我想负载平衡任务，以确保他们的工作大致相同。对于每一个任务T <子>我我有一个数字c <子>我提供了一个很好的近似工作所需该任务的数量。

I'm working on a multi-threaded program where I have a number of worker threads performing tasks of unequal length. I want to load-balance the tasks to ensure that they do roughly the same amount of work. For each task T_i I have a number c_i which provides a good approximation to the amount of work that is required for that task.

我在寻找一个有效的（O（N）N =任务或更高的数）的算法，这将给ç<子>的我大致一个好的负载均衡给出的值我。这并不一定是最优的，但我希望能有一定的理论界对导致分配多么糟糕。

I'm looking for an efficient (O(N) N = number of tasks or better) algorithm which will give me "roughly" a good load balance given the values of c_i. It doesn't have to be optimal, but I would like to be able to have some theoretical bounds on how bad the resulting allocations are.

任何想法？

推荐答案

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

You want to implement a work stealing algorithm. Each worker thread has a double ended queue, new tasks are added to the bottom of the smallest queue. Workers remove tasks from the top of their own queue (the top/bottom separation reduces contention), when a worker has no more jobs to do, it steals a job off the bottom of the largest queue. It's simple, and works well, this is the algorithm which the Microsoft parallel system coming with .net4.0 is based on I believe.

由此产生的分配是pretty的好，工作线程将只留下没有工作，如果有在整个系统中没有提供更多的工作要做。

The resulting allocation is pretty good, worker threads will only be left with no work to do if there are no more jobs available in the entire system.

铌。如果你想要一些例如code撕开，我的朋友写了一个工作窃取系统中的C＃，你可以在这里找到

Nb. If you want some example code to tear apart, my friend wrote a work stealing system for C#, which you can find here

这篇关于启发式算法线程之间的负载均衡的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！