412014, Steele, Lea, and Flood presented SPHTIMmx, an object -oriented pseudorandom number generator (PRNG) that is quite fast (9 64 -bit aritlimeticllogical operations per 64 bits generated) and also splittable. A couveutioual PRNG object provides a generate method that returns one pseudorandom value and updates the state of the PRNG; a splittable PRNG object also has a second operation, split, that replaces the original PRNG object with two (seemingly) independent PRNG objects, by creating and returning a new such object and updating the state of the original object. Splittable PRNG objects make it easy to organize the use of pseudorandom numbers in iriullithreaded programs structured using fork -join parallelism. This overall strategy still appears to be sound, but the specific arithmetic calculation used for generate in the SPHTMIx algorithm has some detectable weaknesses, arid the period of any one generator is limited to 264. Here we present the LXM family of PRNG algorithms. The idea is an old one: combine the outputs of two independent PRNG algorithms, then (optionally) feed the result to a mixing function. An LXM algoritlun uses a linear congruential subgenerator and an F2 -linear subgenerator; the examples studied in this paper use a,,,linear congruential generator (LCG) of period 216 23Z z-64 or 2128 with one of the multipliers recommended by L'Ecayer or by Steele and Vigna, and an F2 linear xor-based generator (XBG) of the xoshi ro filmily or xorosh i ro family as described by Blackman and Vigna. For mixing functions we study the Murmurflash3 finalizer function; variants by David Stafford; Doug Lea, and degski; and the null (identity) mixing function. Like SpirrMix, LXM provides both a generate operation and a split operation. Also like SpirriMmx, LXM requires no locking or other synchronization (other than the usual memory fence after instance initialization), arid is suitable for use with simp instruction' sets because it has no branches or loops. We analyze the period and equidistribution properties of LXM generators, and present the results of thorough testing of specific members of this family, using the Tes11101 and PractRand test suites, not only on single instances of the algorithm but also for collections of instances, used in parallel, ranging in size from 2 to 224. Single instances of LXM that include a strong mixing function appear to have no major weaknesses, and LXM is significantly more robust thm SpirriVirx against accidental correlation in a multithreaded setting. We believe that LXM, like SPHTMix, is suitable for "everyday" scientific and machine -learning applications (but not cryptographic applications), especially iten concurrent threads or distributed processes are involved.

LXM: better splittable pseudorandom number generators (and almost as fast) / G.L. Steele Jr., S. Vigna. - In: PROCEEDINGS OF ACM ON PROGRAMMING LANGUAGES. - ISSN 2475-1421. - 5:OOPSLA(2021 Oct 15), pp. 148.1-148.31. [10.1145/3485525]

LXM: better splittable pseudorandom number generators (and almost as fast)

S. Vigna
Ultimo
2021

Abstract

412014, Steele, Lea, and Flood presented SPHTIMmx, an object -oriented pseudorandom number generator (PRNG) that is quite fast (9 64 -bit aritlimeticllogical operations per 64 bits generated) and also splittable. A couveutioual PRNG object provides a generate method that returns one pseudorandom value and updates the state of the PRNG; a splittable PRNG object also has a second operation, split, that replaces the original PRNG object with two (seemingly) independent PRNG objects, by creating and returning a new such object and updating the state of the original object. Splittable PRNG objects make it easy to organize the use of pseudorandom numbers in iriullithreaded programs structured using fork -join parallelism. This overall strategy still appears to be sound, but the specific arithmetic calculation used for generate in the SPHTMIx algorithm has some detectable weaknesses, arid the period of any one generator is limited to 264. Here we present the LXM family of PRNG algorithms. The idea is an old one: combine the outputs of two independent PRNG algorithms, then (optionally) feed the result to a mixing function. An LXM algoritlun uses a linear congruential subgenerator and an F2 -linear subgenerator; the examples studied in this paper use a,,,linear congruential generator (LCG) of period 216 23Z z-64 or 2128 with one of the multipliers recommended by L'Ecayer or by Steele and Vigna, and an F2 linear xor-based generator (XBG) of the xoshi ro filmily or xorosh i ro family as described by Blackman and Vigna. For mixing functions we study the Murmurflash3 finalizer function; variants by David Stafford; Doug Lea, and degski; and the null (identity) mixing function. Like SpirrMix, LXM provides both a generate operation and a split operation. Also like SpirriMmx, LXM requires no locking or other synchronization (other than the usual memory fence after instance initialization), arid is suitable for use with simp instruction' sets because it has no branches or loops. We analyze the period and equidistribution properties of LXM generators, and present the results of thorough testing of specific members of this family, using the Tes11101 and PractRand test suites, not only on single instances of the algorithm but also for collections of instances, used in parallel, ranging in size from 2 to 224. Single instances of LXM that include a strong mixing function appear to have no major weaknesses, and LXM is significantly more robust thm SpirriVirx against accidental correlation in a multithreaded setting. We believe that LXM, like SPHTMix, is suitable for "everyday" scientific and machine -learning applications (but not cryptographic applications), especially iten concurrent threads or distributed processes are involved.
random number generator; pseudorandom; compound generator; mixing function; splittable; parallel; concurrent; DotMix; SplitMix; LXM; RNG; PRNG;
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
3485525.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 420.18 kB
Formato Adobe PDF
420.18 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/891478
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact