Member Avatar for hpr

Hi guys,

I've been going around the web (whatever that means) in search of a seed-less poisson RNG. It's because I'm going to generate poisson random deviates for parallel-programming and I need it to be seed-less to ensure concurrent execution.

Cheers

  • 3 Contributors
  • 2 Replies
  • 225 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Narue

Dani AI

Generated

There’s no truly “seed‑less” deterministic generator: every PRNG needs some input (seed, key, or counter). For parallel work the important thing is to avoid shared mutable state so each worker can produce reproducible, non‑overlapping streams. As noted, you can turn uniform draws into Poisson deviates; for parallel safety prefer either (A) many independent per‑worker streams (each with its own state) or (B) a stateless counter‑based approach so each worker computes values from a unique counter/key without locking. See the Random123 counter‑based idea for the latter. (https://random123.com/)

Practical Python recommendation: use NumPy’s new Generator/BitGenerator API. Create a single SeedSequence, spawn child SeedSequences for each worker, and build a Generator from a parallel‑friendly bit generator (Philox or PCG64). Each worker gets its own Generator and can call .poisson(...) locally with no shared state and deterministic reproducibility:

from numpy.random import Generator, Philox, SeedSequence

ss = SeedSequence(12345)               # master reproducible entropy
children = ss.spawn(n_workers)         # deterministic child seeds
rngs = [Generator(Philox(s)) for s in children]

# in worker i:
lam = 4.5
samples = rngs[i].poisson(lam=lam, size=10000)

NumPy documents Philox/PCG and the spawn/jump/advance tools useful for parallel streams; using them avoids global locks and accidental stream overlap. (https://numpy.org/doc/stable/reference/random/bit_generators/philox.html) For C/C++/GPU code, use a counter‑based library such as Random123 (Threefry/Philox) which was designed for massive parallelism and passes rigorous tests. (https://github.com/DEShawResearch/random123)

A few cautions: (1) “Many streams” can expose subtle correlations if you choose weak stream splitting — follow library advice (SeedSequence.spawn or counter/key patterns). (2) For Poisson generation use a library implementation (NumPy/Boost/etc.) because they switch efficient algorithms by lambda (direct inversion for tiny lambda, transformed‑rejection for larger lambda). (https://numpy.org/doc/stable/reference/random/generated/numpy.random.Generator.poisson.html) (3) For formal guidance on independent streams and pitfalls see L’Ecuyer et al. on RNGs for parallel computing. (https://www.sciencedirect.com/science/article/pii/S0378475416300829)

Putting those pieces together gives reproducible, concurrent Poisson sampling without a single global RNG or lock.

Recommended Answers

All 2 Replies

Member Avatar for gusano79

If "Poisson RNG" means "pseudorandom number generator that generates Poisson-distributed numbers," you can generate your own from a uniform distribution; there's no need to locate a special Poisson generator if you already have a uniform PRNG that meets your requirements.

It sounds the real issue, though, is finding a generator that you can synchronize across multiple parallel processes--requests from different processes will still consume the number stream from a single generator. Suggestions:

  • Use single instance of any PRNG you want, and write a wrapper for it that buffers generated numbers and tracks requests for numbers, delivering the same sequence in the same order to each parallel process.
  • Use separate instances of the same seeded PRNG in each parallel process, but generate the seed globally so each process will generate the same numbers.
  • If you have a seedless generator that you can duplicate or which provides access to its initial state, use copies of the same seedless PRNG in each parallel process.
Member Avatar for Narue

>It's because I'm going to generate poisson random deviates for parallel-programming
>and I need it to be seed-less to ensure concurrent execution.
No, you just need the seeding mechanism to work properly for your concurrent processes. However, you didn't specify what "work properly" means for you. Do you want each process to have the same sequence or do you want all generated numbers to be distributed randomly across all processes? The answer to that question determines what you should be looking for.

If you want each process to have the same sequence, then you only have an issue with multi-threading where all threads share the same resources (which includes the global seed if you're using something like C++'s rand).

The first way to deal with creating the same sequence is to re-seed the generator for every thread (or every process) if the generator is thread-aware. If it isn't thread-aware, the easiest solution in my opinion is to write a good generator that has the seed passed in as part of the interface:

#define N 624
#define M 397
#define A 0x9908b0dfUL
#define U 0x80000000UL
#define L 0x7fffffffUL

struct twister_state {
  unsigned long x[N];
  int next;
};

twister_state twister_seed ( unsigned long s )
{
  twister_state state;

  state.x[0] = s & 0xffffffffUL;

  for ( int i = 1; i < N; i++ ) {
    state.x[i] = ( 1812433253UL 
      * ( state.x[i - 1] ^ ( state.x[i - 1] >> 30 ) ) + i );
    state.x[i] &= 0xffffffffUL;
  }

  return state;
}

unsigned long twister_rand ( twister_state& state )
{
  unsigned long y;
  unsigned long a;

  /* Refill x if exhausted */
  if ( state.next == N ) {
    state.next = 0;

    for ( int i = 0; i < N - 1; i++ ) {
      y = ( state.x[i] & U ) | state.x[i + 1] & L;
      a = ( y & 0x1UL ) ? A : 0x0UL;
      state.x[i] = state.x[( i + M ) % N] ^ ( y >> 1 ) ^ a;
    }

    y = ( state.x[N - 1] & U ) | state.x[0] & L;
    a = ( y & 0x1UL ) ? A : 0x0UL;
    state.x[N - 1] = state.x[M - 1] ^ ( y >> 1 ) ^ a;
  }

  y = state.x[state.next++];

  /* Improve distribution */
  y ^= (y >> 11);
  y ^= (y << 7) & 0x9d2c5680UL;
  y ^= (y << 15) & 0xefc60000UL;
  y ^= (y >> 18);

  return y;
}

This avoids the global resource and you can manage a separate state from each individual process/thread.

If you want the numbers to be randomly distributed across all of the processes, then with threads and a generator that isn't thread-aware, you're solid as long as you avoid deadlocks on the global seed. With real processes or a non-thread-aware generator, you have more of an issue and at that point it becomes a question of how do you communicate the seed state to every instance of the generator.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.