Analyzing and enhancing OSKI for sparse matrix-vector multiplication

Details Analyzing and enhancing OSKI for sparse matrix-vector multiplication Analyzing and enhancing OSKI for sparse matrix-vector multiplication

2012-03-13

arxiv.org/abs/1203.2739v1

Computer Science

Numerical Analysis

arXiv admin note: substantial text overlap with arXiv:1202.3856

Scientific paper

Sparse matrix-vector multiplication (SpMxV) is a kernel operation widely used in iterative linear solvers. The same sparse matrix is multiplied by a dense vector repeatedly in these solvers. Matrices with irregular sparsity patterns make it difficult to utilize cache locality effectively in SpMxV computations. In this work, we investigate single- and multiple-SpMxV frameworks for exploiting cache locality in SpMxV computations. For the single-SpMxV framework, we propose two cache-size-aware top-down row/column-reordering methods based on 1D and 2D sparse matrix partitioning by utilizing the column-net and enhancing the row-column-net hypergraph models of sparse matrices. The multiple-SpMxV framework depends on splitting a given matrix into a sum of multiple nonzero-disjoint matrices so that the SpMxV operation is performed as a sequence of multiple input- and output-dependent SpMxV operations. For an effective matrix splitting required in this framework, we propose a cache-size-aware top-down approach based on 2D sparse matrix partitioning by utilizing the row-column-net hypergraph model. The primary objective in all of the three methods is to maximize the exploitation of temporal locality. We evaluate the validity of our models and methods on a wide range of sparse matrices by performing actual runs through using OSKI. Experimental results show that proposed methods and models outperform state-of-the-art schemes.

Affiliated with

Also associated with

No associations

Rating

Analyzing and enhancing OSKI for sparse matrix-vector multiplication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analyzing and enhancing OSKI for sparse matrix-vector multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analyzing and enhancing OSKI for sparse matrix-vector multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-143772