🚀 go-pugleaf

maniattb@cs.rpi.edu (Bill Maniatty) writes:


>I have a large distributed stochastic model (runs on MasPar MP-1 with 2,048
>processing elements).  I'm not an expert on random number generation, but
>I need to simultaneously g enerate different ``Random'' sequences on each node.
>I'm not sure just how to define randomness in this kind of system.  Does anyone
>have a pointer to a reference on the problem.  Please note that I'm much more
>interested in making the application work than learning the intricate
>details of random number theory.
If you need random numbers for n processes, the safest way is to
use ONE random number generator for all of the processes in question
(round robin). It should have tolerable spectral behaviour in at least
say 3n dimensions. Good RNGs are contained in libg++, the c++ library
of the GNU project.

In article <h_8yzkk@rpi.edu> maniattb@cs.rpi.edu (Bill Maniatty) writes:
> I have a large distributed stochastic model (runs on MasPar MP-1 with 2,048
> processing elements).  I'm not an expert on random number generation, but
> I need to simultaneously g enerate different ``Random'' sequences on each
> node.

If the nodes must be independent, then it would probably work pretty
well to use one random number generator, say, linear congruential,
to create a sequence of 2048 seeds for a different type of generator,
say additive congruential, running in parallel on the various nodes.
I can't guarantee that this is safe, though, because the biggest
result from random number theory seems to be that nobody knows how
to prove much of anything in it.  :-)

Knuth's _Seminumerical Algorithms_ (volume 2 of _The Art of Computer
Programming_) describes both the generators I mentioned above.

								-- Dave
--
Dave Gillespie
  daveg@synaptics.com, uunet!synaptx!daveg
  or: daveg@csvax.cs.caltech.edu

daveg@synaptics.com (Dave Gillespie) writes:

>In article <h_8yzkk@rpi.edu> maniattb@cs.rpi.edu (Bill Maniatty) writes:
>> I have a large distributed stochastic model (runs on MasPar MP-1 with 2,048
>> processing elements).  I'm not an expert on random number generation, but
>> I need to simultaneously g enerate different ``Random'' sequences on each
>> node.

>If the nodes must be independent, then it would probably work pretty
>well to use one random number generator, say, linear congruential,
>to create a sequence of 2048 seeds for a different type of generator,
>say additive congruential, running in parallel on the various nodes.

This idea is really bad, because it ensures that no two generators will
give the same number at one moment (or even always the same). Besides, random
number generators are usually not designed to produce uncorrelated
numbers at ARBITRARY distances in their sequence, so you would probably
fail even simple tests terribly. As I said before, the only mathematically
safe way is to use ONE (and only one) generator of very high quality to
produce values in turn. This is because the mathematics for a good RNG
can only be ensured with regard to itself, not to other instances of it
(different seeds), and certainly not to different RNGs without further
information.

In article <dak.716387354@tabaqui>, dak@tabaqui.informatik.rwth-aachen.de (David Kastrup) writes:
|> daveg@synaptics.com (Dave Gillespie) writes:
|> 
|> >In article <h_8yzkk@rpi.edu> maniattb@cs.rpi.edu (Bill Maniatty) writes:
|> >> I have a large distributed stochastic model (runs on MasPar MP-1 with 2,048
|> >> processing elements).  I'm not an expert on random number generation, but
|> >> I need to simultaneously g enerate different ``Random'' sequences on each
|> >> node.
|> 
|> >If the nodes must be independent, then it would probably work pretty
|> >well to use one random number generator, say, linear congruential,
|> >to create a sequence of 2048 seeds for a different type of generator,
|> >say additive congruential, running in parallel on the various nodes.
|> 
|> This idea is really bad, because it ensures that no two generators will
|> give the same number at one moment (or even always the same). Besides, random
|> number generators are usually not designed to produce uncorrelated
|> numbers at ARBITRARY distances in their sequence, so you would probably
|> fail even simple tests terribly. As I said before, the only mathematically
|> safe way is to use ONE (and only one) generator of very high quality to
|> produce values in turn. This is because the mathematics for a good RNG
|> can only be ensured with regard to itself, not to other instances of it
|> (different seeds), and certainly not to different RNGs without further
|> information.

