Auto-tuning of Sparse Matrix-Vector Multiplication on Graphics Processors

We present a heuristics-based auto-tuner for sparse matrixvector multiplication (SpMV) on GPUs. For a given sparse matrix, our framework delivers a high performance SpMV kernel which combines the use of the most effective storage format and tuned parameters of the corresponding code targeting the underlying GPU architecture. 250 matrices from 23 application areas are used to develop heuristics which prune the auto-tuning search space. For performance evaluation, we use 59 matrices from 12 application areas and different NVIDIA GPUs. The maximum speedup of our framework delivered kernels over NVIDIA library kernels is 7x. For most matrices, the performance of the kernels delivered by our framework is within 1% of the kernels found using exhaustive search. Compared to exhaustive search auto-tuning, our framework can be more than one order of magnitude faster.