Prev: Parallel Compression library version 1.2 ...
Next: Parallel Quicksort version 1.01...
From: Guilbert STABILO on 13 Apr 2010 07:10
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.

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.

* I do not want to reinvent the wheel so do you know any load C++
balancing algorithm or any C++ code I could compile/integrate in my
code ?

Thanks in advance for your help.



From: Torsten Robitzki on 13 Apr 2010 10:34
Guilbert STABILO schrieb:
> * I do not want to reinvent the wheel so do you know any load C++
> balancing algorithm or any C++ code I could compile/integrate in my
> code ?

One, usual approach is to put the message into a single queue and to let
the "listeners" pick that messages on there own, if they are free to
process the message.

best regards
Torsten

--
kostenlose Wirtschaftssimulation: http://www.financial-rumors.de
From: Patricia Shanahan on 13 Apr 2010 19:16
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
From: Guilbert STABILO on 14 Apr 2010 11:38
On 14 avr, 01:16, Patricia Shanahan <p...(a)acm.org> wrote:

Thanks to all for your replies but my problem was much simpler than I
first thought.
I just modified my loops so one message is successively posted to one
instance then the other and so on ...
Doing so, each listener is fed regularly and my listeners consume
approximately the same amount of CPU.
So you can forget my initial request.
 | 
Pages: 1
Prev: Parallel Compression library version 1.2 ...
Next: Parallel Quicksort version 1.01...