DocumentCode :
1858741
Title :
Accelerating Sparse Matrix Vector Multiplication in Iterative Methods Using GPU
Author :
Matam, Kiran Kumar ; Kothapalli, Kishore
Author_Institution :
CSTAR, IIIT-Hyderabad, Hyderabad, India
fYear :
2011
fDate :
13-16 Sept. 2011
Firstpage :
612
Lastpage :
621
Abstract :
Multiplying a sparse matrix with a vector (spmv for short) is a fundamental operation in many linear algebra kernels. Having an efficient spmv kernel on modern architectures such as the GPUs is therefore of principal interest. The computational challenges that spmv poses are significantlydifferent compared to that of the dense linear algebra kernels. Recent work in this direction has focused on designing data structures to represent sparse matrices so as to improve theefficiency of spmv kernels. However, as the nature of sparseness differs across sparse matrices, there is no clear answer as to which data structure to use given a sparse matrix. In this work, we address this problem by devising techniques to understand the nature of the sparse matrix and then choose appropriate data structures accordingly. By using our technique, we are able to improve the performance of the spmv kernel on an Nvidia Tesla GPU (C1060) by a factor of up to80% in some instances, and about 25% on average compared to the best results of Bell and Garland [3] on the standard dataset (cf. Williams et al. SC´07) used in recent literature. We also use our spmv in the conjugate gradient method and show an average 20% improvement compared to using HYB spmv of [3], on the dataset obtained from the The University of Florida Sparse Matrix Collection [9].
Keywords :
computer graphic equipment; coprocessors; iterative methods; mathematics computing; matrix multiplication; Nvidia Tesla GPU; data structure; graphics processing unit; iterative method; linear algebra kernel; sparse matrix vector multiplication; Data structures; Graphics processing unit; Instruction sets; Kernel; Optimization; Sparse matrices; GPGPU; Iterative Methods; Sparse Matrix Vector Multiplication;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing (ICPP), 2011 International Conference on
Conference_Location :
Taipei City
ISSN :
0190-3918
Print_ISBN :
978-1-4577-1336-1
Electronic_ISBN :
0190-3918
Type :
conf
DOI :
10.1109/ICPP.2011.82
Filename :
6047229
Link To Document :
بازگشت