Re: Looking for some C/C++ load balancing algorithm or API

Guilbert STABILO wrote:
Hi everybody,

Here is my problem:

* I have "n" listener instances of an application running in parallel.

* I have 1 sender dispatching "m" messages to these "n" listeners.

I am looking for a good simple algorithm for balancing the input
messages to the "n" listeners.

My first idea was to dispatch "m/n" messages on the "n-1" first
listeners and the remainder "m%n" on the last "n" listener. I suppose
this a too simple algorithm because I quickly met some problems.

A better version of this general idea is to send (m/n)+1 messages to
each of m%n workers and m/n messages to the remaining workers.


Example:
If "m=13" and "n=8" then I have only 1 message sent to the 7 first
instances and the last instance will process 6 messages => this is not
really balanced.

The modified version would send 2 messages to each of 5 workers, and
1 message to each of the remaining 3 workers.

However, if at all possible use a work queue. Put all the messages on
a shared queue, and have each worker dequeue a message whenever there is
a message available and it has finished any prior tasks.

In most practical situations, the tasks do not take exactly the same
amount of time, and their times are not precisely predictable. If so,
*any* static allocation scheme can result in an idle worker at the same
time as there is a task waiting for its worker to finish a prior task.

Patricia
.