On the Fast Generation of Long-period Pseudorandom Number Sequences

摘要

Monte Carlo simulations and other scientific applications that depend on random numbers are increasingly implemented in parallel configurations in programmable hardware. High-quality pseudo-random number generators (PRNGs), such as the Mersenne Twister, are based on binary linear recurrence equations. They have extremely long periods (more than 2{sup}1024 numbers generated before the entire sequence repeats) and well-proven statistical properties. Many software implementations of such 'long-period' PRNGs exist, but hardware implementations are rare. We develop optimized, resource-efficient parallel architectures for long-period PRNGs that generate multiple independent streams by exploiting the underlying algorithm as well as hardware-specific architectural features. We demonstrate the utility of the framework through parallelized implementations of three types of PRNGs on a field-programmable gate array (FPGA). The area/throughput performance is impressive: for example, compared clock-for-clock with a previous FPGA implementation, a "two-parallelized" 32-bit Mersenne Twister uses 41% fewer resources. It can also scale to 350MHz for a throughput of 22.4Gbps, which is 5.5x faster than the previous implementation and 7.1x faster than a dedicated software implementation. The quality of generated random numbers is verified with standard statistical test batteries. To complete testing, we present a real-world application study by coupling our parallel hardware RNGs to the Ziggurat algorithm for generating normal random variables. The availability of fast long-period random number generators accelerates hardware-based scientific simulations and allows them to scale to greater complexities.