Heuristic algorithm for load balancing among threads.

Posted by Il-Bhima on Stack Overflow See other posts from Stack Overflow or by Il-Bhima
Published on 2010-03-15T12:40:03Z Indexed on 2010/03/15 13:39 UTC
Read the original article Hit count: 475

I'm working on a multithreaded 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 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 = num 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?

© Stack Overflow or respective owner

Related posts about scheduling

Related posts about load-balancing