A Recursive Algebraic Coloring Technique for Hardware-efficient Symmetric Sparse Matrix-vector Multiplication
Authors:
Top Cited Papers
Open Access
- 29 June 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 7 (3) , 1-37
Abstract
The symmetric sparse matrix-vector multiplication (SymmSpMV) is an important building block for many numerical linear algebra kernel operations or graph traversal applications. Parallelizing SymmSpMV on today’s multicore platforms with up to 100 cores is difficult due to the need to manage conflicting updates on the result vector. Coloring approaches can be used to solve this problem without data duplication, but existing coloring algorithms do not take load balancing and deep memory hierarchies into account, hampering scalability and full-chip performance. In this work, we propose the recursive algebraic coloring engine (RACE), a novel coloring algorithm and open-source library implementation that eliminates the shortcomings of previous coloring methods in terms of hardware efficiency and parallelization overhead. We describe the level construction, distance- k coloring, and load balancing steps in RACE, use it to parallelize SymmSpMV, and compare its performance on 31 sparse matrices with other state-of-the-art coloring techniques and Intel MKL on two modern multicore processors. RACE outperforms all other approaches substantially. By means of a parameterized roofline model, we analyze the SymmSpMV performance in detail and discuss outliers. While we focus on SymmSpMV in this article, our algorithm and software are applicable to any sparse matrix operation with data dependencies that can be resolved by distance-k coloring.Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (SPP1648)
This publication has 40 references indexed in Scilit:
- Parallel symmetric sparse matrix–vector product on scalar multi-core CPUsParallel Computing, 2010
- RooflineCommunications of the ACM, 2009
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- A framework for scalable greedy coloring on distributed-memory parallel computersJournal of Parallel and Distributed Computing, 2008
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005
- Sparsity: Optimization Framework for Sparse Matrix KernelsThe International Journal of High Performance Computing Applications, 2004
- A survey of graph layout problemsACM Computing Surveys, 2002
- Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplicationIEEE Transactions on Parallel and Distributed Systems, 1999
- Parallel incremental graph partitioningIEEE Transactions on Parallel and Distributed Systems, 1997
- Scalable iterative solution of sparse linear systemsParallel Computing, 1994