research-article

GPU random numbers via the tiny encryption algorithm

Authors:

Aaron CurtisAuthors Info & Claims

HPG '10: Proceedings of the Conference on High Performance Graphics

Pages 133 - 141

Published: 25 June 2010 Publication History

Abstract

Random numbers are extensively used on the GPU. As more computation is ported to the GPU, it can no longer be treated as rendering hardware alone. Random number generators (RNG) are expected to cater general purpose and graphics applications alike. Such diversity adds to expected requirements of a RNG. A good GPU RNG should be able to provide repeatability, random access, multiple independent streams, speed, and random numbers free from detectable statistical bias. A specific application may require some if not all of the above characteristics at one time. In particular, we hypothesize that not all algorithms need the highest-quality random numbers, so a good GPU RNG should provide a speed quality tradeoff that can be tuned for fast low quality or slower high quality random numbers.

We propose that the Tiny Encryption Algorithm satisfies all of the requirements of a good GPU Pseudo Random Number Generator. We compare our technique against previous approaches, and present an evaluation using standard randomness test suites as well as Perlin noise and a Monte-Carlo shadow algorithm. We show that the quality of random number generation directly affects the quality of the noise produced, however, good quality noise can still be produced with a lower quality random number generator.

References

[1]

{Ada97} Adams C.: The CAST-128 Encryption Algorithm. Tech. rep., RFC Editor, United States, 1997. 3

Digital Library

[2]

{BBS86} Blum L., Blum M., Shub M.: A simple unpredictable pseudo-random number generator. SIAM Journal on Computing 15, 2 (May 1986), 364--383. 2

Digital Library

[3]

{CD05} Cook R. L., DeRose T.: Wavelet noise. In SIGGRAPH '05: ACM SIGGRAPH 2005 Papers (New York, NY, USA, 2005), ACM SIGGRAPH, ACM, pp. 803--811. 2

Digital Library

[4]

{CPC84} Cook R. L., Porter T., Carpenter L.: Distributed ray tracing. In SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1984), ACM SIGGRAPH, ACM, pp. 137--145. 2

Digital Library

[5]

{Cur09} Curtis A.: Real-time Soft Shadows on the GPU via Monte Carlo Sampling. Master's thesis, University of Maryland, Baltimore County, 2009. 2, 7

[6]

{DS86} D'Agostino R. B., Stephens M. A.: Goodness of fit techniques. CRC Press, 1986. 5

Digital Library

[7]

{EMP*98} Ebert D. S., Musgrave K., Peacey D., Perlin K., Andworley S.: Texturing and Modeling, A Procedural Approach. Morgan Kaufmann, 1998. 2

Digital Library

[8]

