Performance-Aware Model for Sparse Matrix-Matrix Multiplication on the Sunway TaihuLight Supercomputer
- 19 September 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 30 (4) , 923-938
Abstract
General sparse matrix-sparse matrix multiplication (SpGEMM) is one of the fundamental linear operations in a wide variety of scientific applications. To implement efficient SpGEMM for many large-scale applications, this paper proposes scalable and optimized SpGEMM kernels based on COO, CSR, ELL, and CSC formats on the Sunway TaihuLight supercomputer. First, a multi-level parallelism design for SpGEMM is proposed to exploit the parallelism of over 10 millions cores and better control memory based on the special Sunway architecture. Optimization strategies, such as load balance, coalesced DMA transmission, data reuse, vectorized computation, and parallel pipeline processing, are applied to further optimize performance of SpGEMM kernels. Second, we thoroughly analyze the performance of the proposed SpGEMM kernels. Third, a performance-aware model for SpGEMM is proposed to select the most appropriate compressed storage formats for the sparse matrices that can achieve the optimal performance of SpGEMM on the Sunway. The experimental results show the SpGEMM kernels have good scalability and meet the challenge of the high-speed computing of large-scale data sets on the Sunway. In addition, the performance-aware model for SpGEMM achieves an absolute value of relative error rate of 8.31% on average when the kernels are executed in one single process and achieves 8.59% on average when the kernels are executed in multiple processes. It is proved that the proposed performance-aware model can perform at high accuracy and satisfies the precision of selecting the best formats for SpGEMM on the Sunway TaihuLight supercomputer.Keywords
Funding Information
- National Key R&D Program of China (2016YFB0200201)
- National Natural Science Foundation of China (61625202)
- National Natural Science Foundation of China (61661146006, 61860206011)
- National Natural Science Foundation of China (61751204, 61806077)
This publication has 31 references indexed in Scilit:
- Evaluation Criteria for Sparse Matrix Storage FormatsIEEE Transactions on Parallel and Distributed Systems, 2015
- GPU-Accelerated Sparse Matrix-Matrix Multiplication by Iterative Row MergingSIAM Journal on Scientific Computing, 2015
- Performance Optimization Using Partitioned SpMV on GPUs and Multicore CPUsIEEE Transactions on Computers, 2014
- Sparse Matrix Multiplication On An Associative ProcessorIEEE Transactions on Parallel and Distributed Systems, 2014
- Simultaneous Input and Output Matrix Partitioning for Outer-Product--Parallel Sparse Matrix-Matrix MultiplicationSIAM Journal on Scientific Computing, 2014
- A Performance Modeling and Optimization Analysis Tool for Sparse Matrix-Vector Multiplication on GPUsIEEE Transactions on Parallel and Distributed Systems, 2013
- Exposing Fine-Grained Parallelism in Algebraic Multigrid MethodsSIAM Journal on Scientific Computing, 2012
- Finding heaviest H -subgraphs in real weighted graphs, with applicationsACM Transactions on Algorithms, 2010
- More Algorithms for All-Pairs Shortest Paths in Weighted GraphsSIAM Journal on Computing, 2010
- Block s‐step Krylov iterative methodsNumerical Linear Algebra with Applications, 2009