[Omp] initialize a array with rundom numbers in a parallel loop

Thu Jan 5 13:42:06 PST 2006

I think Tim and I may be talking about the same thing, but here's
another way to look at it.  Imagine the PRNs (pseudo-random numbers)
are numbers on the side of a disc, and that the (sequential) generator
is just pulling out each element sequentially.  So if you want to have
a parallel generator, then you would have to do one of the following:

1. Have 1 process/thread generate the numbers, and pass them out to
   each "consumer" of the PRN.
2. Have n processes/threads generating the numbers, but the entire
   sequence length split evenly between the n processes/threads by
   either:
   2.1 chopping up the entire sequence length into n contiguous parts
   2.2 have each process/thread interleave n elements in its generating
       process 
3. Have each process/thread generate the numbers with each parallel
   sequence being distinctive sequences.  In other words, have each
   parallel generator pull numbers out from a distinctive disc.  

Method 1 would obviously get you a bottleneck, and incur a lot of
communication.

Method 2 would end up with a much shorter sequence per process/thread.
For method 2.1 to work properly, you need to be able to split the
entire sequence length into n contiguous parts in an efficient manner
at start-up.  Method 2.2 would need you to be able to jump ahead
efficiently (ie: without generating in elements in between, just jump
ahead).

Method 3 would get you much longer sequence, zero communication after
start-up.  But the challenge then is to be able to come up with
distinctive discs in a scalable manner.  You would still want each
parallel sequence to have full period (ie: all numbers between
the min and max values).  With each parallel sequence having full
periodicity, you then need the parallel sequences to have very low
correlation between them, in addition to low correlation within each
of the parallel sequence.  This is what we take care of in
OptimaNumerics PLFG generator.  Yes, of course, you would also get
reproducible numbers.  

The problem with using a sequential generator with different seeds for
each parallel sequence is that you would actually be pulling numbers
out from the same disc.  But you would not have any idea if there are
any overlaps.  

There are also (at least) 2 schools of thought about how to test
PRNs.  But that's another topic (for a PhD thesis?).  

Ken
-----------------------------------------------------------------------
C J Kenneth Tan, PhD
OptimaNumerics Ltd                    Telephone: +44 798 941 7838
E-mail: cjtan at OptimaNumerics.com      Telephone: +44 207 099 4428
Web: http://www.OptimaNumerics.com    Facsimile: +44 207 100 4572
-----------------------------------------------------------------------

On 2006-01-05 12:50 -0800 Mattson, Timothy G (timothy.g.mattson at intel.com)...:

> Date: Thu, 5 Jan 2006 12:50:10 -0800
> From: "Mattson, Timothy G" <timothy.g.mattson at intel.com>
> To: Omp at openmp.org
> Subject: Re: [Omp] initialize a array with rundom numbers in a parallel loop
> 
> 
> Oh dear, I have a ton of work to do and need to be good.  I tried so
> hard to stay out of this.  But I just can't any longer.
> 
> A reentrant generator only solves part of the problem.   It still
> doesn't guarantee that you will get a good sequence of random numbers.
> (even if you fix the race condition Larry mentioned).
> 
> Look, you have to think of random number generators in the context of
> how they are used.  What you are doing is generating sequences of
> pseudo-random numbers. Since you are generating them in a piece of
> software, they are not truly random.  Now each thread will happily go
> off and generate pseudorandom numbers.  If you have a single seed, each
> thread will generate the same sequence.  So instead of one long sequence
> of pseudo-random numbers, you will have multiple copies of the same
> sequence.  If you give each thread its own seed, you'll get different
> sequences for each thread, but you have no guarantee that those
> sequences won't overlap.
> 
> This is a vital issue.  You use pseudo random numbers to sample a
> domain.  If the pseudorandom numbers overlap, then you are over sampling
> subdomains and screwing up your statistics.
> 
> So it takes a bit of extra effort, but you MUST use one of those fancy
> parallel generators that address this problem.  That's what the SPRNG
> package that Larry mentioned takes care of for you.  It will also give
> you a reproducible sequence in parallel ... which is very nice if you
> want to test your software.
> 
> --Tim
> 
> 
> 
> -----Original Message-----
> From: Omp-bounces at openmp.org [mailto:Omp-bounces at openmp.org] On Behalf
> Of Meadows, Lawrence F
> Sent: Thursday, January 05, 2006 11:35 AM
> To: Priya Unnikrishnan; Omp at openmp.org
> Subject: Re: [Omp] initialize a array with rundom numbers in a parallel
> loop
> 
> Looks a lot like a race condition to me -- seed is a shared variable.
> 
> Parallel random numbers are non-trivial 
> 
> >-----Original Message-----
> >From: Omp-bounces at openmp.org [mailto:Omp-bounces at openmp.org] 
> >On Behalf Of Priya Unnikrishnan
> >Sent: Thursday, January 05, 2006 10:50 AM
> >To: Omp at openmp.org
> >Subject: [Omp] initialize a array with rundom numbers in a 
> >parallel loop
> >
> >You can use rand_r - a reentrant pseudo-random integer
> >generator.
> >
> >#include<stdio.h>
> >#include<stdlib.h>
> >
> >int main(){
> >   int a[1000],i;
> >   unsigned int seed=5;
> >
> ># pragma omp parallel for
> >   for(i=0;i<999;i++){
> >      a[i] = rand_r(&seed);
> >   }
> >
> >
> >Lado Kumsiashvili herrlado at arcor.de 
> >Wed Jan 4 17:57:31 EST 2006 
> >
> >Hallo!
> >
> >To solve my excersize i have to initialize a array
> >with random numbers
> >in a parallel loop(for). But i found out, that
> >random() function from
> ><stdlib.h> not threadsafe ist. Is there any better
> >Solution ?
> >
> >Lado
> >
> >
> >
> >-- 
> >
> >
> >
> >-----------------------------------
> >        Lado Kumsiashvili
> >lado at student.uni-kassel.de
> >-----------------------------------
> >
> >
> >
> >
> >
> >		
> >__________________________________________ 
> >Yahoo! DSL - Something to write home about. 
> >Just $16.99/mo. or less. 
> >dsl.yahoo.com 
> >
> >
> >_______________________________________________
> >Omp mailing list
> >Omp at openmp.org
> >http://openmp.org/mailman/listinfo/omp_openmp.org
> >
> 
> _______________________________________________
> Omp mailing list
> Omp at openmp.org
> http://openmp.org/mailman/listinfo/omp_openmp.org
> 
> _______________________________________________
> Omp mailing list
> Omp at openmp.org
> http://openmp.org/mailman/listinfo/omp_openmp.org
> 
> 
> 