{GBP06} Guennebaud G., Barthe L., Paulin M.: Real-time soft shadow mapping by backprojection. In Eurographics Symposium on Rendering (EGSR), Nicosia, Cyprus, 26/06/2006-28/06/2006 (http://www.eg.org/, 2006), Eurographics, pp. 227--234. 7

Digital Library

[9]

{Gre05} Green S.: Implementing improved Perlin noise. In GPU Gems 2, Pharr M., (Ed.). Addison-Wesley, 2005, ch. 26. 2, 3

[10]

{GZD08} Goldberg A., Zwicker M., Durand F.: Anisotropic noise. In SIGGRAPH '08: ACM SIGGRAPH 2008 papers (New York, NY, USA, 2008), ACM, pp. 1--8. 2, 6

Digital Library

[11]

{HJK*04} Hanrahan P., Jeremy S., Kayvon F., Houston M., Foley T., Horn D.: Gpu bench, 2004. ACM Workshop on General Purpose Computing on Graphics Processors. graphics.stanford.edu/projects/gpubench. 3

[12]

{Jen96} Jensen H. W.: Realistic image synthesis using photon mapping. In Proceedings of the Eurographics workshop on Rendering Techniques (1996), pp. 21--30. 2

[13]

{KHN06} Keller A., Heinrich S., Niederreiter H.: Monte Carlo and Quasi-Monte Carlo Methods. Springer-Verlag, 2006. 2

[14]

{KKS08} Kensler A., Knoll A., Shirley P.: Better Gradient Noise. Tech. Rep. UUSCI-2008-001, SCI Institute, 2008. 2, 3, 7

[15]

{Knu97} Knuth D. E.: The Art of Computer Programming, third ed., vol. 2. Addison-Wesley, 1997. 2

[16]

{Lew89} Lewis J. P.: Algorithms for solid noise synthesis. In SIGGRAPH '89: Proceedings of the 16th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1989), ACM Press, pp. 263--270. 2

Digital Library

[17]

{LLDD09} Lagae A., Lefebvre S., Drettakis G., Dutré P.: Procedural noise using sparse gabor convolution. In SIGGRAPH '09: ACM SIGGRAPH 2009 papers (New York, NY, USA, 2009), ACM, pp. 1--10. 2, 6

Digital Library

[18]

{Mar95} Marsaglia G.: The MARSAGLIA random number cdrom including the DIEHARD battery of tests of randomness v0.2 beta, 1995. http://i.cs.hku.hk/diehard/. 2, 4

[19]

{MN98} Matsumoto M., Nishimura T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation 8, 1 (1998), 3--30. 2

Digital Library

[20]

{NVI07} NVIDIA: NVIDIA CUDA compute unified device architecture, 2007. http://developer.download.nvidia.com/compute/cuda/1_0/NVIDIA_CUDA_Programming_Guide_1.0.pdf. 2, 4

[21]

{Ola05} Olano M.: Modified noise for evaluation on graphics hardware. In GH '05: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware (New York, NY, USA, 2005), ACM, pp. 105--110. 2, 3, 6, 7

Digital Library

[22]

{Per85} Perlin K.: An image synthesizer. In SIGGRAPH '85: Proceedings of the 12th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1985), ACM, pp. 287--296. 2, 3

Digital Library

[23]

{Per02} Perlin K.: Improving noise. In SIGGRAPH '02: Proceedings of the 29th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 2002), ACM, pp. 681--682. 2, 6, 7

Digital Library

[24]

{Per04} Perlin K.: Implementing improved perlin noise. In GPU Gems, Fernando R., (Ed.). Addison-Wesley, 2004, ch. 5. 2, 3

[25]

{PWH06} Pang W. M., Wong T. T., Heng P. A.: ShaderX5: Advanced Rendering Techniques. Charles River Media, 2006, ch. 9.8: Implementing High-Quality PRNG on GPU. 2

[26]

{Red03} Reddy V.: A cryptanalysis of the Tiny Encryption Algorithm. Master's thesis, University of Alabama, 2003. 3, 4, 5

[27]

{Riv92a} Rivest R.: The MD5 Message-Digest Algorithm. Tech. rep., RFC Editor, 1992. 2, 3

Digital Library

[28]

{Riv92b} Rivest R. L.: The RC4 Encryption Algorithm. Tech. rep., RSA Data Security, Inc., March 1992. 3

[29]

{Ros04} Rost R. J.: The OpenGL Shading Language. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 2004. 4

Digital Library

[30]

{RSN*08} Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S.: A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications. Tech. rep., NIST Special Publication, August 2008. 2

[31]

{Sch94} Schneier B.: Description of a new variable-length key, 64-bit block cipher (blowfish). In Fast Software Encryption, Cambridge Security Workshop (London, UK, 1994), Springer-Verlag, pp. 191--204. 3

Digital Library

[32]

{TW08} Tzeng S., Wei L.-Y.: Parallel white noise generation on a GPU via cryptographic hash. In I3D '08: Proceedings of the 2008 symposium on Interactive 3D graphics and games (New York, NY, USA, 2008), ACM, pp. 79--87. 1, 2, 3, 4, 5, 6, 7

Digital Library

[33]

{VG97} Veach E., Guibas L. J.: Metropolis light transport. In SIGGRAPH '97: Proceedings of the 24th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1997), ACM Press/Addison-Wesley Publishing Co., pp. 65--76. 2

Digital Library

[34]

{WN94} Wheeler D. J., Needham R. M.: TEA, a tiny encryption algorithm. In Lecture Notes in Computer Science. Fast Software Encryption: Second International Workshop (1994), pp. 363--366. 2, 3

[35]

{Zaf10} Zafar F.: Tiny Encryption Algorithm for Cryptographic Gradient Noise. Master's thesis, University of Maryland, Baltimore County, 2010. 4

Cited By

L'Ecuyer PNadeau-Chamard OChen YLebar J(2021)Multiple streams with recurrence-based, counter-based, and splittable random number generatorsProceedings of the Winter Simulation Conference10.5555/3522802.3522883(1-16)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522883
L'Ecuyer P(2015)Random number generation with multiple streams for sequential and parallel computingProceedings of the 2015 Winter Simulation Conference10.5555/2888619.2888623(31-44)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.5555/2888619.2888623
Davidovič TKřivánek JHašan MSlusallek P(2014)Progressive Light Transport Simulation on the GPUACM Transactions on Graphics10.1145/260214433:3(1-19)Online publication date: 2-Jun-2014
https://dl.acm.org/doi/10.1145/2602144
Show More Cited By

Index Terms

GPU random numbers via the tiny encryption algorithm

Recommendations

Parallel white noise generation on a GPU via cryptographic hash
I3D '08: Proceedings of the 2008 symposium on Interactive 3D graphics and games

A good random number generator is essential for many graphics applications. As more such applications move onto parallel processing, it is vital that a good parallel random number generator be used. Unfortunately, most random number generators today are ...
Random Numbers for Quantum Key Distribution
SYNASC '08: Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

Quantum Key Distribution (QKD) has seen an important development for the last ten years. Nowadays, different companies offer commercial solutions and key exchanges at pulse rates of up to 1 GHz and over distances of up to 00km have been demonstrated in ...
Parallel random numbers: as easy as 1, 2, 3
SC '11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis

Most pseudorandom number generators (PRNGs) scale poorly to massively parallel high-performance computation because they are designed as sequentially dependent state transformations. We demonstrate that independent, keyed transformations of counters ...

Reviews

Reviewer: Soubhik Chakraborty

Random number generators (RNGs) serve many purposes, from Monte Carlo simulations to computer graphics. The modern graphics processing unit (GPU) is a high-performance programmable parallel processor. A good GPU RNG should provide speed, random access, repeatability, and little statistical bias. The main contribution of this paper is in identifying the tiny encryption algorithm (TEA) as quite suitable for GPU random number generation. TEA uses simple but fast operations on modern GPUs with minimal state and internal data tables. "Additionally," claim the authors, "we can vary the number of TEA rounds to provide a speed/quality tradeoff." Another contribution of this paper is the idea that fewer rounds of TEA suffice for several visual applications. The authors compare their approach with those of other researchers, and evaluate their technique using standard randomness tests, such as that of the National Institute of Standards and Technology (NIST) and DIEHARD, as well as Perlin noise and a Monte Carlo shadow algorithm. I found the paper to be interesting. It should appeal to computing researchers and post-graduates, especially those in statistical computing. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HPG '10: Proceedings of the Conference on High Performance Graphics

June 2010

189 pages

General Chairs:
Justin Hensley
AMD
,
Philipp Slusallek
DFKI & Saarland University, Germany
,
Program Chairs:
David McAllister
NVIDIA
,
Christiaan Gribble
Grove City College

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 25 June 2010

Check for updates

Author Tags

Qualifiers

Research-article

Conference

HPG'10

Sponsor:

SIGGRAPH
EUROGRAPHICS

HPG'10: High Performance Graphics

June 25 - 27, 2010

Saarbrucken, Germany

Acceptance Rates

Overall Acceptance Rate 15 of 44 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
403
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

L'Ecuyer PNadeau-Chamard OChen YLebar J(2021)Multiple streams with recurrence-based, counter-based, and splittable random number generatorsProceedings of the Winter Simulation Conference10.5555/3522802.3522883(1-16)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522883
L'Ecuyer P(2015)Random number generation with multiple streams for sequential and parallel computingProceedings of the 2015 Winter Simulation Conference10.5555/2888619.2888623(31-44)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.5555/2888619.2888623
Davidovič TKřivánek JHašan MSlusallek P(2014)Progressive Light Transport Simulation on the GPUACM Transactions on Graphics10.1145/260214433:3(1-19)Online publication date: 2-Jun-2014
https://dl.acm.org/doi/10.1145/2602144
Salmon JMoraes MDror RShaw DLathrop SCosta JKramer W(2011)Parallel random numbersProceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/2063384.2063405(1-12)Online publication date: 12-Nov-2011
https://dl.acm.org/doi/10.1145/2063384.2063405
Nandapalan NBrent RMurray LRendell A(2011)High-performance pseudo-random number generation on graphics processing unitsProceedings of the 9th international conference on Parallel Processing and Applied Mathematics - Volume Part I10.1007/978-3-642-31464-3_62(609-618)Online publication date: 11-Sep-2011
https://dl.acm.org/doi/10.1007/978-3-642-31464-3_62
Neves SAraujo F(2011)Fast and small nonlinear pseudorandom number generators for computer simulationProceedings of the 9th international conference on Parallel Processing and Applied Mathematics - Volume Part I10.1007/978-3-642-31464-3_10(92-101)Online publication date: 11-Sep-2011
https://dl.acm.org/doi/10.1007/978-3-642-31464-3_10

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents