FPGA-optimised high-quality uniform random number generators

ABSTRACT

This paper introduces a method of constructing random numbergenerators from four of the basic primitives provided by FPGAs: Flip-Flips, Lookup-Tables, Shift Registers, and RAMs. The construction methodis designed to ensure maximum clock rates, while using the minimum of resources, and providing statistical quality at the level of the best software generators. In all platforms tested, the generators are limited in speed only by the clock distribution network or the maximum clockspeed of the underlying RAM primitives, using a platform independent VHDL description with no placement or other hints. The area utilisation is also very low, with a Virtex-5 generator requiring just one Block-RAMand 41 slices to produce 48Gb/s at 550MHz: over 14 times faster than the commonly used Mersenne-Twister RNG on an Opteron at 2.2GHz, while providing the same level of quality

REFERENCES

• 1: S. Duplichan. PPSearch: A primitive polynomial search program. http://users2.ev1.net/~sduplichan/primitivepolynomials/, 2003.
• 2: Paul Kohlbrenner , Kris Gaj, An embedded true random number generator for FPGAs, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968292]
• 3: Shiro Konuma , Shuichi Ichikawa, Design and Evaluation of Hardware Pseudo-Random Number Generator MT19937*This work partially appeared as an extended abstract in the 2005 Annual Meeting Record IEE Japan, vol.3, pp.89--90 (March 2005)., IEICE - Transactions on Information and Systems, v.E88-D n.12, p.2876-2879, December 2005 [doi>10.1093/ietisy/e88-d.12.2876]
• 4: Pierre L'Ecuyer, Tables of maximally equidistributed combined LFSR generators, Mathematics of Computation, v.68 n.225, p.261-269, Jan. 1999 [doi>10.1090/S0025-5718-99-01039-X]
• 5: P. L'Ecuyer and R. Simard. TestU01 random number test suite. www.iro.umontreal.ca/~simardr/indexe.html, 2007.
• 6: Dong-U Lee , John D. Villasenor , Wayne Luk , Philip H. W. Leong, A Hardware Gaussian Noise Generator Using the Box-Muller Method and Its Error Analysis, IEEE Transactions on Computers, v.55 n.6, p.659-671, June 2006 [doi>10.1109/TC.2006.81]
• 7: G. Marsaglia. The Diehard random number test suite. http://stat.fsu.edu/pub/diehard/, 1997.
• 8: J. Massey. Shift-register synthesis and bch decoding. IEEE Trans. on Information Theory, 15(1):122--127, 1969.
• 9: Makoto Matsumoto , Yoshiharu Kurita, Twisted GFSR generators II, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.254-266, July 1994 [doi>10.1145/189443.189445]
• 10: V. Shoup. Ntl: A library for doing number theory. http://www.shoup.net/ntl/.
• 11: V. Sriram and D. Kearney. A high throughput area time efficient pseudo uniform random number generator based on the TT800 algorithm. In Proc. Int. Conf. on Field Programmable Logic and Applications, pages 529--532, 2007.
• 12: David B. Thomas , Wayne Luk, Efficient Hardware Generation of Random Variates with Arbitrary Distributions, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.57-66, April 24-26, 2006 [doi>10.1109/FCCM.2006.39]
• 13: David B. Thomas , Wayne Luk, High Quality Uniform Random Number Generation Using LUT Optimised State-transition Matrices, Journal of VLSI Signal Processing Systems, v.47 n.1, p.77-92, April 2007 [doi>10.1007/s11265-006-0014-9]
• 14: David B. Thomas , Wayne Luk, Sampling from the Multivariate Gaussian Distribution using Reconfigurable Hardware, Proceedings of the 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.3-12, April 23-25, 2007 [doi>10.1109/FCCM.2007.57]
• 15: G.L. Zhang, P.H. Leong, D.-U. Lee, J.D. Villasenor, R.C. Cheung, and W. Luk. Ziggurat-based hardware Gaussian random number generator. In Proc. Int. Conf. on Field Programmable Logic and Applications, pages 275--280. IEEE Computer Society Press, 2005.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.0 General

General Terms:
Algorithms, Design, Performance

Keywords:
generation, number, random