More Web Proxy on the site http://driver.im/

research-article

Parallel white noise generation on a GPU via cryptographic hash

Authors:

Li-Yi WeiAuthors Info & Claims

I3D '08: Proceedings of the 2008 symposium on Interactive 3D graphics and games

Pages 79 - 87

https://doi.org/10.1145/1342250.1342263

Published: 15 February 2008 Publication History

Abstract

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 still sequential, exposing performance bottlenecks and denying random accessibility for parallel computations. Furthermore, popular parallel random number generators are still based off sequential methods and can exhibit statistical bias.

In this paper, we propose a random number generator that maps well onto a parallel processor while possessing white noise distribution. Our generator is based on cryptographic hash functions whose statistical robustness has been examined under heavy scrutiny by cryptologists. We implement our generator as a GPU pixel program, allowing us to compute random numbers in parallel just like ordinary texture fetches: given a texture coordinate per pixel, instead of returning a texel as in ordinary texture fetches, our pixel program computes a random noise value based on this given texture coordinate. We demonstrate that our approach features the best quality, speed, and random accessibility for graphics applications.

References

[1]

1997. Advanced encryption standard. In FSE '97: Proceedings of the 4th International Workshop on Fast Software Encryption, Springer-Verlag, London, UK, 83--87.

[2]

Anderson, and Biham. 1996. Tiger: A fast new hash function. In IWFSE: International Workshop on Fast Software Encryption, LNCS.

Digital Library

[3]

Blum, L., Blum, M., and Shub, M. 1986. A simple unpredictable pseudo random number generator. SIAM J. Comput. 15, 2, 364--383.

Digital Library

[4]

Brands, S., and Gill, R. 1996. Cryptography, statistics and pseudo-randomness, part ii. Probability and Mathematical Statistics 16, 1--17.

[5]

Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. In SIGGRAPH '03: ACM SIGGRAPH 2003 Papers, ACM Press, New York, NY, USA, 287--294.

Digital Library

[6]

D'Agostino, R. B., and Stephens, M. A., Eds. 1986. Goodness-of-fit techniques. Marcel Dekker, Inc., New York, NY, USA.

Digital Library

[7]

Dobbertin, H., Bosselaers, A., and Preneel, B. 1996. RIPEMD-160: A strengthened version of RIPEMD. In Fast Software Encryption, 71--82.

Digital Library

[8]

Ebert, D. S., Musgrave, K., Peachey, D., Perlin, K., and Worley, S. 1998. Texturing & Modeling, A Procedural Approach. AP Professional.

Digital Library

[9]

Entacher, K., Uhl, A., and Wegenkittl, S. 1998. Linear and inversive pseudorandom numbers for parallel and distributed simulation. In PADS '98: Proceedings of the twelfth workshop on Parallel and distributed simulation, IEEE Computer Society, Washington, DC, USA, 90--97.

Digital Library

[10]

Howes, L., and Thomas, D. 2007. Efficient random number generation and application using CUDA. In GPU Gems 3, H. Nguyen, Ed. Addison Wesley, July, ch. 37, 805--830.

[11]

Knuth, D. 1998. The Art of Computer Programming. Addison-Wesley Publishing Company.

Digital Library

[12]

Lagae, A., and Dutré, P. 2006. An alternative for wang tiles: colored edges versus colored corners. ACM Trans. Graph. 25, 4, 1442--1459.

Digital Library

[13]

Lagae, A., and Dutré, P. 2006. A comparison of methods for generating Poisson disk distributions. Report CW 459, Department of Computer Science, K. U. Leuven, Leuven, Belgium, August.

[14]

L'Ecuyer, P., Simard, R., Chen, E., and Kelton, W., 2001. An object-oriented randomnumber package with many long streams and substreams.

[15]

Lefebvre, S., and Hoppe, H. 2005. Parallel controllable texture synthesis. ACM Trans. Graph. 24, 3, 777--786.

Digital Library

[16]

Lefebvre, S., and Hoppe, H. 2006. Perfect spatial hashing. ACM Trans. Graph. 25, 3, 579--588.

Digital Library

[17]

Lefebvre, S., and Neyret, F. 2003. Pattern based procedural textures. In I3D '03: Proceedings of the 2003 symposium on Interactive 3D graphics, ACM Press, New York, NY, USA, 203--212.

Digital Library

[18]

Marsaglia, G., 1995. The marsaglia random number cdrom including the diehard battery of tests of randomness. http://www.stat.fsu.edu/pub/diehard/.

