Fast sparse matrix-vector multiplication on GPUs
Authors:
Open Access
- 1 January 2011
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 4 (4) , 231-242
Abstract
Scaling up the sparse matrix-vector multiplication kernel on modern Graphics Processing Units (GPU) has been at the heart of numerous studies in both academia and industry. In this article we present a novel non-parametric, self-tunable, approach to data representation for computing this kernel, particularly targeting sparse matrices representing power-law graphs. Using real web graph data, we show how our representation scheme, coupled with a novel tiling algorithm, can yield significant benefits over the current state of the art GPU efforts on a number of core data mining algorithms such as PageRank, HITS and Random Walk with Restart.Keywords
This publication has 13 references indexed in Scilit:
- Implementing sparse matrix-vector multiplication on throughput-oriented processors2009
- An analytical model for a GPU architecture with memory-level and thread-level parallelism awarenessACM SIGARCH Computer Architecture News, 2009
- Concurrent number cruncher: a GPU implementation of a general sparse linear solverInternational Journal of Parallel, Emergent and Distributed Systems, 2009
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- Random walk with restart: fast solutions and applicationsKnowledge and Information Systems, 2007
- Power laws, Pareto distributions and Zipf's lawContemporary Physics, 2005
- UbiCrawler: a scalable fully distributed Web crawlerSoftware: Practice and Experience, 2004
- Parallel Data Mining for Association Rules on Shared-Memory SystemsKnowledge and Information Systems, 2001
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998