Lsrb-Csr: A Low Overhead Storage Format For Spmv On The Gpu Systems

Keywords

CSR; GPU; LSRB-CSR; Sparse Matrices; SpMV

Abstract

Sparse matrix vector multiplication (SpMV) is a basic building block of many scientific applications. Several GPU accelerated SpMV algorithms for the CSR format suffer from workload unbalance for irregular matrices. In this paper, we propose a new auxiliary array assisted CSR format called local segmented reduction based CSR (LSRB-CSR), which enables synchronization free preprocessing and efficient SpMV algorithm with the light weight auxiliary arrays. It is efficient for both regular matrices and irregular matrices with tiny preprocessing overhead. We compare our LSRB-CSR based SpMV algorithm with the CSR-based SpMV from cuSPARSE, the SpMV algorithm based on segmented reduction adopted by CUDPP library, and the CSR5-based SpMV algorithm for both regular and irregular sparse matrices. Compared to cuSparse, our LSRB-CSR based SpMV algorithm could improve the performance by 26% on regular matrices and up to 4750% on irregular matrices. Compared to CUDPP, our LSRB-CSR based SpMV algorithm could improve the average SpMV performance by 210% on regular matrices and 250% on irregular matrices. Our LSRB-CSR based SpMV algorithm has comparable performance as the CSR5 based SpMV algorithm for regular matrices, and achieves better performance over the CSR5 based SpMV algorithm for irregular matrices. Experimental results show that the conversion overhead from the CSR to the LSRB-CSR is only 1/10 of the overhead from the CSR to the CSR5 on average.

Publication Date

1-15-2016

Publication Title

Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS

Volume

2016-January

Number of Pages

733-741

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ICPADS.2015.97

Socpus ID

84964690831 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84964690831

This document is currently not available here.

Share

COinS