Linear algebra operators for GPU implementation of numerical algorithms

ABSTRACT

In this work, the emphasis is on the development of strategies to realize techniques of numerical computing on the graphics chip. In particular, the focus is on the acceleration of techniques for solving sets of algebraic equations as they occur in numerical simulation. We introduce a framework for the implementation of linear algebra operators on programmable graphics processors (GPUs), thus providing the building blocks for the design of more complex numerical algorithms. In particular, we propose a stream model for arithmetic operations on vectors and matrices that exploits the intrinsic parallelism and efficient communication on modern GPUs. Besides performance gains due to improved numerical computations, graphics algorithms benefit from this model in that the transfer of computation results to the graphics processor for display is avoided. We demonstrate the effectiveness of our approach by implementing direct solvers for sparse matrices, and by applying these solvers to multi-dimensional finite difference equations, i.e. the 2D wave equation and the incompressible Navier-Stokes equations.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: ATI, 2003. Sample effects on the ATI graphics cards. http://www.ati.com/developer/techpapers.html.
• 3: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 4: 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
• 5: Jim X. Chen , Niels da Vitoria Lobo, Toward interactive-rate simulation of fluids with moving obstacles using Navier-Stokes equations, Graphical Models and Image Processing, v.57 n.2, p.107-116, March 1995 [doi>10.1006/gmip.1995.1012]
• 6: Cassidy J. Curtis , Sean E. Anderson , Joshua E. Seims , Kurt W. Fleischer , David H. Salesin, Computer-generated watercolor, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.421-430, August 1997 [doi>10.1145/258734.258896]
• 7: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 8: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 9: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 10: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 11: Elder, G. 2002. Radeon 9700. In Proceedings Eurographics/SIGGRAPH Workshop on Graphics Hardware 2002.
• 12: 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]
• 13: 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]
• 14: Nick Foster , Dimitri Metaxas, Realistic animation of liquids, Graphical Models and Image Processing, v.58 n.5, p.471-483, Sept. 1996 [doi>10.1006/gmip.1996.0039]
• 15: Mark J. Harris , Greg Coombe , Thorsten Scheuermann , Anselmo Lastra, Physically-based visual simulation on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 16: John C. Hart, Perlin noise pixel shaders, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.87-94, August 2001, Los Angeles, California, United States [doi>10.1145/383507.383531]
• 17: Wolfgang Heidrich , Rüdiger Westermann , Hans-Peter Seidel , Thomas Ertl, Applications of pixel textures in visualization and realistic image synthesis, Proceedings of the 1999 symposium on Interactive 3D graphics, p.127-134, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300538]
• 18: Karl E. Hillesland , Sergey Molinov , Radek Grzeszczuk, Nonlinear optimization framework for image-based modeling on programmable graphics hardware, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 19: Matthias Hopf , Thomas Ertl, Accelerating 3D convolution using graphics hardware (case study), Proceedings of the conference on Visualization '99: celebrating ten years, p.471-474, October 1999, San Francisco, California, United States
• 20: Hopf, M., and Ertl, T. 2000. Hardware accelerated wavelet transformations. In Proceedings EG/IEEE TCVG Symposium on Visualization VisSym '00, 93--103.
• 21: Bruno Jobard , Gordon Erlebacher , M. Yousuff Hussaini, Lagrangian-Eulerian advection for unsteady flow visualization, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 22: Michael Kass , Gavin Miller, Rapid, stable fluid dynamics for computer graphics, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.49-57, September 1990, Dallas, TX, USA
• 23: E. Scott Larsen , David McAllister, Fast matrix multiplies using graphics hardware, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.55-55, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582089]
• 24: Erik Lindholm , Mark J. Kligard , Henry Moreton, A user-programmable vertex engine, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.149-158, August 2001 [doi>10.1145/383259.383274]
• 25: Microsoft, 2002. DirectX9 SDK. http://www.microsoft.com/DirectX.
• 26: Montrym, J., and Moreton, H. 2002. GeForce4. In Proceedings Eurographics/SIGGRAPH Workshop on Graphics Hardware 2002.
• 27: NVidia, 2002. nvidia OpenGL game of life. http://www.nvidia.com/view.asp?IO=ogl-gameoflife.
• 28: NVidia, 2003. Sample effects on the nVIDIA graphics cards. http://developer.nvidia.com/view.asp?PAGE=papers.
• 29: Marc Olano , Anselmo Lastra, A shading language on graphics hardware: the pixelflow shading system, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.159-168, July 1998 [doi>10.1145/280814.280857]
• 30: William H. Press , William T. Vetterling , Saul A. Teukolsky , Brian P. Flannery, Numerical Recipes in C++: the art of scientific computing, 2001
• 31: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 32: 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]
• 33: Strzodka, R., and Rumpf, M. 2001. Nonlinear diffusion in graphics hardware. In Proceedings EG/IEEE TCVG Symposium on Visualization 2001, 75--84.
• 34: Strzodka, R., and Rumpf, M. 2001. Using graphics cards for quantized FEM computations. In Proceedings VIIP 2001, 98--107.
• 35: Chris J. Thompson , Sahngyun Hahn , Mark Oskin, Using modern graphics architectures for general-purpose computing: a framework and analysis, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 36: Daniel Weiskopf , Matthias Hopf , Thomas Ertl, Hardware-Accelerated Visualization of Time-Varying 2D and 3D Vector Fields by Texture Advection via Programmable Per-Pixel Operations, Proceedings of the Vision Modeling and Visualization Conference 2001, p.439-446, November 21-23, 2001
• 37: Weiskopf, D., Hopf, M., and Ertl, T. 2002. Hardware-accelerated Lagrangian-Eulerian texture advection for 2D flow visualization. In Proceedings Workshop on Vision, Modeling, and Visualization VMV '02.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems

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

Keywords:
graphics hardware, numerical simulation