Cache-Oblivious Sparse Matrix–Vector Multiplication by Using Sparse Matrix Partitioning Methods
Authors:
- A. N. YzelmanAYA. N. Yzelman
- Rob H. BisselingRBRob H. Bisseling
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 31 (4) , 3128-3154
Abstract
In this article, we introduce a cache-oblivious method for sparse matrix–vector multiplication. Our method attempts to permute the rows and columns of the input matrix using a recursive hypergraph-based sparse matrix partitioning scheme so that the resulting matrix induces cache-friendly behavior during sparse matrix–vector multiplication. Matrices are assumed to be stored in row-major format, by means of the compressed row storage (CRS) or its variants incremental CRS and zig-zag CRS. The zig-zag CRS data structure is shown to fit well with the hypergraph metric used in partitioning sparse matrices for the purpose of parallel computation. The separated block-diagonal (SBD) form is shown to be the appropriate matrix structure for cache enhancement. We have implemented a run-time cache simulation library enabling us to analyze cache behavior for arbitrary matrices and arbitrary cache properties during matrix–vector multiplication within a k-way set-associative idealized cache model. The results of these simulations are then verified by actual experiments run on various cache architectures. In all these experiments, we use the Mondriaan sparse matrix partitioner in one-dimensional mode. The savings in computation time achieved by our matrix reorderings reach up to 50 percent, in the case of a large link matrix.Keywords
This publication has 36 references indexed in Scilit:
- A Hilbert-order multiplication scheme for unstructured sparse matricesInternational Journal of Parallel, Emergent and Distributed Systems, 2007
- Applying Automated Memory Analysis to Improve Iterative AlgorithmsSIAM Journal on Scientific Computing, 2007
- The Design and Implementation of FFTW3Proceedings of the IEEE, 2005
- Permuting Sparse Rectangular Matrices into Block-Diagonal FormSIAM Journal on Scientific Computing, 2004
- A multilevel unsymmetric matrix ordering algorithm for parallel process simulationComputers & Chemical Engineering, 2000
- Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplicationIEEE Transactions on Parallel and Distributed Systems, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Improving the Run Time and Quality of Nested Dissection OrderingSIAM Journal on Scientific Computing, 1998
- Design and implementation of a parallel unstructured Euler solver using software primitivesAIAA Journal, 1994
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973