Marcus (m.delete@this.bitsnbites.eu) on March 25, 2022 12:57 am wrote:
> Adrian (a.delete@this.acm.org) on March 24, 2022 2:34 pm wrote:
> > rwessel (rwessel.delete@this.yahoo.com) on March 24, 2022 1:28 pm wrote:
> > > Paul A. Clayton (paaronclayton.delete@this.gmail.com) on March 24, 2022 11:43 am wrote:
> > > > Pseudo-random number generator would provide reproducible stochastic rounding
> > >
> > > Easier said than done if the code is multi-threaded. Which is something of a given if we're assuming GPUs.
> >
> >
> > There are many good PRNG's that allow the deterministic splitting of the
> > generated sequence of numbers in separate subsequences for each thread.
> >
> > For example the multiplicative Fibonacci generators or those
> > which use a pseudo-random function in counter mode.
> >
> >
> > So the problem of having a multi-threaded program with pseudo-random but reproducible behavior
> > has been solved since about 1984 for the cases when very fast PRNGs are needed and since
> > about 1970 for the cases when the speed of the PRNGs does not matter so much.
> >
>
> What if you change your program so that you do some extra FP computations before the main
> work that you want to be reproducible? Or if you move from one compute node to another node
> with a different number of HW threads so that you partition the work differently?
>
> I can see lots of situations where it would be hard to guarantee the same PRN sequence for your
> operations. Not saying that it can't be done, but it feels like an inherently fragile solution.




If you change in any way your program, then certainly the results will not be reproducible, even if you do not use any PRNG.

If you change in any way the input data for your program, then certainly the results will not be reproducible, even if you do not use any PRNG.

If you want to insert some computations in a program that uses PRNGs without changing the results of later computations, that is trivial. For the new inserted program section you must initialize a PRNG with a different seed than any used before. When you reach the reproducible section, you initialize the PRNG or PRNGs with the same seed or seeds used before.

This is an absolutely trivial rule for using PRNGs and it has absolutely nothing to do with multi-threaded programs. You must do the same in a single-threaded program.

If you use some weird PRNG that lacks an initialization function, then obviously that PRNG cannot be used in a program with reproducible results. If it has an initialization function, then you must reinitialize it with the same seed, whenever you want to obtain again the same pseudorandom sequence.



The discussion was whether the use of a PRNG in a program prevents it to produce reproducible results, when you change neither the program nor its input data.

For a single-threaded program, satisfying the reproducibility constraint requires a means to provide a seed for the PRNG, which ensures the generation of the same sequence as long as you do not change the seed.

For a multi-threaded program that is not enough, because arbitrary interleaving of the thread executions is possible.

The initialization of the PRNGs for multithreaded programs must use not only a seed, but also a thread identifier. The PRNGs thus initialized must generate distinct and uncorrelated pseudorandom sequences.

Like I have said in my previous post, there are plenty of such PRNGs and some of them are simple enough (e.g. a double-length integer multiplication and shift per generated number) to be easily implemented in GPU shader programs, to be computed in parallel for each GPU thread.