Parallel white noise generation on a GPU via cryptographic hash

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: Ross J. Anderson , Eli Biham, TIGER: A Fast New Hash Function, Proceedings of the Third International Workshop on Fast Software Encryption, p.89-97, February 21-23, 1996
• 3: L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
• 4: Brands, S., and Gill, R. 1996. Cryptography, statistics and pseudo-randomness, part ii. Probability and Mathematical Statistics 16, 1--17.
• 5: Michael F. Cohen , Jonathan Shade , Stefan Hiller , Oliver Deussen, Wang Tiles for image and texture generation, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 6: Ralph B D'Agostino , Michael A Stephens, Goodness-of-fit techniques, Marcel Dekker, Inc., New York, NY, 1986
• 7: Hans Dobbertin , Antoon Bosselaers , Bart Preneel, RIPEMD-160: A Strengthened Version of RIPEMD, Proceedings of the Third International Workshop on Fast Software Encryption, p.71-82, February 21-23, 1996
• 8: David S. Ebert , F. Kenton Musgrave , Darwyn Peachey , Ken Perlin , Steven Worley, Texturing and modeling: a procedural approach, Academic Press Professional, Inc., San Diego, CA, 1994
• 9: K. Entacher , A. Uhl , S. Wegenkittl, Linear and inversive pseudorandom numbers for parallel and distributed simulation, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.90-97, May 26-29, 1998, Banff, Alberta, Canada
• 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: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 12: Ares Lagae , Philip Dutré, An alternative for Wang tiles: colored edges versus colored corners, ACM Transactions on Graphics (TOG), v.25 n.4, p.1442-1459, October 2006 [doi>10.1145/1183287.1183296]
• 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: Pierre L'Ecuyer , Richard Simard , E. Jack Chen , W. David Kelton, An Object-Oriented Random-Number Package with Many Long Streams and Substreams, Operations Research, v.50 n.6, p.1073-1075, November 2002 [doi>10.1287/opre.50.6.1073.358]
• 15: Sylvain Lefebvre , Hugues Hoppe, Parallel controllable texture synthesis, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 16: Sylvain Lefebvre , Hugues Hoppe, Perfect spatial hashing, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 17: Sylvain Lefebvre , Fabrice Neyret, Pattern based procedural textures, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641518]
• 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: Michael Mascagni , Ashok Srinivasan, Algorithm 806: SPRNG: a scalable library for pseudorandom number generation, ACM Transactions on Mathematical Software (TOMS), v.26 n.3, p.436-461, Sept. 2000 [doi>10.1145/358407.358427]
• 20: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 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: Marc Olano, Modified noise for evaluation on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 30-31, 2005, Los Angeles, California [doi>10.1145/1071866.1071883]
• 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: Ken Perlin, An image synthesizer, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.287-296, July 1985
• 29: Ken Perlin, Improving noise, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 30: Podlozhnyuk, V., 2007. Parallel mersenne twister. http://developer.download.nvidia.com/compute/cuda/sdk/website/projects/MersenneTwister/doc/MersenneTwister.pdf.
• 31: R. Rivest, The MD5 Message-Digest Algorithm, RFC Editor, 1992
• 32: Randi J. Rost, OpenGL(R) Shading Language, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 2004
• 33: M. Sussman , W. Crutchfield , M. Papakipos, Pseudorandom number generation on the GPU, Proceedings of the 21st ACM SIGGRAPH/Eurographics symposium on Graphics hardware, September 03-04, 2006, Vienna, Austria [doi>10.1145/1283900.1283914]
• 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.
• 36: Peter Wayner, Disappearing Cryptography: Information Hiding: Steganography and Watermarking (2nd Edition), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2002
• 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: Li-Yi Wei, Tile-based texture mapping on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058138]
• 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.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

Keywords:
GPU techniques, noise, parallel computation, random number generation, texturing