Model-driven autotuning of sparse matrix-vector multiply on GPUs
Top Cited Papers
Open Access
- 9 January 2010
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 45 (5) , 115-126
Abstract
We present a performance model-driven framework for automated performance tuning (autotuning) of sparse matrix-vector multiply (SpMV) on systems accelerated by graphics processing units (GPU). Our study consists of two parts. First, we describe several carefully hand-tuned SpMV implementations for GPUs, identifying key GPU-specific performance limitations, enhancements, and tuning opportunities. These implementations, which include variants on classical blocked compressed sparse row (BCSR) and blocked ELLPACK (BELLPACK) storage formats, match or exceed state-of-the-art implementations. For instance, our best BELLPACK implementation achieves up to 29.0 Gflop/s in single-precision and 15.7 Gflop/s in double-precision on the NVIDIA T10P multiprocessor (C1060), enhancing prior state-of-the-art unblocked implementations (Bell and Garland, 2009) by up to 1.8× and 1.5× for single-and double-precision respectively. However, achieving this level of performance requires input matrix-dependent parameter tuning. Thus, in the second part of this study, we develop a performance model that can guide tuning. Like prior autotuning models for CPUs (e.g., Im, Yelick, and Vuduc, 2004), this model requires offline measurements and run-time estimation, but more directly models the structure of multithreaded vector processors like GPUs. We show that our model can identify the implementations that achieve within 15% of those found through exhaustive search.Keywords
This publication has 12 references indexed in Scilit:
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- Is Search Really Necessary to Generate High-Performance BLAS?Proceedings of the IEEE, 2005
- Self-Adapting Linear Algebra Algorithms and SoftwareProceedings of the IEEE, 2005
- Vectorized Sparse Matrix Multiply for Compressed Row Storage FormatLecture Notes in Computer Science, 2005
- Fast Sparse Matrix-Vector Multiplication by Exploiting Variable Block Structure2005
- 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
- Sparse matrix solvers on the GPU2003
- Towards a fast parallel sparse symmetric matrix–vector multiplicationParallel Computing, 2001
- Improving performance of sparse matrix-vector multiplication1999