Implementing Sparse Matrix-vector Multiplication on Throughput-oriented Processors
N. Bell, and M. Garland. Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, page 18:1--18:11. New York, NY, USA, ACM, (2009)
DOI: 10.1145/1654059.1654078
Abstract
Sparse matrix-vector multiplication (SpMV) is of singular importance in sparse linear algebra. In contrast to the uniform regularity of dense linear algebra, sparse operations encounter a broad spectrum of matrices ranging from the regular to the highly irregular. Harnessing the tremendous potential of throughput-oriented processors for sparse operations requires that we expose substantial fine-grained parallelism and impose sufficient regularity on execution paths and memory access patterns. We explore SpMV methods that are well-suited to throughput-oriented architectures like the GPU and which exploit several common sparsity classes. The techniques we propose are efficient, successfully utilizing large percentages of peak bandwidth. Furthermore, they deliver excellent total throughput, averaging 16 GFLOP/s and 10 GFLOP/s in double precision for structured grid and unstructured mesh matrices, respectively, on a GeForce GTX 285. This is roughly 2.8 times the throughput previously achieved on Cell BE and more than 10 times that of a quad-core Intel Clovertown system.
Description
Implementing sparse matrix-vector multiplication on throughput-oriented processors
%0 Conference Paper
%1 Bell:2009:ISM:1654059.1654078
%A Bell, Nathan
%A Garland, Michael
%B Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis
%C New York, NY, USA
%D 2009
%I ACM
%K format matrix_vector_mult nvidia performance sparse sparsity
%P 18:1--18:11
%R 10.1145/1654059.1654078
%T Implementing Sparse Matrix-vector Multiplication on Throughput-oriented Processors
%U http://doi.acm.org/10.1145/1654059.1654078
%X Sparse matrix-vector multiplication (SpMV) is of singular importance in sparse linear algebra. In contrast to the uniform regularity of dense linear algebra, sparse operations encounter a broad spectrum of matrices ranging from the regular to the highly irregular. Harnessing the tremendous potential of throughput-oriented processors for sparse operations requires that we expose substantial fine-grained parallelism and impose sufficient regularity on execution paths and memory access patterns. We explore SpMV methods that are well-suited to throughput-oriented architectures like the GPU and which exploit several common sparsity classes. The techniques we propose are efficient, successfully utilizing large percentages of peak bandwidth. Furthermore, they deliver excellent total throughput, averaging 16 GFLOP/s and 10 GFLOP/s in double precision for structured grid and unstructured mesh matrices, respectively, on a GeForce GTX 285. This is roughly 2.8 times the throughput previously achieved on Cell BE and more than 10 times that of a quad-core Intel Clovertown system.
%@ 978-1-60558-744-8
@inproceedings{Bell:2009:ISM:1654059.1654078,
abstract = {Sparse matrix-vector multiplication (SpMV) is of singular importance in sparse linear algebra. In contrast to the uniform regularity of dense linear algebra, sparse operations encounter a broad spectrum of matrices ranging from the regular to the highly irregular. Harnessing the tremendous potential of throughput-oriented processors for sparse operations requires that we expose substantial fine-grained parallelism and impose sufficient regularity on execution paths and memory access patterns. We explore SpMV methods that are well-suited to throughput-oriented architectures like the GPU and which exploit several common sparsity classes. The techniques we propose are efficient, successfully utilizing large percentages of peak bandwidth. Furthermore, they deliver excellent total throughput, averaging 16 GFLOP/s and 10 GFLOP/s in double precision for structured grid and unstructured mesh matrices, respectively, on a GeForce GTX 285. This is roughly 2.8 times the throughput previously achieved on Cell BE and more than 10 times that of a quad-core Intel Clovertown system.},
acmid = {1654078},
added-at = {2018-06-12T16:09:16.000+0200},
address = {New York, NY, USA},
articleno = {18},
author = {Bell, Nathan and Garland, Michael},
biburl = {https://www.bibsonomy.org/bibtex/27b550f48a479f4782d7d42552a24bf11/loroch},
booktitle = {Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis},
description = {Implementing sparse matrix-vector multiplication on throughput-oriented processors},
doi = {10.1145/1654059.1654078},
interhash = {953c74dc2969078443668fdc5b64dd71},
intrahash = {7b550f48a479f4782d7d42552a24bf11},
isbn = {978-1-60558-744-8},
keywords = {format matrix_vector_mult nvidia performance sparse sparsity},
location = {Portland, Oregon},
numpages = {11},
pages = {18:1--18:11},
publisher = {ACM},
series = {SC '09},
timestamp = {2018-06-16T10:46:03.000+0200},
title = {Implementing Sparse Matrix-vector Multiplication on Throughput-oriented Processors},
url = {http://doi.acm.org/10.1145/1654059.1654078},
year = 2009
}