[19]

Mascagni, and Srinivasan. 2000. SPRNG: A scalable library for pseudorandom number generation. ACMTMS: ACM Transactions on Mathematical Software 26.

Digital Library

[20]

Matsumoto, M., and Nishimura, T. 1998. Mersenne twister: a 623-dimensionally equidistributed uniform pseudorandom number generator. ACM Trans. Model. Comput. Simul. 8, 1, 3--30.

Digital Library

[21]

(NSA), N. S. A., 2001. Us secure hash algorithm 1 (sha1). http://tools.ietf.org/html/rfc3174.

[22]

NVIDIA, 2007. Ext_gpu_shader4 opengl extension. http://developer.download.nvidia.com/opengl/specs/GL_EXT_gpu_shader4.txt.

[23]

NVIDIA, 2007. Nvidia cuda compute unified device architecture. http://developer.download.nvidia.com/compute/cuda/1_0/NVIDIA_CUDA_Programming_Guide_1.0.pdf.

[24]

Olano, M. 2005. Modified noise for evaluation on graphics hardware. In HWWS '05: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, ACM Press, New York, NY, USA, 105--110.

Digital Library

[25]

Pang, W.-M., Wong, T.-T., and Heng, P.-A. 2006. Implementing high-quality prng on gpus. In Shader X5: Advanced Rendering Techniques, Charles River Media, Inc., Rockland, MA, USA, 579--590.

[26]

Patel, M., 2006. The goulburn hashing function. http://www.geocities.com/drone115b/Goulburn06.pdf.

[27]

Peachey, D. 1990. Texture on demand. Tech. Rep. technical memo 217, Pixar.

[28]

Perlin, K. 1985. An image synthesizer. In Computer Graphics (Proceedings of SIGGRAPH 85), 287--296.

Digital Library

[29]

Perlin, K. 2002. Improving noise. ACM Transactions on Graphics 21, 3 (July), 681--682.

Digital Library

[30]

Podlozhnyuk, V., 2007. Parallel mersenne twister. http://developer.download.nvidia.com/compute/cuda/sdk/website/projects/MersenneTwister/doc/MersenneTwister.pdf.

[31]

Rivest, R., 1992. Rfc 1321: The md5 message-digest algorithm. Reference implementation: http://www.faqs.org/rfcs/rfc1321.html.

Digital Library

[32]

Rost, R. J. 2004. OpenGL(R) Shading Language. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA.

Digital Library

[33]

Sussman, M., Crutchfield, W., and Papakipos, M. 2006. Pseudorandom number generation on the gpu. In Graphics Hardware 2006, 87--94.

Digital Library

[34]

The IEEE, and The Open Group. 2004. The Open Group Base Specifications Issue 6.

[35]

Wang, X., and Yu, H. 2005. How to break md5 and other hash functions. In EUROCRYPT, 19--35.

Digital Library

[36]

Wayner, P. 2002. Disappearing Cryptography. Morgan Kaufmann.

Digital Library

[37]

Wei, L.-Y., and Levoy, M. 2002. Order-independent texture synthesis. Tech. Rep. TR-2002-01, Computer Science Department, Stanford University.

[38]

Wei, L.-Y., 2004. A system and method of generating white noise for use in graphics and image processing. U.S. Patent Pending No. 10/956, 954, filed September 30, 2004 with NVIDIA Corp.

[39]

Wei, L.-Y. 2004. Tile-based texture mapping on graphics hardware. In HWWS '04: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, ACM Press, New York, NY, USA, 55--63.

Digital Library

[40]

Yamanouchi, T. 2007. Aes encryption and decryption on the gpu. In GPU Gems 3, H. Nguyen, Ed. Addison Wesley, July, ch. 36, 785--803.

Cited By

Bostanci FOlgun AOrosa LYaglikci AKim JHassan HErgin OMutlu O(2022)DR-STRaNGe: End-to-End System Design for DRAM-based True Random Number Generators2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA53966.2022.00087(1141-1155)Online publication date: Apr-2022
https://doi.org/10.1109/HPCA53966.2022.00087
Okada KBrumby PYasuoka K(2021)The influence of random number generation in dissipative particle dynamics simulations using a cryptographic hash functionPLOS ONE10.1371/journal.pone.025059316:4(e0250593)Online publication date: 27-Apr-2021
https://doi.org/10.1371/journal.pone.0250593
Tian HWang CManocha DZhang X(2019)Realtime Hand-Object Interaction Using Learned Grasp Space for Virtual EnvironmentsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.284938125:8(2623-2635)Online publication date: 1-Aug-2019
https://doi.org/10.1109/TVCG.2018.2849381
Show More Cited By

