Adaptive runtime tuning of parallel sparse matrix-vector multiplication on distributed memory systems

ABSTRACT

Sparse matrix-vector (SpMV) multiplication is a widely used kernel in scientific applications. In these applications, the SpMV multiplication is usually deeply nested within multiple loops and thus executed a large number of times. We have observed that there can be significant performance variability, due to irregular memory access patterns. Static performance optimizations are difficult because the patterns may be known only at runtime. In this paper, we propose adaptive runtime tuning mechanisms to improve the parallel performance on distributed memory systems. Our adaptive iteration-to-process mapping mechanism balances computational load at runtime with negligible overhead (1% on average), and our runtime communication selection algorithm searches for the best communication method for a given data distribution and mapping. Actual runs on 26 real matrices show that our runtime tuning system reduces execution time up to 68.8% (30.9% on average) over a base block-distributed parallel algorithm on distributed systems with 32 nodes.

REFERENCES

• 1: The message passing interface (MPI) standard {online}. available: http://www-unix.mcs.anl.gov/mpi/.
• 2: J. I. Aliaga and V. Hernandez. Symmetric sparse matrix-vector product on distributed memory multiprocessors. Conf. on Parallel Computing and Transputer Applications, 1992.
• 3: R. H. Bisseling and W. Meesen. Communication balancing in parallel sparse matrix-vector multiplication. Electronic Transactions on Numerical Analysis, 21:47--65, 2005.
• 4: E. G. Boman and U. Catalyurek. Constrained fine-grain parallel sparse matrix distribution. SIAM Workshop on Combinatorial Scientific Computing, 2007.
• 5: Umit Catalyurek , Cevdet Aykanat, Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.10 n.7, p.673-693, July 1999 [doi>10.1109/71.780863]
• 6: T. Davis. University of Florida Sparse Matrix Collection {online}. available: http://www.cise.ufl.edu/research/sparse/matrices/.
• 7: G. E. Fagg, J. Pjesivac-Grbovic, G. Bosilca, T. Angskun, J. J. Dongarra, and E. Jeannot. Flexible collective communication tuning architecture applied to Open MPI. Euro PVM/MPI, 2006.
• 8: Ahmad Faraj , Xin Yuan, Automatic generation and tuning of MPI collective communication routines, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088202]
• 9: Bruce Hendrickson , Tamara G. Kolda, Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing, SIAM Journal on Scientific Computing, v.21 n.6, p.2048-2072, Dec 1999 [doi>10.1137/S1064827598341475]
• 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: D. Jin and S. G. Ziavras. A super-programming technique for large sparse matrix multiplication on PC clusters. IEICE Trans. Inf. & Syst., E87-D(7), July 2004.
• 12: Sorin G. Nastea , Tarek El-Ghazawi, Load-Balancing in Sparse Matrix-Vector Multiplication, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.218, October 23-26, 1996
• 13: Andrew T. Ogielski , William Aiello, Sparse matrix computations on parallel processor arrays, SIAM Journal on Scientific Computing, v.14 n.3, p.519-530, May 1993 [doi>10.1137/0914033]
• 14: Chao-Wei Ou , Sanjay Ranka, Parallel Incremental Graph Partitioning, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.884-896, August 1997 [doi>10.1109/71.605773]
• 15: R. Rabenseifner. Automatic MPI counter profiling of all users: First results on a CRAY T3E 900-512. Euro PVM/MPI, pages 35--42, 1999.
• 16: Edward Rothberg , Robert Schreiber, Improved load distribution in parallel sparse Cholesky factorization, Proceedings of the 1994 conference on Supercomputing, p.783-792, December 1994, Washington, D.C., United States
• 17: R. Shahnaz, A. Usman, and I. R. Chughtai. Implementation and evaluation of parallel sparse matrix-vector products on distributed memory parallel computers. IEEE Int. Conf. on Cluster Computing, pages 1--6, 2006.
• 18: Jimmy Su , Katherine Yelick, Automatic Support for Irregular Computations in a High-Level Language, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.53.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.118]
• 19: Sathish S. Vadhiyar , Graham E. Fagg , Jack Dongarra, Automatically tuned collective communications, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.3-es, November 04-10, 2000, Dallas, Texas, United States
• 20: 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]
• 21: 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]
• 22: Louis H. Ziantz , Can C. Özturan , Boleslaw K. Szymanski, Run-Time Optimization of Sparse Matrix-Vector Multiplication on SIMD Machines, Proceedings of the 6th International PARLE Conference on Parallel Architectures and Languages Europe, p.313-322, July 04-08, 1994

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Performance

Keywords:
process mapping, runtime tuning, sparse matrix