Pattern-based sparse matrix representation for memory-efficient SMVM kernels

ABSTRACT

Pattern-based Representation (PBR) is a novel approach to improving the performance of Sparse Matrix-Vector Multiply (SMVM) numerical kernels. Motivated by our observation that many matrices can be divided into blocks that share a small number of distinct patterns, we generate custom multiplication kernels for frequently recurring block patterns. The resulting reduction in index overhead significantly reduces memory bandwidth requirements and improves performance. Unlike existing methods, PBR requires neither detection of dense blocks nor zero filling, making it particularly advantageous for matrices that lack dense nonzero concentrations. SMVM kernels for PBR can benefit from explicit prefetching and vectorization, and are amenable to parallelization. We present sequential and parallel performance results for PBR on two current multicore architectures, which show that PBR outperforms available alternatives for the matrices to which it is applicable.

REFERENCES

• 1: R. C. Agarwal , F. G. Gustavson , M. Zubair, A high performance algorithm using pre-processing for the sparse matrix-vector multiplication, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.32-41, November 16-20, 1992, Minneapolis, Minnesota, United States
• 2: A. Antoulas, D. Sorensen, and S. Gugercin. A survey of model reduction methods for large-scale systems. In Structured Matrices in Operator Theory, Numerical Analysis, Control, Signal and Image Processing, Contemporary Mathematics, number 280, pages 193--219. AMS Publications, 2001.
• 3: C. Beattie and S. Gugercin. Inexact solves in krylov-based model reduction. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 3405--3411, December 2006.
• 4: Aart J. C. Bik , Harry A. G. Wijshoff, Compilation techniques for sparse matrix computations, Proceedings of the 7th international conference on Supercomputing, p.416-424, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.166023]
• 5: Guy E. Blelloch , Michael A. Heroux , Marco Zagha, Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors, Carnegie Mellon University, Pittsburgh, PA, 1993
• 6: T. Davis. The University of Florida sparse matrix collection. http://www.cise.u .edu/research/sparse/matrices.
• 7: E. F. D'Azevedo, M. R. Fahey, and R. T. Mills. Vectorized sparse matrix multiply for compressed row storage format. In International Conference on Computational Science, May 2005.
• 8: Y. Fukui , H. Yoshida , S. Higono, Supercomputing of circuits simulation, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.81-85, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76272]
• 9: Roman Geus , Stefan Röllin, Towards a fast parallel sparse symmetric matrix-vector multiplication, Parallel Computing, v.27 n.7, p.883-896, June 2001 [doi>10.1016/S0167-8191(01)00073-4]
• 10: T. Gneiting and A. E. Raftery. Weather forecasting with ensemble methods. Science (Washington, D.C.), 310(5746):248, 2005.
• 11: Georgios Goumas , Kornilios Kourtis , Nikos Anastopoulos , Vasileios Karakasis , Nectarios Koziris, Understanding the Performance of Sparse Matrix-Vector Multiplication, Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008), p.283-292, February 13-15, 2008 [doi>10.1109/PDP.2008.41]
• 12: F. G. Gustavson , W. Liniger , R. Willoughby, Symbolic Generation of an Optimal Crout Algorithm for Sparse Systems of Linear Equations, Journal of the ACM (JACM), v.17 n.1, p.87-109, Jan. 1970 [doi>10.1145/321556.321565]
• 13: Eun-Jin Im , Katherine A. Yelick, Optimizing Sparse Matrix Computations for Register Reuse in SPARSITY, Proceedings of the International Conference on Computational Sciences-Part I, p.127-136, May 28-30, 2001
• 14: Eun-Jin Im , Katherine Yelick , Richard Vuduc, Sparsity: Optimization Framework for Sparse Matrix Kernels, International Journal of High Performance Computing Applications, v.18 n.1, p.135-158, February 2004 [doi>10.1177/1094342004041296]
• 15: James B. White, III , P. Sadayappan, On Improving the Performance of Sparse Matrix-Vector Multiplication, Proceedings of the Fourth International Conference on High-Performance Computing, p.66, December 18-21, 1997
• 16: Kornilios Kourtis , Georgios Goumas , Nectarios Koziris, Optimizing sparse matrix-vector multiplication using index and value compression, Proceedings of the 5th conference on Computing frontiers, May 05-07, 2008, Ischia, Italy [doi>10.1145/1366230.1366244]
• 17: Benjamin C. Lee , Richard W. Vuduc , James W. Demmel , Katherine A. Yelick, Performance Models for Evaluation and Automatic Tuning of Symmetric Sparse Matrix-Vector Multiply, Proceedings of the 2004 International Conference on Parallel Processing, p.169-176, August 15-18, 2004 [doi>10.1109/ICPP.2004.58]
• 18: J. D. McCalpin. Memory bandwidth and machine balance in current high performance computers. IEEE Computer Society Technical Committee on Computer Architecture (TCCA) Newsletter, pages 19--25, Dec. 1995.
• 19: John Mellor-Crummey , John Garvin, Optimizing Sparse Matrix-Vector Product Computations Using Unroll and Jam, International Journal of High Performance Computing Applications, v.18 n.2, p.225-236, May 2004 [doi>10.1177/1094342004038951]
• 20: H. Merlitz, T. Herges, and W. Wenzel. Fluctuation analysis and accuracy of a large-scale in silico screen. Journal of Computational Chemistry, 25(13):1568, October 2004.
• 21: H. Meuer, E. Strohmaier, J. Dongarra, and H. Simon. Top500 supercomputing sites, Nov. 2008. http://www.top500.org/.
• 22: R. Nishtala, R. Vuduc, J. Demmel, and K. Yelick. Performance modeling and analysis of cache blocking in sparse matrix vector multiply. Technical report, Berkeley, EECS Dept., 2004.
• 23: R. Nishtala, R. Vuduc, J. W. Demmel, and K. A. Yelick. When cache blocking sparse matrix vector multiply works and why. In Proceedings of the PARA'04: Workshop on the State-of-the-art in Scientific Computing, 2004.
• 24: S. C. Park , J. P. Draayer , S.-Q. Zheng, An efficient algorithm for sparse matrix computations, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.919-926, March 1992, Kansas City, Missouri, United States [doi>10.1145/130069.130108]
• 25: Ali Pinar , Michael T. Heath, Improving performance of sparse matrix-vector multiplication, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.30-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331562]
• 26: D. J. Rose. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory and Computing, pages 183--217, 1973.
• 27: O. Temam , W. Jalby, Characterizing the behavior of sparse algorithms on caches, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.578-587, November 16-20, 1992, Minneapolis, Minnesota, United States
• 28: S. Toledo, Improving the memory-system performance of sparse-matrix vector multiplication, IBM Journal of Research and Development, v.41 n.6, p.711-726, Nov. 1997
• 29: Richard Wilson Vuduc , James W. Demmel, Automatic performance tuning of sparse matrix kernels, University of California, Berkeley, 2003
• 30: R. Vuduc, J. W. Demmel, and K. A. Yelick. OSKI: A library of automatically tuned sparse matrix kernels. In Proceedings of SciDAC 2005, Journal of Physics: Conference Series, San Francisco, CA, USA, June 2005. Institute of Physics Publishing.
• 31: R. Vuduc, S. Kamil, J. Hsu, R. Nishtala, J. W. Demmel, and K. A. Yelick. Automatic performance tuning and analysis of sparse triangular solve. In ICS 2002: Workshop on Performance Optimization via High-Level Languages and Libraries, 2002.
• 32: R. W. Vuduc and H.-J. Moon. Fast sparse matrix-vector multiplication by exploiting variable block structure. In High Performance Computing and Communcations, volume 3726 of Lecture Notes in Computer Science, pages 807--816. Springer, 2005. Editors: Laurence Tianruo Yang and Omer F. Rana and Beniamino Di Martino and Jack Dongarra.
• 33: Jeremiah Willcock , Andrew Lumsdaine, Accelerating sparse matrix computations via data compression, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183444]
• 34: 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]
• 35: Wm. A. Wulf , Sally A. McKee, Hitting the memory wall: implications of the obvious, ACM SIGARCH Computer Architecture News, v.23 n.1, p.20-24, March 1995 [doi>10.1145/216585.216588]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance

Keywords:
bcoo, bcsr, csr, iterative solvers, matrix splitting, memory bandwidth, pbr, prefetching, smvm, sparse computations, spmv, vectorization