The problem with this solution as I see it is that it eliminates any parallelism
I might have in my program.  Please remember that there is a LARGE number of
random number generated (2048) for each time step.  It seems that making each
time step wait for all 2048 random numbers to be generated is terribly
inefficient (wait to generate 2047 random numbers never used by this processor).

Can you tell me just what sort of metrics are used to determine ``randomness'',
and suggest some solutions/references (can a sequential algorithm be extended
to operate in parallel? can a parallel algorithm be developed directly with any
reasonable degree of confidence?)

Thanks for your help,

Bill
-- 
|
|	maniattb@cs.rpi.edu - in real life Bill Maniatty
|

maniattb@cs.rpi.edu (Bill Maniatty) writes:

>In article <dak.716387354@tabaqui>, dak@tabaqui.informatik.rwth-aachen.de (David Kastrup) writes:
>|> daveg@synaptics.com (Dave Gillespie) writes:
>|> 
>|> >In article <h_8yzkk@rpi.edu> maniattb@cs.rpi.edu (Bill Maniatty) writes:
>|> >> I have a large distributed stochastic model (runs on MasPar MP-1 with 2,048
>|> >> processing elements).  I'm not an expert on random number generation, but
>|> >> I need to simultaneously g enerate different ``Random'' sequences on each
>|> >> node.
>|> 
>|> >If the nodes must be independent, then it would probably work pretty
>|> >well to use one random number generator, say, linear congruential,
>|> >to create a sequence of 2048 seeds for a different type of generator,
>|> >say additive congruential, running in parallel on the various nodes.
>|> 
>|> This idea is really bad, because it ensures that no two generators will
>|> give the same number at one moment (or even always the same). Besides, random
>|> number generators are usually not designed to produce uncorrelated
>|> numbers at ARBITRARY distances in their sequence, so you would probably
>|> fail even simple tests terribly. As I said before, the only mathematically
>|> safe way is to use ONE (and only one) generator of very high quality to
>|> produce values in turn. This is because the mathematics for a good RNG
>|> can only be ensured with regard to itself, not to other instances of it
>|> (different seeds), and certainly not to different RNGs without further
>|> information.

>The problem with this solution as I see it is that it eliminates any parallelism
>I might have in my program.  Please remember that there is a LARGE number of
>random number generated (2048) for each time step.  It seems that making each
>time step wait for all 2048 random numbers to be generated is terribly
>inefficient (wait to generate 2047 random numbers never used by this processor).

>Can you tell me just what sort of metrics are used to determine ``randomness'',
>and suggest some solutions/references (can a sequential algorithm be extended
>to operate in parallel? can a parallel algorithm be developed directly with any
>reasonable degree of confidence?)

The most important test for randomness is the spectral test. In essence,
ina p-dimensional spectral test, you take all possible sequences of
p consecutive numbers, and regard them as points in p-dimensional space.
The maximum distance of two p-1-dimensional planes in any direction of
the space is a measure for the goodness of the generator. All good
algorithms have been shown to pass this test reasonaby, all bad
generators seem to fail it. p usually runs about to 1-8 when testing.

For more specifications and some good generators, try Seminumerical
Algorithms (The Art of Computer Programming) by Knuth.

Letting ONE generator run on all machines is no problem, because
applying a linear congruential generator 2048 times can be replaced by
applying a different one only one time. So you start by giving
each generator the next value in sequence of the basic generator
as a seed, then proceed by letting the individual generators
advance 2048 steps at a time. But in 2048-dimensional space a
single LNG is pretty probable to be bad. Maybe the best idea would
be to choose a set of different LNG with relatively prime period,
and use them instead. This would certainly imply having to program
a spectral test to check the generators, or else bad ones will be
there (I know no precompiled tables of 2048 RNGs)