Is there a Poisson RNG that is seed-less?

[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

[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.

[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.