Index Terms

Parallel white noise generation on a GPU via cryptographic hash

Recommendations

Recycling random bits in parallel
HICSS '95: Proceedings of the 28th Hawaii International Conference on System Sciences

Shows that r pseudo-random bits can be obtained by concatenating t blocks of r/t pseudo-random bits, where the blocks are generated in parallel. This can be considered as a parallel version of R. Impagliazzo and D. Zuckerman's (1989) method of recycling ...
GPU random numbers via the tiny encryption algorithm
HPG '10: Proceedings of the Conference on High Performance Graphics

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 ...
Bit-Wise Behavior of Random Number Generators

In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

I3D '08: Proceedings of the 2008 symposium on Interactive 3D graphics and games

February 2008

219 pages

ISBN:9781595939838

DOI:10.1145/1342250

Conference Chairs:
Eric Haines
Autodesk
,
Morgan McGuire
Williams College

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 February 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

I3D08

Sponsor:

SIGGRAPH

I3D08: Symposium on Interactive 3D Graphics and Games

February 15 - 17, 2008

California, Redwood City

Acceptance Rates

Overall Acceptance Rate 148 of 485 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
947
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bostanci FOlgun AOrosa LYaglikci AKim JHassan HErgin OMutlu O(2022)DR-STRaNGe: End-to-End System Design for DRAM-based True Random Number Generators2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA53966.2022.00087(1141-1155)Online publication date: Apr-2022
https://doi.org/10.1109/HPCA53966.2022.00087
Okada KBrumby PYasuoka K(2021)The influence of random number generation in dissipative particle dynamics simulations using a cryptographic hash functionPLOS ONE10.1371/journal.pone.025059316:4(e0250593)Online publication date: 27-Apr-2021
https://doi.org/10.1371/journal.pone.0250593
Tian HWang CManocha DZhang X(2019)Realtime Hand-Object Interaction Using Learned Grasp Space for Virtual EnvironmentsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.284938125:8(2623-2635)Online publication date: 1-Aug-2019
https://doi.org/10.1109/TVCG.2018.2849381
Zaporozhko VShardakov VParfenov D(2019)Simulation of Multimedia Data Parallelization Process when Processing on CPU and GPU in Online Learning Cloud Platforms2019 International Russian Automation Conference (RusAutoCon)10.1109/RUSAUTOCON.2019.8867796(1-5)Online publication date: Sep-2019
https://doi.org/10.1109/RUSAUTOCON.2019.8867796
Kim JPatel MHassan HOrosa LMutlu O(2019)D-RaNGe: Using Commodity DRAM Devices to Generate True Random Numbers with Low Latency and High Throughput2019 IEEE International Symposium on High Performance Computer Architecture (HPCA)10.1109/HPCA.2019.00011(582-595)Online publication date: Feb-2019
https://doi.org/10.1109/HPCA.2019.00011
Kirillov A(2018)Non-periodic Tiling of Procedural Noise FunctionsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/32333061:2(1-15)Online publication date: 24-Aug-2018
https://dl.acm.org/doi/10.1145/3233306
Aljahdali AMascagni M(2017)Feistel-inspired scrambling improves the quality of linear congruential generatorsMonte Carlo Methods and Applications10.1515/mcma-2017-010523:2(89-99)Online publication date: 20-May-2017
https://doi.org/10.1515/mcma-2017-0105
Mokhtari RStumm M(2017)The SEPO Model of Computation to Enable Larger-Than-Memory Hash Tables for GPU-Accelerated Big Data Analytics2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2017.122(866-875)Online publication date: May-2017
https://doi.org/10.1109/IPDPS.2017.122
L’Ecuyer PMunger DOreshkin BSimard R(2017)Random numbers for parallel computers: Requirements and methods, with emphasis on GPUsMathematics and Computers in Simulation10.1016/j.matcom.2016.05.005135(3-17)Online publication date: May-2017
https://doi.org/10.1016/j.matcom.2016.05.005
Pianu DNerino RFerraris CChimienti A(2016)A novel approach to train random forests on GPU for computer vision applications using local featuresThe International Journal of High Performance Computing Applications10.1177/109434201562267230:3(290-304)Online publication date: 28-Jul-2016
https://doi.org/10.1177/1094342015622672
Show More Cited By

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