Seeding parallel xoroshiro128+ generators

As part of the statistical quality analysis I did of the of the xoroshiro128aox PRNG, I looked at interleaved parallel generators (where a single generator is created by round-robin interleaving the output $n$ identical generators with different seeds) as a way to test its suitability for parallel processing. Against my intuition, I found that simple seeding schemes produce poor interleaved generators, and even when the subsequences are disjoint. These findings equally apply to xoroshiro128+ as we will see.

The xoroshiro128+ creators recommend using a jump function to seed parallel generators to deterministically move to disjoint parts of the sequence. However, computing jumps is expensive to do in hardware because it involves 128-bit arithmetic and so it is preferable to compute seed values based on a simpler function of a machine’s state, such as an integer identifier for a process/thread. Since the probability of any two randomly-chosen sequences overlap is very small even with a large number of sequences, it seems reasonable to assume that a simple seed generator will perform okay in practice. Note also that the creators separately recommend “that initialization must be performed with a generator radically different in nature from the one initialized to avoid correlation on similar seeds”, based on research from 2007.

To investigate the use of simple seeding schemes, I ran tests against interleaved generators with three representative options (the source code is available on GitHub):

With equidistant intervals from 1 in the natural number sequence [Scheme A], defined in Python notation as:

for i in range(NUM_SEEDS):
    seed[i] = int(1 + i * ((2**128) // NUM_SEEDS))

With equidistant intervals starting from a random offset [Scheme B]:

for i in range(NUM_SEEDS):
    seed[i] = int(rand(0, (2**128) // NUM_SEEDS) + i * ((2**128) // NUM_SEEDS))

By adding a fixed offset to a initial state of balanced 0s and 1s [Scheme C]:

for i in range(NUM_SEEDS):
    seed[i] = 0x55555555555555555555555555555555 + i

And, as baselines:

Using the xoroshiro128 jump function, jumping $2^{64}$ steps [Scheme D].
Using a minimum-size jump for the number of generators to pass PractRand [Scheme E] (for example, the distance for 1000 generators is 4398046511 = (32 * 1024**4) / (8 * 1000)).
Using a non-linear PRNG to choose seeds (PCG64) [Scheme F].

To test these seeding schemes, I ran each generator against the standard PractRand test battery. PractRand is a good choice for these tests since it reports results at intermediate points and consumes much more output than Big Crush or Gjrand: 32 TB by default. A pass is achieved if no overtly suspicious $p$-values are flagged.

The results are summarised in the following table:

Seeding scheme	Number of generators	Output seen	Failing tests
Scheme A	10	256 MB	`DC6`, `FPF`
Scheme A	100	512 MB	`DC6`, `FPF`
Scheme A	1000	16 GB	`BCFN`
Scheme B	10	256 MB	`FPF`
Scheme B	100	2 GB	`DC6`
Scheme B	1000	32 GB	`BCFN`
Scheme C	10	256 MB	`DC6`, `Gap`, `FPF`, `mod3`
Scheme C	100	256 MB	`BCFN`, `DC6`, `Gap`, `FPF`, `mod3n`
Scheme C	1000	256 MB	`BCFN`, `DC6`, `Gap`, `Brank`, `FPF`, `mod3n`
Scheme D	10,100,1000	32 TB	Pass
Scheme E	10,100,1000	32 TB	Pass
Scheme F	10,100,1000	32 TB	Pass

Note that DC6 and BCFN are both tests for linearity. For the failing generators (schemes A-C), I checked there are no duplicate values between the different generators to establish that no two sequences overlap (using the analyse mode). This means that the above failures are due to correlations between disjoint sequences.

For reference, below is sample output for running the Scheme A generator with 10 parallel streams against PractRand. There are comprehensive failures within the first 256 MB of output.

$ ./build/xoroshiro128plus_il_equia_10 stdout std64 0 0 | ./install/PractRand-pre0.95/RNG_test stdin64 -a
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 256 megabytes (2^28 bytes), time= 2.3 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+0,13-2,T)                  R=  -0.0  p = 0.494     normal
  BCFN(2+1,13-2,T)                  R=  +4.1  p = 0.050     normal
  BCFN(2+2,13-3,T)                  R=  +0.0  p = 0.484     normal
  BCFN(2+3,13-3,T)                  R=  +1.3  p = 0.292     normal
...
  [Low16/64]BCFN(2+12,13-9,T)       R=  -2.1  p = 0.849     normal
  [Low16/64]DC6-9x1Bytes-1          R=  +1.6  p = 0.332     normal
  [Low16/64]Gap-16:A                R=  +0.5  p = 0.523     normal
  [Low16/64]Gap-16:B                R=  +4.3  p =  1.3e-3   normalish
  [Low16/64]FPF-14+6/16:(0,14-0)    R=  +0.2  p = 0.434     normal
  [Low16/64]FPF-14+6/16:(1,14-0)    R=  +2.2  p = 0.061     normal
...
  [Low4/64]BCFN(2+9,13-9,T)         R=  +0.6  p = 0.310     normal
  [Low4/64]BCFN(2+10,13-9,T)        R=  +0.2  p = 0.372     normal
  [Low4/64]DC6-9x1Bytes-1           R= +88.5  p =  5.9e-51    FAIL !!!!
  [Low4/64]Gap-16:A                 R=  +4.4  p =  4.6e-3   normalish
  [Low4/64]Gap-16:B                 R=  -0.6  p = 0.656     normal
  [Low4/64]FPF-14+6/16:(0,14-1)     R=  -1.0  p = 0.759     normal
  [Low4/64]FPF-14+6/16:(1,14-2)     R=  -3.7  p =1-4.2e-3   normal
  [Low4/64]FPF-14+6/16:(2,14-2)     R=  -0.9  p = 0.738     normal
  [Low4/64]FPF-14+6/16:(3,14-3)     R=  +1.3  p = 0.189     normal
  [Low4/64]FPF-14+6/16:(4,14-4)     R=  +1.6  p = 0.134     normal
  [Low4/64]FPF-14+6/16:(5,14-5)     R=  +1.2  p = 0.206     normal
  [Low4/64]FPF-14+6/16:(6,14-5)     R=  +1.4  p = 0.166     normal
  [Low4/64]FPF-14+6/16:(7,14-6)     R=  -1.6  p = 0.877     normal
  [Low4/64]FPF-14+6/16:(8,14-7)     R=  -0.7  p = 0.681     normal
  [Low4/64]FPF-14+6/16:(9,14-8)     R=  +1.2  p = 0.187     normal
  [Low4/64]FPF-14+6/16:(10,14-8)    R= +19.4  p =  5.5e-14    FAIL
  [Low4/64]FPF-14+6/16:(11,14-9)    R= +12.4  p =  4.0e-8   suspicious
  [Low4/64]FPF-14+6/16:(12,14-10)   R= +12.5  p =  3.0e-7   mildly suspicious
  [Low4/64]FPF-14+6/16:(13,14-11)   R=  +5.1  p =  4.8e-3   normal
  [Low4/64]FPF-14+6/16:(14,14-11)   R=  +8.8  p =  1.1e-4   normal
  [Low4/64]FPF-14+6/16:all          R=  +0.3  p = 0.435     normal
  [Low4/64]FPF-14+6/16:cross        R=  +2.1  p = 0.032     normal
  [Low4/64]BRank(12):128(4)         R=  -0.8  p~= 0.670     normal
  [Low4/64]BRank(12):256(2)         R=  +1.6  p~= 0.168     normal
  [Low4/64]BRank(12):384(1)         R=  +1.8  p~= 0.146     normal
  [Low4/64]BRank(12):512(2)         R=  -0.2  p~= 0.554     normal
  [Low4/64]BRank(12):768(1)         R=  -0.7  p~= 0.689     normal
  [Low4/64]mod3n(5):(0,9-6)         R= +14.0  p =  1.3e-5   mildly suspicious
  [Low4/64]mod3n(5):(1,9-6)         R=  -0.0  p = 0.451     normal
  [Low4/64]mod3n(5):(2,9-6)         R=  -0.2  p = 0.492     normal
  [Low4/64]mod3n(5):(3,9-6)         R=  -1.5  p = 0.781     normal
  [Low4/64]mod3n(5):(4,9-6)         R=  +0.0  p = 0.433     normal
  [Low4/64]mod3n(5):(5,9-6)         R=  +0.4  p = 0.353     normal
  [Low4/64]mod3n(5):(6,9-6)         R=  -1.3  p = 0.742     normal
  [Low4/64]mod3n(5):(7,9-6)         R=  +1.9  p = 0.152     normal
  [Low4/64]mod3n(5):(8,9-6)         R=  -1.3  p = 0.731     normal
  [Low4/64]mod3n(5):(9,9-6)         R=  -0.4  p = 0.540     normal
  [Low4/64]mod3n(5):(10,9-6)        R=  -0.6  p = 0.585     normal
  [Low4/64]mod3n(5):(11,9-6)        R=  +0.6  p = 0.322     normal
  [Low1/64]BCFN(2+0,13-6,T)         R=  +7.3  p =  6.5e-3   normalish
  [Low1/64]BCFN(2+1,13-6,T)         R=  -3.2  p = 0.926     normal
  [Low1/64]BCFN(2+2,13-6,T)         R=  -1.5  p = 0.716     normal
  [Low1/64]BCFN(2+3,13-6,T)         R=  +1.6  p = 0.238     normal
  [Low1/64]BCFN(2+4,13-7,T)         R=  +1.7  p = 0.212     normal
  [Low1/64]BCFN(2+5,13-8,T)         R=  +0.8  p = 0.304     normal
  [Low1/64]BCFN(2+6,13-8,T)         R=  +0.2  p = 0.403     normal
  [Low1/64]BCFN(2+7,13-9,T)         R=  +1.0  p = 0.257     normal
  [Low1/64]BCFN(2+8,13-9,T)         R=  -1.8  p = 0.790     normal
  [Low1/64]DC6-9x1Bytes-1           R= +1379  p =  3.6e-777   FAIL !!!!!!!
  [Low1/64]Gap-16:A                 R= +4863  p =  5e-3914    FAIL !!!!!!!!
  [Low1/64]Gap-16:B                 R=+11222  p =  6e-8467    FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:(0,14-2)     R=+10120  p =  5e-8851    FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:(1,14-3)     R= +7164  p =  2e-6279    FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:(2,14-4)     R= +5071  p =  9e-4144    FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:(3,14-5)     R= +3567  p =  1e-2956    FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:(4,14-5)     R= +2180  p =  7e-1807    FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:(5,14-6)     R= +1535  p =  1e-1174    FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:(6,14-7)     R=+350.5  p =  9.0e-279   FAIL !!!!!!
  [Low1/64]FPF-14+6/16:(7,14-8)     R=+255.2  p =  1.1e-183   FAIL !!!!!!
  [Low1/64]FPF-14+6/16:(8,14-8)     R=+235.5  p =  1.7e-169   FAIL !!!!!
  [Low1/64]FPF-14+6/16:(9,14-9)     R=+152.7  p =  2.0e-96    FAIL !!!!!
  [Low1/64]FPF-14+6/16:(10,14-10)   R= +87.1  p =  6.7e-47    FAIL !!!
  [Low1/64]FPF-14+6/16:(11,14-11)   R= +58.4  p =  2.6e-26    FAIL !!
  [Low1/64]FPF-14+6/16:(12,14-11)   R= +58.0  p =  3.9e-26    FAIL !!
  [Low1/64]FPF-14+6/16:all          R=+14029  p = 0           FAIL !!!!!!!!
  [Low1/64]FPF-14+6/16:cross        R= +3119  p =  3e-2681    FAIL !!!!!!!!
  [Low1/64]BRank(12):128(2)         R=  -0.2  p~= 0.554     normal
  [Low1/64]BRank(12):256(2)         R=  -1.0  p~= 0.744     normal
  [Low1/64]BRank(12):384(1)         R=  -0.7  p~= 0.689     normal
  [Low1/64]BRank(12):512(1)         R=  +0.4  p~= 0.366     normal
  [Low1/64]mod3n(5):(0,9-6)         R=+322.9  p =  4.1e-111   FAIL !!!!!
  [Low1/64]mod3n(5):(1,9-6)         R=  -0.5  p = 0.563     normal
  [Low1/64]mod3n(5):(2,9-6)         R=  +2.1  p = 0.129     normal
  [Low1/64]mod3n(5):(3,9-6)         R=  +5.0  p = 0.016     normal
  [Low1/64]mod3n(5):(4,9-6)         R=  +2.5  p = 0.099     normal
  [Low1/64]mod3n(5):(5,9-6)         R=  -0.8  p = 0.614     normal
  [Low1/64]mod3n(5):(6,9-6)         R=  -1.4  p = 0.757     normal
  [Low1/64]mod3n(5):(7,9-6)         R=  +1.7  p = 0.167     normal
  [Low1/64]mod3n(5):(8,9-6)         R=  +2.3  p = 0.111     normal
  [Low1/64]mod3n(5):(9,9-6)         R=  +2.2  p = 0.125     normal

Conclusion

When choosing seeds for PRNGs operating in parallel, it might seem sufficient to ensure that the sequences they range over are disjoint, provably or with high probability. However, correlations between disjoint subsequences do exist in PRNGs based on the xoroshiro128 linear engine. It is known that these correlations can manifest when sequences are chosen by a linear generator. Based on the findings in this note, these correlations also occur when seeds are created using non-linear operations such as addition. The safest course of action to take is to follow the guidance of the xoroshiro128 authors and either use the jump function to traverse the state space or use a high-quality non-linear PRNG to generate random seeds.

References

My PRNG testing source code.
xoshiro / xoroshiro generators and the PRNG shootout.
PractRand.
Makoto Matsumoto, Isaku Wada, Ai Kuramoto, and Hyo Ashihara. 2007. Common defects in initialization of pseudorandom number generators. ACM Transactions on Modeling and Computer Simulation.