Optimizing Sparse Matrix-Vector Multiplication for Large-Scale Data Analytics
Authors:
Open Access
- 1 June 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-12
Abstract
Sparse Matrix-Vector multiplication (SpMV) is a fundamental kernel, used by a large class of numerical algorithms. Emerging big-data and machine learning applications are propelling a renewed interest in SpMV algorithms that can tackle massive amount of unstructured data---rapidly approaching the TeraByte range---with predictable, high performance. In this paper we describe a new methodology to design SpMV algorithms for shared memory multiprocessors (SMPs) that organizes the original SpMV algorithm into two distinct phases. In the first phase we build a scaled matrix, that is reduced in the second phase, providing numerous opportunities to exploit memory locality. Using this methodology, we have designed two algorithms. Our experiments on irregular big-data matrices (an order of magnitude larger than the current state of the art) show a quasi-optimal scaling on a large-scale POWER8 SMP system, with an average performance speedup of 3.8x, when compared to an equally optimized version of the CSR algorithm. In terms of absolute performance, with our implementation, the POWER8 SMP system is comparable to a 256-node cluster. In terms of size, it can process matrices with up to 68 billion edges, an order of magnitude larger than state-of-the-art clusters.Keywords
This publication has 26 references indexed in Scilit:
- Hypergraph Partitioning Based Models and Methods for Exploiting Cache Locality in Sparse Matrix-Vector MultiplicationSIAM Journal on Scientific Computing, 2013
- The Combinatorial BLAS: design, implementation, and applicationsThe International Journal of High Performance Computing Applications, 2011
- Model-driven autotuning of sparse matrix-vector multiply on GPUsACM SIGPLAN Notices, 2010
- Cache-Oblivious Sparse Matrix–Vector Multiplication by Using Sparse Matrix Partitioning MethodsSIAM Journal on Scientific Computing, 2009
- Performance evaluation of the sparse matrix-vector multiplication on modern architecturesThe Journal of Supercomputing, 2008
- Random walk with restart: fast solutions and applicationsKnowledge and Information Systems, 2007
- Structure and tie strengths in mobile communication networksProceedings of the National Academy of Sciences, 2007
- R-MAT: A Recursive Model for Graph Mining2004
- Sparsity: Optimization Framework for Sparse Matrix KernelsThe International Journal of High Performance Computing Applications, 2004
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999