A Work-Efficient Parallel Sparse Matrix-Sparse Vector Multiplication Algorithm
Authors:
- Ariful AzadAAAriful Azad
- Aydin BulucABAydin Buluc
- 1 May 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 688-697
Abstract
We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including breadth-first search, bipartite graph matching, and maximal independent set. As thread counts increase, existing multithreaded SpMSpV algorithms can spend more time accessing the sparse matrix data structure than doing arithmetic. Our shared-memory parallel SpMSpV algorithm is work efficient in the sense that its total work is proportional to the number of arithmetic operations required. The key insight is to avoid each thread individually scan the list of matrix columns. Our algorithm is simple to implement and operates on existing column-based sparse matrix formats. It performs well on diverse matrices and vectors with heterogeneous sparsity patterns. A high-performance implementation of the algorithm attains up to 15x speedup on a 24-core Intel Ivy Bridge processor and up to 49x speedup on a 64-core Intel KNL manycore processor. In contrast to implementations of existing algorithms, the performance of our algorithm is sustained on a variety of different input types include matrices representing scale-free and high-diameter graphs.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Optimizing Sparse Matrix-Vector Multiplication for Large-Scale Data Analytics2016
- Graph programming interface (GPI)2016
- Distributed-Memory Algorithms for Maximum Cardinality Matching in Bipartite Graphs2016
- Parallel graph analyticsCommunications of the ACM, 2016
- GraphMatProceedings of the VLDB Endowment, 2015
- Fast Sparse Matrix and Sparse Vector Multiplication Algorithm on the GPU2015
- Evaluation Criteria for Sparse Matrix Storage FormatsIEEE Transactions on Parallel and Distributed Systems, 2015
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph PartitioningSIAM Journal on Computing, 2013
- Sparse Matrices in MATLAB: Design and ImplementationSIAM Journal on Matrix Analysis and Applications, 1992
- Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted TranspositionACM Transactions on Mathematical Software, 1978