[Beowulf] Master-Slave Problems

Robert G. Brown rgb at phy.duke.edu
Thu Feb 12 09:35:33 EST 2004

On 12 Feb 2004, Dean Michael C. Berris wrote:

> Good day everyone,
> I've just finished implementing and testing a master-slave prime number
> finder as a test problem for my thesis on heterogeneous cluster load
> balancing for parallel applications. Test results show anomalies which
> may be tied to work chunk size allocations to the slaves, but to test
> whether it will hold true for other applications and is not directly
> tied to the parallel prime number finder, I am in need of other problems
> that may be solved using a master-slave architecture.
> Sure it is easy to come up with just any problem and implement a
> solution in a master-slave model, but I'm looking for computationally
> intensive problems wherein the computation necessary for parts of the
> problem are not equal. What I mean by this is similar to the case of the
> parallel number finder, seeing whether 11 is prime requires less
> computation compared to seeing whether 9999991 is prime.
> Any insights or pointers to documentations or papers that have had
> similar problems are most welcome.

Two remarks.  One, lots of problems (e.g. descent into a Mandelbrot set)
have widely variable compute times for chunks of work divvied out in a
master/slave model with very short and uniform messages distributing the

Two, why not just simulate work?  You're studying something in computer
science, not trying to compute prime numbers or random numbers or
mandelbrot sets or julia sets.  Set up your master to distribute times
for slaves to sleep and then reply.  Select the times to distribute from
the distribution (random or otherwise) of your choice, and scale a
return "results" packet accordingly.  This yields you complete control
over the statistics of the "work" distribution and network load and lets
you explore distributions that you might not easily find in the real
world.  It also lets you CONNECT the results of your simulations with
"known" distributions to the results you obtain with real problems,
which may help you identify or even categorically classify problems in
terms of work-load complexity.  This would doubtless make your thesis
still more powerful.

This is what I've been doing in my Cluster World column -- simulating
work (or nearly so) with a trivial master-slave computation of random
numbers (the return) accompanied by an adjustable "sleep time" that
permits me to effectively sweep the granularity of the computation to
demonstrate at least simple Amdahlian scaling properties of this sort of
computation.  In fact, I can likely give you a PVM program to do this
that could easily be hacked into precisely what you'd need to implement
this with little effort (a few days, INCLUDING learning how to generate
distributions with e.g. the GSL).

Let me know.


Robert G. Brown	                       http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone: 1-919-660-2567  Fax: 919-660-2525     email:rgb at phy.duke.edu

Beowulf mailing list, Beowulf at beowulf.org
To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf

More information about the Beowulf mailing list