Heuristic algorithm for load balancing among threads

Question

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.

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.

Any ideas?

Answer 1

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.

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.

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

Answer 2

My inclination is not to try to figure out ahead of time how to assign the tasks, but to throw them all into a common work queue. Any worker thread with nothing else to do grabs the next task from the queue does the work and checks the queue for the next task.