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: 481
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