Optimization of sparse matrix-vector multiplication on emerging multicore platforms

ABSTRACT

We are witnessing a dramatic change in computer architecture due to the multicore paradigm shift, as every electronic device from cell phones to supercomputers confronts parallelism of unprecedented scale. To fully unleash the potential of these systems, the HPC community must develop multicore specific optimization methodologies for important scientific computations. In this work, we examine sparse matrix-vector multiply (SpMV) - one of the most heavily used kernels in scientific computing - across a broad spectrum of multicore designs. Our experimental platform includes the homogeneous AMD dual-core and Intel quad-core designs, the heterogeneous STI Cell, as well as the first scientific study of the highly multithreaded Sun Niagara2. We present several optimization strategies especially effective for the multicore environment, and demonstrate significant performance improvements compared to existing state-of-the-art serial and parallel SpMV implementations. Additionally, we present key insights into the architectural tradeoffs of leading multicore design strategies, in the context of demanding memory-bound numerical algorithms.

REFERENCES

• 1: K. Asanovic, R. Bodik, B. Catanzaro, et al. The landscape of parallel computing research: A view from Berkeley. Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley, December 2006.
• 2: D. Bailey. Little's law and high performance computing. In RNR Technical Report, 1997.
• 3: Satish Balay , William D. Gropp , Lois Curfman McInnes , Barry F. Smith, Efficient management of parallelism in object-oriented numerical software libraries, Modern software tools for scientific computing, Birkhauser Boston Inc., Cambridge, MA, 1997
• 4: Guy E. Blelloch , Michael A. Heroux , Marco Zagha, Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors, Carnegie Mellon University, Pittsburgh, PA, 1993
• 5: Shekhar Borkar, Design Challenges of Technology Scaling, IEEE Micro, v.19 n.4, p.23-29, July 1999 [doi>10.1109/40.782564]
• 6: R. Geus and S. Röllin. Towards a fast parallel sparse matrix-vector multiplication. In E. H. D'Hollander, J. R. Joubert, F. J. Peters, and H. Sips, editors, Proceedings of the International Conference on Parallel Computing (ParCo), pages 308--315. Imperial College Press, 1999.
• 7: Michael Gschwind, Chip multiprocessing and the cell broadband engine, Proceedings of the 3rd conference on Computing frontiers, p.1-8, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128023]
• 8: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 9: John L. Hennessy , David A. Patterson, Computer Architecture, Fourth Edition: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2006
• 10: 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]
• 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: J. Mellor-Crummey and J. Garvin. Optimizing sparse matrix vector multiply using unroll-and-jam. In Proc. LACSI Symposium, Santa Fe, NM, USA, October 2002.
• 13: Rajesh Nishtala , Richard W. Vuduc , James W. Demmel , Katherine A. Yelick, When cache blocking of sparse matrix vector multiply works and why, Applicable Algebra in Engineering, Communication and Computing, v.18 n.3, p.297-311, May 2007 [doi>10.1007/s00200-007-0038-9]
• 14: 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]
• 15: 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.
• 16: 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
• 17: S. Toledo. Improving memory-system performance of sparse matrix-vector multiplication. In Eighth SIAM Conference on Parallel Processing for Scientific Computing, March 1997.
• 18: Brendan Vastenhouw , Rob H. Bisseling, A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication, SIAM Review, v.47 n.1, p.67-95, 2005 [doi>10.1137/S0036144502409019]
• 19: Richard Wilson Vuduc , James W. Demmel, Automatic performance tuning of sparse matrix kernels, University of California, Berkeley, 2003
• 20: R. Vuduc, J. W. Demmel, and K. A. Yelick. OSKI: A library of automatically tuned sparse matrix kernels. In Proc. SciDAC 2005, Journal of Physics: Conference Series, San Francisco, CA, June 2005.
• 21: R. Vuduc, A. Gyulassy, J. W. Demmel, and K. A. Yelick. Memory hierarchy optimizations and bounds for sparse A^TAx. In Proceedings of the ICCS Workshop on Parallel Linear Algebra, volume LNCS, Melbourne, Australia, June 2003. Springer.
• 22: 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, New York, USA, June 2002.
• 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: J. W. Willenbring, A. A. Anda, and M. Heroux. Improving sparse matrix-vector product kernel performance and availabillity. In Proc. Midwest Instruction and Computing Symposium, Mt. Pleasant, IA, 2006.
• 25: Samuel Williams , John Shalf , Leonid Oliker , Shoaib Kamil , Parry Husbands , Katherine Yelick, Scientific computing Kernels on the cell processor, International Journal of Parallel Programming, v.35 n.3, p.263-298, June 2007 [doi>10.1017/s10766-007-0034-5]