Beowulf Questions

[Robert G. Brown]

On Tue, 14 Jan 2003, Bryce Bockman wrote:

>  From a theoretical standpoint I can't add too much to this debate, but
> when I was writing an extension to Mathew Walls GALib (a genetic
> algorithms library) I used MPI to implement a collection of "Island
> Model" genetic algorithms.  Initially, I took no steps to make sure that
> the random number pools didn't overlap other than using different seeds
> (node id along with time) on each node.  Mathew's library implements the
> famous ran2 from numerical recipes.  However, when I finally did
> implement a leapfrog method for guaranteeing disjoint sets, my solutions
> began to converge much more quickly.  So my guess is that making sure
> that I had unique pools did help in my case.  Clearly GAs are one of the
> more RNG intensive applications, but I think there is a case for using a
> leapfrog method on small clusters or if your random number generator
> permits it, a look ahead technique that allows you to partition your
> pseudo random number space on a per node basis.  Or use of the SPRNG
> library which was mentioned earlier.

Anyone preparing to use RNG's seriously should (these days) likely START
with the latest version of the Gnu Scientific Library (gsl), which is
getting quite sophisticated and complete time passes and lots of very
talented people continue to contribute.

I'm playing with a fairly recent but not even bleeding-edge current
snapshot of the library, and there are (or were recently) 56 different
RNG's encapsulated in the library's one basic call wrapper, selectable
either in code or via an external environment variable.  The best of
these is very good indeed -- it passes the DIEHARD tests, has a period
of something truly absurd like 10^6000, and is almost as fast as NR's
ran3 (which fails DIEHARD and has an uncomfortably short period).  With
a period like this, getting non-overlapping seeds from e.g. /dev/random
is likely enough for "any" application (in quotes so that I can better
withstand it when somebody tells me why this is wrong and I'm silly to
even think it for THEIR application...:-)

I'm embedding the gsl in a testing/benchmarking wrapper designed to JUST
test (against e.g.  diehard and sts/fips), benchmark, and demonstrate
all these RNG's in a shell that makes it fairly easy to test standalone
generators or hardware generators or new subroutine-level generators.
This is a natural extension of my benchmarking /dev/random for speed
last week.  I'll probably announce it on the list if/when I ever finish
it.

The GSL manual (http://sources.redhat.com/gsl/ref/gsl-ref_toc.html) is
an excellent numerical resource to benchmark.  It is a good idea to read
its discussion of RNG's, look over the generators it provides (including
many old/obsolete/known bad generators for comparison purposes).  It is
a generally BAD idea to use ANY code from Numerical Recipes.  There is a
lovely online rant against NR that scathingly picks it apart in terms of
the quality of its algorithms.  It also has a horribly restrictive
copyright and license, if one actually takes the time to read it.
Currently, one can't even use NR in one's own code on one's own machine
unless one owns the book and types in the code BY HAND.  Licenses for
machine readable access for multiple machines, networks, multiple users,
and so forth are ruinously expensive.

Before the GSL matured, NR might have been one of the few games in town
along with even more expensive IMSL, NAG and so forth.  At this point,
the GSL is powerful, extensive, portable, GPL, extensible, etc, etc.  So
far, I've found its routines to be of high quality with a few exceptions
where the code "just wasn't finished" yet.  There are a lot of very good
numerical coders contributing now, and many areas are very well covered
indeed (the table of contents alone is nearly 1000 lines long).

   rgb

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