Parallel_Simulation

Parallel_Simulation

[Vincent LAFAGE]

I am interested in MonteCarlo simulation and I had translated a former
F77 code to Ada with success, with the goal of parallelizing it, but one
part in the algorithm still resists parallelization: the random number
generator. I need the different worker to rely on independant random
number generators.

Then I found a precious example in
 RM-A-5-2 59., 60., 61.
that compiles smoothly.

I will now attempt to check the independance of the sequence generated
by each thread. But this kind of check is always more subtle than expected.

I wonder whether there is a statement about the independance of such
generator, in particular in the gnat implementation?

Vincent

Re: Parallel_Simulation

[John B. Matthews]

In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
 Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:

> I am interested in MonteCarlo simulation and I had translated a 
> former F77 code to Ada with success, with the goal of parallelizing 
> it, but one part in the algorithm still resists parallelization: the 
> random number generator. I need the different worker to rely on 
> independant random number generators.
> 
> Then I found a precious example in
>  RM-A-5-2 59., 60., 61.
> that compiles smoothly.
> 
> I will now attempt to check the independance of the sequence 
> generated by each thread. But this kind of check is always more 
> subtle than expected.
> 
> I wonder whether there is a statement about the independance of such 
> generator, in particular in the gnat implementation?

You should check your implementation's required documentation and any 
statements on implementation advice. For example, GNAT includes a 
comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference Manual 
says, "The generator period is sufficiently long for the first condition 
here [A.5.2(47)] to hold true."

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: Parallel_Simulation

[Vincent LAFAGE]

Le 25/02/2013 13:40, John B. Matthews a écrit :
> In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
>  Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
> 
>> I am interested in MonteCarlo simulation and I had translated a 
>> former F77 code to Ada with success, with the goal of parallelizing 
>> it, but one part in the algorithm still resists parallelization: the 
>> random number generator. I need the different worker to rely on 
>> independant random number generators.
>>
>> Then I found a precious example in
>>  RM-A-5-2 59., 60., 61.
>> that compiles smoothly.
>>
>> I will now attempt to check the independance of the sequence 
>> generated by each thread. But this kind of check is always more 
>> subtle than expected.
>>
>> I wonder whether there is a statement about the independance of such 
>> generator, in particular in the gnat implementation?
> 
> You should check your implementation's required documentation and any 
> statements on implementation advice. For example, GNAT includes a 
> comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference Manual 
> says, "The generator period is sufficiently long for the first condition 
> here [A.5.2(47)] to hold true."

Thanks for the advice,
but the particular doesn't exactly fit my question.
I understand that the sequence is long enough.
But different seeds will in the end be different starting points along
the same sequence (well, at least for congruential generators, I still
have to confirm it for Mersenne Twister algorithm that is used).
And this would in turn lead to fine correlations between the sequences.

The best statement I have found until now is in gnat_rm-4.6.info:

*67*.  The minimum time interval between calls to the time-dependent
Reset procedure that are guaranteed to initiate different random number
sequences.  See A.5.2(45).
   The minimum period between reset calls to guarantee distinct series
of random numbers is one microsecond.

So I need to assert the delay between the reset of each worker in
   RM-A-5-2 60.
to be sure that there is at least one microsecond.

Would you think of another way?

Best regards
Vincent

Re: Parallel_Simulation

[Shark8]

On Monday, February 25, 2013 11:17:23 AM UTC-6, Vincent LAFAGE wrote:
> 
> Would you think of another way?

Well, you could forgo the independent RNG requirement and make a protected object that is say a stack filled with random values and is replenished as-needed.

OR you could have your different RNGs nested into the task itself (say the declaration area) -- then make the seed value take values from the protected object above.

Re: Parallel_Simulation

[John B. Matthews]

In article <kgg6b2$kma$1@ccpntc8.in2p3.fr>,
 Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:

> Le 25/02/2013 13:40, John B. Matthews a écrit :
> > In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
> >  Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
> > 
> >> I am interested in MonteCarlo simulation and I had translated a 
> >> former F77 code to Ada with success, with the goal of 
> >> parallelizing it, but one part in the algorithm still resists 
> >> parallelization: the random number generator. I need the different 
> >> worker to rely on independant random number generators.
> >>
> >> Then I found a precious example in
> >>  RM-A-5-2 59., 60., 61.
> >> that compiles smoothly.
> >>
> >> I will now attempt to check the independance of the sequence 
> >> generated by each thread. But this kind of check is always more 
> >> subtle than expected.
> >>
> >> I wonder whether there is a statement about the independance of 
> >> such generator, in particular in the gnat implementation?
> > 
> > You should check your implementation's required documentation and 
> > any statements on implementation advice. For example, GNAT includes 
> > a comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference 
> > Manual says, "The generator period is sufficiently long for the 
> > first condition here [A.5.2(47)] to hold true."
> 
> Thanks for the advice, but the particular doesn't exactly fit my 
> question. I understand that the sequence is long enough. But 
> different seeds will in the end be different starting points along 
> the same sequence (well, at least for congruential generators, I 
> still have to confirm it for Mersenne Twister algorithm that is 
> used). And this would in turn lead to fine correlations between the 
> sequences.
> 
> The best statement I have found until now is in gnat_rm-4.6.info:
> 
> *67*.  The minimum time interval between calls to the time-dependent 
> Reset procedure that are guaranteed to initiate different random 
> number sequences.  See A.5.2(45).
>   The minimum period between reset calls to guarantee distinct
>   series of random numbers is one microsecond.
> 
> So I need to assert the delay between the reset of each worker in 
> RM-A-5-2 60 to be sure that there is at least one microsecond.

