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 Ti I have a number ci 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 ci. 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?
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