[Beowulf] Open source prime number application

[Robert G. Brown]

On Tue, 14 Aug 2007, Tim Simon wrote:

> I would like to know if there is any open source software that will
> run on a beowulf, which will do something like find prime numbers, or
> something simillar. I cant afford a commercial program.
>
> I am guessing that there is not "one size fits all" type thing - what
> fits your beowulf wont fit mine. Is there anything that can be easily
> made to fit? I have searched all over the net, and all i can find are
> educational or high research type applications. I just would like
> something reasonably simple, (I thought prime numbers but hey,
> anything is good).

Writing your own is good.  Hunting for primes is actually something that
will parallelize decently simply because the Sieve of Erasthones for a
proposed number N only requires that you try all the primes found up to
N/2.  Therefore a collection of nodes can contain and share all the
primes found up to N-1, and distribute the testing of N, N+2, N+4,
N+6... N+M (obviously skipping all even numbers) as long as N+M < 2N.

For a small number M of nodes, if you precompute and load all the primes
less than M -- trivially done -- then you're in business.

You will have a few longer term problems.  A single processor can sieve
all the unsigned int primes from 0-(2^32-1) out fairly quickly anyway.
To go beyond this, you'll need to use symbolic division instead of
binary computer arithmetic, I think.  You'll also run into
storage/memory problems as you start to get a significant number of
primes in your running table.

But it is a fun problem, for sure.  Go for it.

Beyond that, there are a number of programs people use to play with or
demonstrate a beowulf's speedup.  The "funnest" is any of the
rubberbandable Mandelbrot set exploration tools parallelized on top of
MPI or PVM -- makes nifty graphics.  It isn't quite as cool as it used
to be because Moore's Law has overwhelmed the computational difficulty
of the task.  When I started in this business, it might have taken
minutes to compute a rubberbanding down into the MS, depending on where
one was (and how deep one had to go on all those pixels to terminate).
Parallelize that on sixty or so nodes and it drops DRAMATICALLY to
seconds.

Now CPUs are so fast that a SINGLE CPU can rubberband down in a second
or two, and networks haven't kept pace so that computing the pixels in a
single thread might actually be faster than splitting them.  So speedup
is a bit less dramatic, but still very cool.

    rgb

> I am running Red Hat FC4.

Hmmm, might at least TRY 6 or 7.


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

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