Nonuniform random numbers are key for many technical applications, and designing efficient hardware implementations of non-uniform random number generators is a very active research field. However, most state-of-the-art architectures are either tailored to specific distributions or use up a lot of hardware resources. At ReConFig 2010, we have presented a new design that saves up to 48% of area compared to state-of-the-art inversion-based implementation, usable for arbitrary distributions and precision. In this paper, we introduce a more flexible version together with a refined segmentation scheme that allows to further reduce the approximation error significantly. We provide a free software tool allowing users to implement their own distributions easily, and we have tested our random number generator thoroughly by statistic analysis and two application tests. 1. Introduction The fast generation of random numbers is essential for many tasks. One of the major fields of application are Monte Carlo simulation, for example widely used in the areas of financial mathematics and communication technology. Although many simulations are still performed on high-performance CPU or general-purpose graphics processing unit (GPGPU) clusters, using reconfigurable hardware accelerators based on field programmable gate arrays (FPGAs) can save up to at least one order of magnitude of power consumption if the random number generator (RNG) is located on the accelerator. As an example, we have implemented the generation of normally distributed random numbers on the three mentioned architectures. The results for the achieved throughput and the consumed energy are given in Table 1. Since one single instance of our proposed hardware design (together with a uniform random number generator) consumes less than 1% of the area on the used Xilinx Virtex-5 FPGA, we have introduced a line with the extrapolated values for 100 instances to highlight the enormous potential of hardware accelerators with respect to the achievable throughput per energy. Table 1: Normal random number generator architecture comparison. In this paper, we present a refined version of the floating point-based nonuniform random number generator already shown at ReConFig 2010 [1]. The modifications allow a higher precision while having an even lower area consumption compared to the previous results. This is due to a refined synthesis. The main benefits of the proposed hardware architecture are the following:(i)The area saving is even higher than the formerly presented compared to the state-of-the-art FPGA
References
[1]
C. de Schryver, D. Schmidt, N. Wehn, et al., “A new hardware ecient inversion based random number generator for non-uniform distributions,” in Proceedings of the International Conference on Recongurable Computing and FPGAs (ReConFig '10), pp. 190–195, December 2010.
[2]
R. C. C. Cheung, D.-U. Lee, W. Luk, and J. D. Villasenor, “Hardware generation of arbitrary random number distributions from uniform distributions via the inversion method,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 15, no. 8, pp. 952–962, 2007.
[3]
P. L'Ecuyer, “Uniform random number generation,” Annals of Operations Research, vol. 53, no. 1, pp. 77–120, 1994.
[4]
N. Bochard, F. Bernard, V. Fischer, and B. Valtchanov, “True-randomness and pseudo-randomness in ring oscillator-based true random number generators,” International Journal of Reconfigurable Computing, vol. 2010, article 879281, 2010.
[5]
H. Niederreiter, “Quasi-Monte Carlo methods and pseudo-random numbers,” American Mathematical Society, vol. 84, no. 6, p. 957, 1978.
[6]
H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, Society for Industrial Mathematics, 1992.
[7]
M. Matsumoto and T. Nishimura, “Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator,” ACM Transactions on Modeling and Computer Simulation, vol. 8, no. 1, pp. 3–30, 1998.
[8]
M. Matsumoto, Mersenne Twister, http://www.math.sci.hiroshima-u.ac.jp/?m-mat/MT/emt.html, 2007.
[9]
V. Podlozhnyuk, Parallel Mersenne Twister, http://developer.download.nvidia.com/compute/cuda/2_2/sdk/website/projects/MersenneTwister/doc/MersenneTwister.pdf, 2007.
[10]
S. Chandrasekaran and A. Amira, “High performance FPGA implementation of the Mersenne Twister,” in Proceedings of the 4th IEEE International Symposium on Electronic Design, Test and Applications (DELTA '08), pp. 482–485, January 2008.
[11]
S. Banks, P. Beadling, and A. Ferencz, “FPGA implementation of Pseudo Random Number generators for Monte Carlo methods in quantitative finance,” in Proceedings of the International Conference on Reconfigurable Computing and FPGAs (ReConFig '08), pp. 271–276, December 2008.
[12]
X. Tian and K. Benkrid, “Mersenne Twister random number generation on FPGA, CPU and GPU,” in Proceedings of the NASA/ESA Conference on Adaptive Hardware and Systems (AHS '09), pp. 460–464, August 2009.
[13]
P. L'Ecuyer and R. Simard, “TestU01: a C library for empirical testing of random number generators,” ACM Transactions on Mathematical Software, vol. 33, no. 4, 22 pages, 2007.
[14]
G. Marsaglia, Diehard Battery of Tests of Randomness, http://stat.fsu.edu/pub/diehard/, 1995.
[15]
D. E. Knuth, Seminumerical Algorithms, Volume 2 of The Art of Computer Programming, Addison-Wesley, Reading, Mass, USA, 3rd edition, 1997.
[16]
B. D. McCullough, “A review of TESTU01,” Journal of Applied Econometrics, vol. 21, no. 5, pp. 677–682, 2006.
[17]
A. Rukhin, J. Soto, J. Nechvatal, et al., “A statistical test suite for random and pseudorandom number generators for cryptographic applications,” http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf, Special Publication 800-22, Revision 1a, 2010.
[18]
G. B. Robert, Dieharder: A Random Number Test Suite, http://www.phy.duke.edu/?rgb/General/dieharder.php, Version 3.31.0, 2011.
[19]
D. B. Thomas, W. Luk, P. H. W. Leong, and J. D. Villasenor, “Gaussian random number generators,” ACM Computing Surveys, vol. 39, no. 4, article 11, 2007.
[20]
G. E. P. Box and M. E. Muller, “A note on the generation of random normal deviates,” The Annals of Mathematical Statistics, vol. 29, no. 2, pp. 610–611, 1958.
[21]
A. Ghazel, E. Boutillon, J. L. Danger, et al., “Design and performance analysis of a high speed AWGN communication channel emulator,” in Proceedings of the IEEE Pacific Rim Conference, pp. 374–377, Citeseer, Victoria, BC, Canada, 2001.
[22]
D.-U. Lee, J. D. Villasenor, W. Luk, and P. H. W. Leong, “A hardware Gaussian noise generator using the box-muller method and its error analysis,” IEEE Transactions on Computers, vol. 55, no. 6, pp. 659–671, 2006.
[23]
G. Marsaglia and W. W. Tsang, “The ziggurat method for generating random variables,” Journal of Statistical Software, vol. 5, pp. 1–7, 2000.
[24]
G. Zhang, P. H. W. Leong, D.-U. Lee, J. D. Villasenor, R. C. C. Cheung, and W. Luk, “Ziggurat-based hardware gaussian random number generator,” in Proceedings of the International Conference on Field Programmable Logic and Applications (FPL '05), pp. 275–280, August 2005.
[25]
H. Edrees, B. Cheung, M. Sandora, et al., “Hardware-optimized ziggurat algorithm for high-speed gaussian random number generators,” in Proceedings of the International Conference on Engineering of Recongurable Systems & Algorithms (ERSA '09), pp. 254–260, July 2009.
[26]
N. A. Woods and T. Court, “FPGA acceleration of quasi-monte carlo in finance,” in Proceedings of the International Conference on Field Programmable Logic and Applications (FPL '08), pp. 335–340, September 2008.
[27]
C. S. Wallace, “Fast pseudorandom generators for normal and exponential variates,” ACM Transactions on Mathematical Software, vol. 22, no. 1, pp. 119–127, 1996.
[28]
C. S. Wallace, MDMC Software—Random Number Generators, http://www.datamining.monash.edu.au/software/random/index.shtml, 2003.
[29]
D. U. Lee, W. Luk, J. D. Villasenor, G. Zhang, and P. H. W. Leong, “A hardware Gaussian noise generator using the Wallace method,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 13, no. 8, pp. 911–920, 2005.
[30]
R. Korn, E. Korn, and G. Kroisandt, Monte Carlo Methods and Models in Finance and Insurance, Financial Mathematics Series, Chapman & Hull/CRC, Boca Raton, Fla, USA, 2010.
[31]
L. Devroye, Non-Uniform Random Variate Generation, Springer, New York, NY, USA, 1986.
[32]
J. A. Peter, An algorithm for computing the inverse normal cumulative distribution function, 2010.
[33]
B. Moro, “The full Monte,” Risk Magazine, vol. 8, no. 2, pp. 57–58, 1995.
[34]
D.-U. Lee, R. C. C. Cheung, W. Luk, and J. D. Villasenor, “Hierarchical segmentation for hardware function evaluation,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 17, no. 1, pp. 103–116, 2009.
[35]
D.-U. Lee, W. Luk, J. Villasenor, and P. Y. K. Cheung, “Hierarchical Segmentation Schemes for Function Evaluation,” in Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT '03), pp. 92–99, 2003.
[36]
IEEE-SA Standards Board. IEEE 754-2008 Standard for Floating-Point Arithmetic, August 2008.
[37]
Free Software Foundation Inc. GSL—GNU Scientic Library, http://www.gnu.org/software/gsl/, 2011.
[38]
S. L. Heston, “A closed-form solution for options with stochastic volatility with applications to bond and currency options,” Review of Financial Studies, vol. 6, no. 2, p. 327, 1993.
[39]
S. S. Shapiro and M. B. Wilk, “An analysis-of-variance test for normality (complete samples),” Biometrika, vol. 52, pp. 591–611, 1965.
[40]
M. A. Stephens, “EDF statistics for goodness of fit and some comparisons,” Journal of the American Statistical Association, vol. 69, no. 347, pp. 730–737, 1974.
