“Linear algebra operators for GPU implementation of numerical algorithms” by Krüger and Westermann

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.

1. ANDERSON, E., BAI, Z., BISCHOF, C., BLACKFORD, S., DEMMEL, J., DONGARRA, J., DU CROZ, J., GREENBAUM, A., HAMMARLING, S., MCKENNEY, A., AND SORENSEN, D. 1999. LAPACK Users’ Guide, third ed. Society for Industrial and Applied Mathematics, Philadelphia, PA. Google Scholar
2. ATI, 2003. Sample effects on the ATI graphics cards. http://www.ati.com/developer/techpapers.html.Google Scholar
3. BARAFF, D., AND WITKIN, A. 1998. Large steps in cloth simulation. Computer Graphics SIGGRAPH 98 Proceedings, 43–54. Google Scholar
4. BOLZ, J., FARMER, I., GRINSPUN, E., AND SCHROEDER, P. 2003. Sparse matrix solvers on the GPU: Conjugate gradients and multigrid. Computer Graphics SIGGRAPH 03 Proceedings. Google Scholar
5. CHEN, J., AND DA VITORIA LOBO, N. 1995. Towards interactive-rate simulation of fluids with moving obstacles using Navier-Stokes equations. Graphical Models and Image Processing 57, 2. Google ScholarDigital Library
6. CURTIS, C., ANDERSON, S., SEIMS, J., FLEISCHER, F., AND SALESIN, D. 1997. Computer-generated watercolor. Computer Graphics SIGGRAPH 97 Proceedings. Google Scholar
7. DEBUNNE, G., DESBRUN, M., M.-P., C., AND BARR, A. 2001. Dynamic real-time deformations using space and time adaptive sampling. In Computer Graphics SIGGRAPH 01 Proceedings. Google Scholar
8. DESBRUN, M., MEYER, M., SCHROEDER, P., AND BARR, A. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Computer Graphics SIGGRAPH 99 Proceedings, 317–324. Google Scholar
9. DONGARRA, J., DU CROZ, J., HAMMARLING, S., AND HANSON, R. 1988. An extended set of FORTRAN basic linear algebra subprograms. ACM Transactions on Mathematical Software 14, 1–17. Google ScholarDigital Library
10. DONGARRA, J., DU CROZ, J., HAMMARLING, S., AND HANSON, R. 1990. A set of level 3 basic linear algebra subprograms,. ACM Transactions on Mathematical Software 16, 1–17. Google ScholarDigital Library
11. ELDER, G. 2002. Radeon 9700. In Proceedings Eurographics/SIGGRAPH Workshop on Graphics Hardware 2002.Google Scholar
12. FEDKIW, R., STAM, J., AND JENSEN, H. 2001. Visual simulation of smoke. Computer Graphics SIGGRAPH 01 Proceedings, 15–22. Google Scholar
13. FOSTER, N., AND FEDKIW, R. 2001. Practical animation of liquids. Computer Graphics SIGGRAPH 01 Proceedings, 23–30. Google Scholar
14. FOSTER, N., AND METAXAS, D. 1996. Realistic animation of liquids. Graphical Models and Image Processing 58, 5, 471–483. Google ScholarDigital Library
15. HARRIS, M., COOMBE, G., SCHEUERMANN, T., AND LASTRA, A. 2002. Physically-based visual simulation on graphics hardware. In Proceedings Eurographics/SIGGRAPH Workshop on Graphics Hardware 2002. Google ScholarDigital Library
16. HART, J. 2001. Perlin noise pixel shaders. In ProceedingsEurographics/SIGGRAPH Workshop on Graphics Hardware 2001. Google ScholarDigital Library
17. HEIDRICH, W., WESTERMANN, R., SEIDEL, H.-P., AND ERTL, T. 1999. Applications of pixel textures in visualization and realistic image synthesis. In ACM Symposium on Interactive 3D Graphics, 110–119. Google Scholar
18. HILLLESLAND, K., MOLINOV, S., AND GRZESZCZUK, R. 2003. Nonlinear Optimization Framework for Image-Based Modelling on Programmable Graphics Hardware. Computer Graphics SIGGRAPH 03 Proceedings. Google Scholar
19. HOPF, M., AND ERTL, T. 1999. Accelerating 3D convolution using graphics hardware. In Proceedings IEEE Visualization’99, 471–474. Google Scholar
20. HOPF, M., AND ERTL, T. 2000. Hardware accelerated wavelet transformations. In Proceedings EG/IEEE TCVG Symposium on Visualization VisSym ’00, 93–103.Google ScholarCross Ref
21. JOBARD, B., ERLEBACHER, G., AND HUSSAINI, Y. 2000. Lagrangian-Eulerian advection of noise and dye textures for unsteady flow visualization. In Proceedings IEEE Visualization’00, 110–118. Google Scholar
22. KAAS, M., AND MILLER, G. 1990. Rapid, stable fluid dynamics for computer graphics. Computer Graphics SIGGRAPH 90 Proceedings, 49–57. Google Scholar
23. LARSEN, E. S., AND MCALLISTER, D. 2001. Fast matrix multiplies using graphics hardware. In Proceedings Supercomputing 2001. Google Scholar
24. LINDHOLM, E., KILGARD, M., AND MORETON, H. 2001. A user programmable vertex engine. Computer Graphics SIGGRAPH 01 Proceedings. Google Scholar
25. MICROSOFT, 2002. DirectX9 SDK. http://www.microsoft.com/DirectX.Google Scholar
26. MONTRYM, J., AND MORETON, H. 2002. GeForce4. In Proceedings Eurographics/SIGGRAPH Workshop on Graphics Hardware 2002.Google Scholar
27. NVIDIA, 2002. nvidia OpenGL game of life. http://www.nvidia.com/view.asp?IO=ogl_gameoflife.Google Scholar
28. NVIDIA, 2003. Sample effects on the nVIDIA graphics cards. http://developer.nvidia.com/view.asp?PAGE=papers.Google Scholar
29. OLANO, M., AND LASTRA, A. 1998. A shading-language on graphics hardware. Computer Graphics SIGGRAPH 98 Proceedings, 159–168. Google Scholar
30. PRESS, W., TEUKOLSKY, S., VETTERLING, W., AND FLANNERY, B. 2002. Numerical Recipes in C++: The Art of Scientific Computing. Cambridge University Press. Google Scholar
31. PURCELL, T., BUCK, I., MARK, W., AND HANRAHAN, P. 2002. Ray tracing on programmable graphics hardware. Computer Graphics SIGGRAPH 98 Proceedings, 703–712. Google Scholar
32. STAM, J. 1999. Stable fluids. Computer Graphics SIGGRAPH 99 Proceedings, 121–128. Google Scholar
33. STRZODKA, R., AND RUMPF, M. 2001. Nonlinear diffusion in graphics hardware. In Proceedings EG/IEEE TCVG Symposium on Visualization 2001, 75–84. Google Scholar
34. STRZODKA, R., AND RUMPF, M. 2001. Using graphics cards for quantized FEM computations. In Proceedings VIIP 2001, 98–107.Google Scholar
35. THOMPSON, C., HAHN, S., AND OSKIN, M. 2002. Using modern graphics architectures for general-purpose computing: A framework and analysis. Proceedings of 35th International Symposium on Microarchitecture (MICRO-35). Google Scholar
36. WEISKOPF, D., HOPF, M., AND ERTL, T. 2001. Hardware-accelerated visualization of time-varying 2D and 3D vector fields by texture advection via programmable per-pixel operations. In Proceedings Workshop on Vision, Modeling, and Visualization VMV’01, 439–446. Google Scholar
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.Google Scholar