Optimizing sparse matrix-vector multiplication using index and value compression

ABSTRACT

Previous research work has identified memory bandwidth as the main bottleneck of the ubiquitous Sparse Matrix-Vector Multiplication kernel. To attack this problem, we aim at reducing the overall data volume of the algorithm. Typical sparse matrix representation schemes store only the non-zero elements of the matrix and employ additional indexing information to properly iterate over these elements. In this paper we propose two distinct compression methods targeting index and numerical values respectively. We perform a set of experiments on a large real-world matrix set and demonstrate that the index compression method can be applied successfully to a wide range of matrices. Moreover, the value compression method is able to achieve impressive speedups in a more limited yet important class of sparse matrices that contain a small number of distinct values

REFERENCES

• 1: W. K. Anderson , W. D. Gropp , D. K. Kaushik , D. E. Keyes , B. F. Smith, Achieving high sustained performance in an unstructured mesh CFD application, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.69-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331600]
• 2: R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. M. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia, 1994.
• 3: Martin Burtscher , Paruj Ratanaworabhan, High Throughput Compression of Double-Precision Floating-Point Data, Proceedings of the 2007 Data Compression Conference, p.293-302, March 27-29, 2007 [doi>10.1109/DCC.2007.44]
• 4: T. Davis. University of Florida sparse matrix collection. NA Digest, 97(23):7, 1997.
• 5: 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]
• 6: Eun-Jin Im , Katherine A. Yelick, Optimizing the performance of sparse matrix-vector multiplication, University of California, Berkeley, 2000
• 7: E. Im and K. Yelick. Optimizing sparse matrix-vector multiplication on SMPs. In 9th SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Mar. 1999.
• 8: 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
• 9: D. Keyes. Four Horizons for Enhancing the Performance of Parallel Simulations Based on Partial Differential Equations. Springer, 2000.
• 10: Julie Langou , Julien Langou , Piotr Luszczek , Jakub Kurzak , Alfredo Buttari , Jack Dongarra, Exploiting the performance of 32 bit floating point arithmetic in obtaining 64 bit accuracy (revisiting iterative refinement for linear systems), Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188573]
• 11: 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]
• 12: 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]
• 13: J. C. Pichel, D. B. Heras, J. C. Cabaleiro, and F. F. Rivera. Improving the locality of the sparse matrix-vector product on shared memory multiprocessors. In PDP, pages 66--71. IEEE Computer Society, 2004.
• 14: J. C. Pichel , D. B. Heras , J. C. Cabaleiro , F. F. Rivera, Performance optimization of irregular codes based on the combination of reordering and blocking techniques, Parallel Computing, v.31 n.8+9, p.858-876, August 2005 [doi>10.1016/j.parco.2005.04.012]
• 15: 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]
• 16: Y. Saad. SPARSKIT: A basic tool kit for sparse matrix computations. Technical report, Computer Science Department, University of Minnesota, Minneapolis, MN 55455, June 1994. Version 2.
• 17: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 18: Malik Silva, Sparse matrix storage revisited, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy [doi>10.1145/1062261.1062299]
• 19: 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
• 20: Richard Vuduc , James W. Demmel , Katherine A. Yelick , Shoaib Kamil , Rajesh Nishtala , Benjamin Lee, Performance optimizations and bounds for sparse matrix-vector multiply, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-35, November 16, 2002, Baltimore, Maryland
• 21: R. W. Vuduc and H. Moon. Fast sparse matrix-vector multiplication by exploiting variable block structure. In High Performance Computing and Communications, volume 3726 of Lecture Notes in Computer Science, pages 807--816. Springer, 2005.
• 22: 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
• 23: 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]
• 24: 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:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Experimentation, Measurement, Performance

Keywords:
data compression, memory bandwidth, sparse matrix