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

[Horand.Gassmann]

On Apr 16, 2:11*pm, "J.M." <[e-mail]:

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]

J.M. wrote:

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.)

[Chris Thomasson]

<Ho*************@googlemail.comwrote in message
news:83**********************************@d1g2000h sg.googlegroups.com...
On Apr 16, 2:11 pm, "J.M." <[e-mail]:

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

[...]

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.

I would suggest searching for work-stealing algorithms. They work very well
for evenly balancing dynamic workloads.

[Kai-Uwe Bux]

Juha Nieminen wrote:

J.M. wrote:

>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).

[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

[Chris Thomasson]

<Ho*************@googlemail.comwrote in message
news:83**********************************@d1g2000h sg.googlegroups.com...
On Apr 16, 2:11 pm, "J.M." <[e-mail]:

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...)

[...]

Here is an algorithm that works very well:

http://research.sun.com/scalable/pub...rkstealing.pdf

This will help you.

[Tim Little]

On 2008-04-18, James Waldby <[e-mail]:

The multiprocessor scheduling problem is known to be NP-complete (see
eg http://en.wikipedia.org/wiki/Multiprocessor_scheduling ).

The usual statement of the multiprocessor scheduling problem is that
each job may require multiple processors simultaneously. I am not
sure that the problem remains NP-complete if all jobs require only
1 CPU. I increasingly suspect that it is not.
- Tim