Hardware-aware analysis and optimization of stable fluids

ABSTRACT

We perform a detailed flop and bandwidth analysis of Jos Stam's Stable Fluids algorithm on the CPU, GPU, and Cell. In all three cases, we find that the algorithm is bandwidth bound, with the cores sitting idle up to 96% of the time. Knowing this, we propose two modifications to accelerate the algorithm. First, a Mehrstellen discretization for the pressure solver which reduces the running time of the solver by a third. Second, a static caching scheme that eliminates roughly 99% of the random lookups in the advection stage. We observe a 2x speedup in the advection stage using this scheme. Both modifications apply equally well to all three architectures.

REFERENCES

• 1: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 2: Collatz, L. 1960. The Numerical Treatment of Differential Equations. Springer-Verlag.
• 3: Crane, K., Tariq, S., and Llamas, I. 2007. GPU Gems 3. ch. Real-time Simulation and Rendering of 3D Fluids.
• 4: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 5: Douglas Enright , Ronald Fedkiw , Joel Ferziger , Ian Mitchell, A hybrid particle level set method for improved interface capturing, Journal of Computational Physics, v.183 n.1, p.83-116, November 20, 2002 [doi>10.1006/jcph.2002.7166]
• 6: Ronald Fedkiw , Jos Stam , Henrik Wann Jensen, Visual simulation of smoke, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.15-22, August 2001 [doi>10.1145/383259.383260]
• 7: Nick Foster , Ronald Fedkiw, Practical animation of liquids, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.23-30, August 2001 [doi>10.1145/383259.383261]
• 8: Nolan Goodnight , Cliff Woolley , Gregory Lewin , David Luebke , Greg Humphreys, A multigrid solver for boundary value problems using programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 9: Murli M. Gupta , Jules Kouatchou , Jun Zhang, Comparison of second- and fourth-order discretizations for multigrid Poisson solvers, Journal of Computational Physics, v.132 n.2, p.226-232, April 1997 [doi>10.1006/jcph.1996.5466]
• 10: Harada, T., Koshizuka, S., and Kawaguchi, Y. 2007. Smoothed particle hydrodynamics on gpus. In Computer Graphics International, 63--70.
• 11: Mark Harris, Fast fluid dynamics simulation on the GPU, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198790]
• 12: Mark Harris, Mapping computational concepts to GPUs, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198768]
• 13: IBM, 2007. Cell broadband engine programming handbook. http://www-01.ibm.com/chips/techlib/techlib.nsf/products/Cell_Broadband_Engine.
• 14: Intel, 2007. Dual-core intel xeon processor 5100 series datasheet. http://www.intel.com/design/xeon/datashts/313355.htm.
• 15: Byungmoon Kim , Yingjie Liu , Ignacio Llamas , Xiangmin Jiao , Jarek Rossignac, Simulation of bubbles in foam with the volume control method, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 16: Michael Kistler , Michael Perrone , Fabrizio Petrini, Cell Multiprocessor Communication Network: Built for Speed, IEEE Micro, v.26 n.3, p.10-23, May 2006 [doi>10.1109/MM.2006.49]
• 17: Bryan M. Klingner , Bryan E. Feldman , Nuttapong Chentanez , James F. O'Brien, Fluid animation with dynamic meshes, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 18: Lax, P., and Wendroff, B. 1960. Systems of conservation laws. Communications on Pure and Applied Mathematics, 217--237.
• 19: Li, W., Wei, X., and Kaufman, A. 2003. Implementing lattice boltzmann computation on graphics hardware. The Visual Computer, 444--456.
• 20: Kenneth Moreland , Edward Angel, The FFT on a GPU, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 21: Nvidia, 2007. Geforce 8 series. http://www.nvidia.com/page/geforce8.html.
• 22: Nvidia. 2007. Nvidia CUDA Programming Guide.
• 23: SLEPc, 2007. Scalable library for eigenvalue problem computations. http://www.grycap.upv.es/slepc/.
• 24: Smith, R., 2007. Ode: Open dynamics engine. http://www.ode.org/.
• 25: Jos Stam, Stable fluids, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.121-128, July 1999 [doi>10.1145/311535.311548]
• 26: Stam, J. 2003. Real-time fluid dynamics for games. In Proceedings of the Game Developer Conference.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

General Terms:
Algorithms, Experimentation