Title: Two-dimensional cache-oblivious sparse matrix-vector multiplication
Authors: Yzelman, Albert-Jan # ×
Bisseling, Rob H #
Issue Date: 2011
Publisher: North-Holland
Series Title: Parallel Computing vol:37 issue:12 pages:806-819
Conference: 6th International Workshop on Parallel Matrix Algorithms & Applications (PMAA) location:Basel: SWITZERLAND date:JUN 30-JUL 02, 2010
Abstract: In earlier work, we presented a one-dimensional cache-oblivious sparse matrix–vector (SpMV) multiplication scheme which has its roots in one-dimensional sparse matrix partitioning. Partitioning is often used in distributed-memory parallel computing for the SpMV multiplication, an important kernel in many applications. A logical extension is to move towards using a two-dimensional partitioning. In this paper, we present our research in this direction, extending the one-dimensional method for cache-oblivious SpMV multiplication to two dimensions, while still allowing only row and column permutations on the sparse input matrix. This extension requires a generalisation of the compressed row storage data structure to a block-based data structure, for which several variants are investigated. Experiments performed on three different architectures show further improvements of the two-dimensional method compared to the one-dimensional method, especially in those cases where the one-dimensional method already provided significant gains. The largest gain obtained by our new reordering is over a factor of 3 in SpMV speed, compared to the natural matrix ordering.
ISSN: 0167-8191
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Non-KU Leuven Association publications
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
yzelman11a-rev.pdfOA article Published 249KbAdobe PDFView/Open
yzelman11a-pp.pdfPreprint Published 222KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science