Sparse matrix computations on manycore GPU's

ABSTRACT

Modern microprocessors are becoming increasingly parallel devices, and GPUs are at the leading edge of this trend. Designing parallel algorithms for manycore chips like the GPU can present interesting challenges, particularly for computations on sparse data structures. One particularly common example is the collection of sparse matrix solvers and combinatorial graph algorithms that form the core of many physical simulation techniques. Although seemingly irregular, these operations can often be implemented with data parallel operations that map very well to massively parallel processors.

REFERENCES

• 1: P. Alliez, G. Ucelli, C. Gotsman, and M. Attene. Recent advances in remeshing of surfaces. In L. D. Floriani and M. Spagnulo, editors, Shape Analysis and Structuring, pages 53--82. Springer, 2007.
• 2: A.-L. Barabási and E. Bonabeau. Scale-free networks. Scientific American, 288:60--69, 2003.
• 3: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: CUDPP: CUDA data parallel primitives library. http://www.gpgpu.org/developer/cudpp/.
• 6: G. H. Golub and C. F. V. Loan. Matrix Computations. Johns Hopkins Univ. Press, Baltimore, Third edition, 1996.
• 7: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• 8: Erik Lindholm , John Nickolls , Stuart Oberman , John Montrym, NVIDIA Tesla: A Unified Graphics and Computing Architecture, IEEE Micro, v.28 n.2, p.39-55, March 2008 [doi>10.1109/MM.2008.31]
• 9: M. E. J. Newman. The structure and function of complex networks. In SIAM Review, volume 45, pages 167--256, 2003.
• 10: John Nickolls , Ian Buck , Michael Garland , Kevin Skadron, Scalable parallel programming with CUDA, Queue, v.6 n.2, March/April 2008 [doi>10.1145/1365490.1365500]
• 11: NVIDIA Corporation. NVIDIA CUDA Programming Guide, Nov. 2007. Version 1.1.
• 12: Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
• 13: J. A. Stratton, S. S. Stone, and W. W. Hwu. M-CUDA: An efficient implementation of CUDA kernels on multi-cores. IMPACT Technical Report IMPACT-08-01, UIUC, Feb. 2008.
• 14: Samuel Williams , Leonid Oliker , Richard Vuduc , John Shalf , Katherine Yelick , James Demmel, Optimization of sparse matrix-vector multiplication on emerging multicore platforms, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362674]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms

Keywords:
GPU computing, data-parallel algorithms, parallel programming, shortest path algorithms, sparse matrix-vector multiplication