Load Balancing

[J.M.]

I need a decent algorithm to divide work amongst my workers (processors)
which I will use with OpenMP:

More precisely, I have a list of tasks (numbered 1,...n) requiring t_i
(i=1,..,n) time units (flops, whatever). I would like to assign each task
to one of my k workers (processors) so that all workers have about the same
amount of work. Ideal would of course be if all workers have work for T/k
time units, T being the sum over the t_i. As I want the total time I have
to wait for all work to be completed to be minimal, the deviation of the
ideal work time for each worker should be "punished" in the max. norm (or
2-norm). I don't need the best solution, but a work load that is balanced
reasonably well - so I am looking for a heuristic and ideally for a C/C++
implementation that is available in the public domain.

I would be grateful for any hint as to where I can find such an algorithm
(either already implemented or described so that I can program it myself).

(Note: I do not want to use the various OpenMP scheduling techniques,
because I will adapt my data structure in advance so that the data will be
accessed sequentially by each processor. Furthemore, t_i varies
significantly (some may even be 0), and this is unknown to the OpenMP
scheduler...)

Thanks in advance.

Jan

 

[J.M.]

If the tasks are predefined and indivisible, and if the
processors are uniform in speed and capabilities, then
why not order the tasks in descending size and assign
them first come first served to the processors as they
become available?

That is what I too thought of doing.. I was just wondering if that was the
best possibility... Note: I would like to make the list of the sort:

Processor 1: gets tasks 1, 4 ,5
Processor 2: gets tasks 2, 3, 7
Processor 3: gets tasks 0, 6, 8

in advance because I will rearange my data accordingly, so each processor
accesses it linearly and does not have to jump.. As I will be calling this
routine many times, reordering should be worth the effort... But off the
top of my head, I can't think of anything better than the greedy approach
you suggest...

Jan

 

[Horand.Gassmann]

I need a decent algorithm to divide work amongst my workers (processors)
which I will use with OpenMP:

More precisely, I have a list of tasks (numbered 1,...n) requiring t_i
(i=1,..,n) time units (flops, whatever). I would like to assign each task
to one of my k workers (processors) so that all workers have about the same
amount of work. Ideal would of course be if all workers have work for T/k
time units, T being the sum over the t_i. As I want the total time I have
to wait for all work to be completed to be minimal, the deviation of the
ideal work time for each worker should be "punished" in the max. norm (or
2-norm). I don't need the best solution, but a work load that is balanced
reasonably well - so I am looking for a heuristic and ideally for a C/C++
implementation that is available in the public domain.

I would be grateful for any hint as to where I can find such an algorithm
(either already implemented or described so that I can program it myself).

(Note: I do not want to use the various OpenMP scheduling techniques,
because I will adapt my data structure in advance so that the data will be
accessed sequentially by each processor. Furthemore, t_i varies
significantly (some may even be 0), and this is unknown to the OpenMP
scheduler...)

Search for "multi-processor scheduling". The problem is NP-hard, but
it is common enough that there should be descriptions of heuristics
available fairly easily.

 

[Juha Nieminen]

so I am looking for a heuristic and ideally for a C/C++
implementation that is available in the public domain.

Nitpicking, but there's no such thing as program source code in the
"public domain" (at least not with the copyright laws of most western
countries).

http://www.linuxjournal.com/article/6225

(Even if someone *claims* his code is PD, that doesn't make it so.
Copyright is not something you can simply make disappear at a whim.)

 

[Kai-Uwe Bux]

Nitpicking, but there's no such thing as program source code in the
"public domain" (at least not with the copyright laws of most western
countries).

[snip]

Sure there is. For instance some code produced and published by US
government agencies:

http://www.copyright.gov/title17/92chap1.html#105


Best

Kai-Uwe Bux