Fast Sparse Matrix Multiplication on GPU
Brno University of Technology, Faculty of Information Technology, Bozetechova 2, 612 66 Brno, Czech Republic
23rd High Performance Computing Symposia (HPC’15), 2015
@inproceedings{polok2015fast,
title={Fast Sparse Matrix Multiplication on GPU},
author={Polok, Luk{‘a}{v{s}} and Ila, S Viorela and Smr{v{z}}, Pavel},
booktitle={Proceedings of the 23rd High Performance Computing Symposia},
pages={1–8},
year={2015},
organization={Association for Computing Machinery}
}
Sparse matrix multiplication is an important algorithm in a wide variety of problems, including graph algorithms, simulations and linear solving to name a few. Yet, there are but a few works related to acceleration of sparse matrix multiplication on a GPU. We present a fast, novel algorithm for sparse matrix multiplication, outperforming the previous algorithm on GPU up to 3x and CPU up to 30x. The principal improvements include more efficient load balancing strategy, and a faster sorting algorithm. The main contribution is design and implementation of efficient sparse matrix multiplication algorithm and extending it to sparse block matrices, which is to our best knowledge the first implementation of this kind.
March 18, 2015 by hgpu
