Counter-based random number generator (CBRNG)

Counter-based random number generation is a technique for creating a pseudorandom number generator using only an integer counter as the internal state of the generator.

Most pseudorandom generators rely on some type of internal state and a function that updates the state. Each value of the internal state is then mapped to one pseudorandom sample. Normally the state transition function is complicated and the function mapping state to a sample is simple. In the case of counter-based generators the internal state is just an integer counter. The state transition function is an increment by one. The complexity comes in the map from the state to the random sample.

Because the state is just a counter it is trivial to split random number generation between parallel processors without overlap. Skip-a-head and rewind in the stream of generated random numbers also become trivial O(1) operations. It is easy to organize different numbers of parallel processors to generate the same sequence of pseudorandom numbers.

The technique was proposed by a group at D. E. Shaw Research[1] In addition to the general technique, specific generators named ARS, Threefry, and Philox were proposed as examples. Code implementing the generators is available in the library "Random123". . The ARS-5 generator is included in recent versions of the Intel Math Kernel Library and has excellent performance.[2] Variations of Philox are the fastest generators on GPUs that pass both TestU01 and the Ising test.[3]

References

  1. ↑ Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Parallel random numbers: as easy as 1, 2, 3". Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16. doi:10.1145/2063384.2063405.
  2. ↑ Fedorov, Gennady; Gladkov, Eugeny (2015). "New counter-based Random Number Generators in Intel® Math Kernel Library". Intel. Retrieved August 22, 2016.
  3. ↑ Manssen, M.; Weigel, M; Hartmann, A.K. (August 2012). "Random number generators for massively parallel simulations on GPU". Eur. Phys. J. Spec. Top. Springer. 210 (1): 53–71. doi:10.1140/epjst/e2012-01637-8.
This article is issued from Wikipedia - version of the 8/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.