IIUC, the example in A.5.2(60) uses the version of Reset that is _not_ 
time-dependent; it initializes each Worker's generator to "a state 
denoted by a single integer." As long as you're not using the 
time-dependent version, I don't see how the minimum period would come 
into play.

> Would you think of another way?

If you Reset a single instance of Discrete_Random in a time-dependent 
way and use it to generate each Worker's Initiator, as suggested in 
A.5.2(61), I don't see much chance of correlation.

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: Parallel_Simulation

[Simon Wright]

Vincent LAFAGE <lafage@ipno.in2p3.fr> writes:

> But different seeds will in the end be different starting points along
> the same sequence (well, at least for congruential generators, I still
> have to confirm it for Mersenne Twister algorithm that is used).  And
> this would in turn lead to fine correlations between the sequences.

That will be true whether you initialize with 1,2,3... or with clock
values. The only way to get truly different PRNGs must be to use
different algorithms, surely?

Re: Parallel_Simulation

[gautier_niouzes]

> I understand that the sequence is long enough.
> But different seeds will in the end be different starting points along
> the same sequence

In that case it should not be an issue if the sequence is (much) longer than the number of workers times the number of MC simulations, should it ?
______________________________________________________________________________
Gautier's Ada programming -- http://gautiersblog.blogspot.com/search/label/Ada 
NB: follow the above link for a valid e-mail address

Re: Parallel_Simulation

[Vincent LAFAGE]

Le 25/02/2013 18:17, Vincent LAFAGE a écrit :
> Le 25/02/2013 13:40, John B. Matthews a écrit :
>> In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
>>  Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
>>
>>> I am interested in MonteCarlo simulation and I had translated a 
>>> former F77 code to Ada with success, with the goal of parallelizing 
>>> it, but one part in the algorithm still resists parallelization: the 
>>> random number generator. I need the different worker to rely on 
>>> independant random number generators.
>>>
>>> Then I found a precious example in
>>>  RM-A-5-2 59., 60., 61.
>>> that compiles smoothly.
>>>
>>> I will now attempt to check the independance of the sequence 
>>> generated by each thread. But this kind of check is always more 
>>> subtle than expected.
>>>
>>> I wonder whether there is a statement about the independance of such 
>>> generator, in particular in the gnat implementation?
>>
>> You should check your implementation's required documentation and any 
>> statements on implementation advice. For example, GNAT includes a 
>> comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference Manual 
>> says, "The generator period is sufficiently long for the first condition 
>> here [A.5.2(47)] to hold true."
> 
> Thanks for the advice,
> but the particular doesn't exactly fit my question.

Ooups...
Sorry I hastened to answer while I had not read carefully enough
A.5.2(47)

 47. If the generator period is sufficiently long in relation to the
     number of distinct initiator values, then each possible value of
     Initiator passed to Reset should initiate a sequence of random
     numbers that does not, in a practical sense, overlap the sequence
     initiated by any other value. If this is not possible, then the
     mapping between initiator values and generator states should be a
     rapidly varying function of the initiator value.

I see the statement, but while Mersenne Twister algorithms provides
very, very long period (2^19937?),  I would appreciate order of
magnitudes of the subperiods.

I guess I have to test,
And read much more m(__)m

Best regards

> I understand that the sequence is long enough.
> But different seeds will in the end be different starting points along
> the same sequence (well, at least for congruential generators, I still
> have to confirm it for Mersenne Twister algorithm that is used).
> And this would in turn lead to fine correlations between the sequences.
> 
> The best statement I have found until now is in gnat_rm-4.6.info:
> 
> *67*.  The minimum time interval between calls to the time-dependent
> Reset procedure that are guaranteed to initiate different random number
> sequences.  See A.5.2(45).
>    The minimum period between reset calls to guarantee distinct series
> of random numbers is one microsecond.
> 
> So I need to assert the delay between the reset of each worker in
>    RM-A-5-2 60.
> to be sure that there is at least one microsecond.
> 
> Would you think of another way?
> 
> Best regards
> Vincent

