A comparison of CPUs, GPUs, FPGAs, and massively parallel processor arrays for random number generation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A comparison of CPUs, GPUs, FPGAs, and massively parallel processor arrays for random number generation

Full text

Pdf (589 KB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays table of contents

Monterey, California, USA

SESSION: High performance computing applications table of contents

Pages 63-72

Year of Publication: 2009

ISBN:978-1-60558-410-2

Authors

David Barrie Thomas	Imperial College London, London, United Kingdom
Lee Howes	Imperial College London, London, United Kingdom
Wayne Luk	Imperial College London, London, United Kingdom

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 79, Downloads (12 Months): 345, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1508128.1508139 What is a DOI?

ABSTRACT

The future of high-performance computing is likely to rely on the ability to efficiently exploit huge amounts of parallelism. One way of taking advantage of this parallelism is to formulate problems as "embarrassingly parallel" Monte-Carlo simulations, which allow applications to achieve a linear speedup over multiple computational nodes, without requiring a super-linear increase in inter-node communication. However, such applications are reliant on a cheap supply of high quality random numbers, particularly for the three main maximum entropy distributions: uniform, used as a general source of randomness; Gaussian, for discrete-time simulations; and exponential, for discrete-event simulations. In this paper we look at four different types of platform: conventional multi-core CPUs (Intel Core2); GPUs (NVidia GTX 200); FPGAs (Xilinx Virtex-5); and Massively Parallel Processor Arrays (Ambric AM2000). For each platform we determine the most appropriate algorithm for generating each type of number, then calculate the peak generation rate and estimated power efficiency for each device.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. H. Ahrens , U. Dieter, Computer methods for sampling from the exponential and normal distributions, Communications of the ACM, v.15 n.10, p.873-882, Oct. 1972 [doi>10.1145/355604.361593]
	2	Ambric, Inc. Am2000 Family Architecture Reference, May 2008.
	3	G. E. P. Box and M. E. Muller. A note on the generation of random normal deviates. Annals of Mathematical Statistics, 29(2):610--611, 1958.
	4	Richard P. Brent, Algorithm 488: A Gaussian pseudo-random number generator, Communications of the ACM, v.17 n.12, p.704-706, Dec 1974 [doi>10.1145/361604.361629]
	5	R. Cheung, D. Lee, W. Luk, and J. Villasenor. Hardware generation of arbitrary random number distributions from uniform distributions via the inverson method. IEEE Transactions on VLSI, 15(8):952--962, 2007.
	6	L. Devroye. Non-Uniform Random Variate Generation. Springer-Verlag New York, 1996.
	7	M. Y. et. al. FPGA implementation of a data-driven stochastic biochemical simulator with the next reaction method. In Proc. Int. Conf. on Field Programmable Logic and Applications, pages 254--259, 2007.
	8	G. E. Forsythe. Von neumann's comparison method for random sampling from the normal and other distributions. Mathematics of Computation, 26(120):817--826, 1972.
	9	L. Howes and D. Thomas. GPU Gems 3: Efficient Random Number Generation and Application Using CUDA, chapter 37. Addison-Wesley, 2007.
	10	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]
	11	P. L'Ecuyer. Elsevier Handbooks in Operations Research and Management Science: Simulation, chapter 3: Random Number Generation, pages 55--81. Elsevier Science, 2006.
	12	P. L'Ecuyer and R. Simard. TestU01 random number test suite. www.iro.umontreal.ca/~simardr/indexe.html, 2007.
	13	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]
	14	Dong-U Lee , Wayne Luk , John D. Villasenor , Peter Y. K. Cheung, A Gaussian Noise Generator for Hardware-Based Simulations, IEEE Transactions on Computers, v.53 n.12, p.1523-1534, December 2004 [doi>10.1109/TC.2004.106]
	15	D.-U. Lee, W. Luk, J. D. Villasenor, G. Zhang, and P. H. Leong. A hardware Gaussian noise generator using the wallace method. IEEE Transactions on VLSI Systems, 13(8):911--920, 2005.
	16	G. Marsaglia. Xorshift RNGs. Journal of Statistical Software, 8(14):1--6, 2003.
	17	G. Marsaglia and W. W. Tsang. The ziggurat method for generating random variables. Journal of Statistical Software, 5(8):1--7, 2000.
	18	François Panneton , Pierre L'Ecuyer , Makoto Matsumoto, Improved long-period generators based on linear recurrences modulo 2, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.1-16, March 2006 [doi>10.1145/1132973.1132974]
	19	Rainer A Rueppel, Correlation immunity and the summation generator, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.260-272, June 1986, Santa Barbara, California, United States
	20	M. Saito and M. Matsumoto. SIMD-oriented fast mersenne twister: a 128-bit pseudorandom number generator. In Monte-Carlo and Quasi-Monte Carlo Methods, pages 607--622, 2006.
	21	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]
	22	D. B. Thomas and W. Luk. Non-uniform random number generation through piecewise linear approximations. IET Computers and Digital Techniques, 1(4):312--321, 2007.
	23	David B. Thomas , Wayne Luk, Credit Risk Modelling using Hardware Accelerated Monte-Carlo Simulation, Proceedings of the 2008 16th International Symposium on Field-Programmable Custom Computing Machines, p.229-238, April 14-15, 2008 [doi>10.1109/FCCM.2008.41]
	24	D. B. Thomas and W. Luk. Sampling from the exponential distribution using independent bernoulli variates. In Proc. Int. Conf. on Field Programmable Logic and Applications, 2008.
	25	David B. Thomas , Wayne Luk , Philip H.W. Leong , John D. Villasenor, Gaussian random number generators, ACM Computing Surveys (CSUR), v.39 n.4, p.11-es, 2007 [doi>10.1145/1287620.1287622]
	26	C. S. Wallace, Fast pseudorandom generators for normal and exponential variates, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.119-127, March 1996 [doi>10.1145/225545.225554]
	27	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.