Re: Parallel_Simulation

[Vincent LAFAGE]

Le 25/02/2013 19:30, John B. Matthews a écrit :
> In article <kgg6b2$kma$1@ccpntc8.in2p3.fr>,
>  Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
> 
>> Le 25/02/2013 13:40, John B. Matthews a écrit :
>>> In article <kgfdsp$tb0$1@ccpntc8.in2p3.fr>,
>>>  Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:
>>>
>>>> I am interested in MonteCarlo simulation and I had translated a 
>>>> former F77 code to Ada with success, with the goal of 
>>>> parallelizing it, but one part in the algorithm still resists 
>>>> parallelization: the random number generator. I need the different 
>>>> worker to rely on independant random number generators.
>>>>
>>>> Then I found a precious example in
>>>>  RM-A-5-2 59., 60., 61.
>>>> that compiles smoothly.
>>>>
>>>> I will now attempt to check the independance of the sequence 
>>>> generated by each thread. But this kind of check is always more 
>>>> subtle than expected.
>>>>
>>>> I wonder whether there is a statement about the independance of 
>>>> such generator, in particular in the gnat implementation?
>>>
>>> You should check your implementation's required documentation and 
>>> any statements on implementation advice. For example, GNAT includes 
>>> a comment in Ada.Numerics.Float_Random.ads, and the GNAT Reference 
>>> Manual says, "The generator period is sufficiently long for the 
>>> first condition here [A.5.2(47)] to hold true."
>>
>> Thanks for the advice, but the particular doesn't exactly fit my 
>> question. I understand that the sequence is long enough. But 
>> different seeds will in the end be different starting points along 
>> the same sequence (well, at least for congruential generators, I 
>> still have to confirm it for Mersenne Twister algorithm that is 
>> used). And this would in turn lead to fine correlations between the 
>> sequences.
>>
>> The best statement I have found until now is in gnat_rm-4.6.info:
>>
>> *67*.  The minimum time interval between calls to the time-dependent 
>> Reset procedure that are guaranteed to initiate different random 
>> number sequences.  See A.5.2(45).
>>   The minimum period between reset calls to guarantee distinct
>>   series of random numbers is one microsecond.
>>
>> So I need to assert the delay between the reset of each worker in 
>> RM-A-5-2 60 to be sure that there is at least one microsecond.
> 
> IIUC, the example in A.5.2(60) uses the version of Reset that is _not_ 
> time-dependent; it initializes each Worker's generator to "a state 
> denoted by a single integer." As long as you're not using the 
> time-dependent version, I don't see how the minimum period would come 
> into play.

Indeed.

>> Would you think of another way?
> 
> If you Reset a single instance of Discrete_Random in a time-dependent 
> way and use it to generate each Worker's Initiator, as suggested in 
> A.5.2(61), I don't see much chance of correlation.

Thank you for your guidance and detailled answer!

Vincent

Re: Parallel_Simulation

[Vincent LAFAGE]

Le 25/02/2013 19:18, Shark8 a �crit :
> On Monday, February 25, 2013 11:17:23 AM UTC-6, Vincent LAFAGE wrote:
>>
>> Would you think of another way?
> 
> Well, you could forgo the independent RNG requirement and make a protected object that is say a stack filled with random values and is replenished as-needed.

This was indeed my first attempt. But it turned out that the workers for
the computation were not so slow (quite optimized) compared to the
generator, and would dry the RNG stack quickly. So I try to explore the
more parallel way.

> OR you could have your different RNGs nested into the task itself (say the declaration area) -- then make the seed value take values from the protected object above.

Could be another interesting try.

Thanks!

Re: Parallel_Simulation

[John B. Matthews]

In article <kghn3m$36m$1@ccpntc8.in2p3.fr>,
 Vincent LAFAGE <lafage@ipno.in2p3.fr> wrote:

> Sorry I hastened to answer while I had not read carefully enough
> A.5.2(47)
> 
>  47. If the generator period is sufficiently long in relation to the
>      number of distinct initiator values, then each possible value of 
>      Initiator passed to Reset should initiate a sequence of random 
>      numbers that does not, in a practical sense, overlap the 
>      sequence initiated by any other value. If this is not possible, 
>      then the mapping between initiator values and generator states 
>      should be a rapidly varying function of the initiator value.
> 
> I see the statement, but while Mersenne Twister algorithms provides 
> very, very long period (2^19937?),  I would appreciate order of 
> magnitudes of the subperiods.

I'm guessing that no overlap "in a practical sense" is based on the 
very low probability:

<http://www.johndcook.com/blog/2012/04/16/random-number-sequence-overlap/>
 
> I guess I have to test,
> And read much more m(__)m

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>