2012/02/17 by Kadir Akbudak, Akbudak, Kadir, Enver Kayaaslan +3 · 1 citation
Computer Science · #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Parallel Computing and Optimization Techniques #Performance (cs.PF)
paper · pdf · doi:10.48550/arxiv.1202.3856
openalex publication_date 2012/02/17 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
The sparse matrix-vector multiplication (SpMxV) is a kernel operation widely\nused in iterative linear solvers. The same sparse matrix is multiplied by a\ndense vector repeatedly in these solvers. Matrices with irregular sparsity\npatterns make it difficult to utilize cache locality effectively in SpMxV\ncomputations. In this work, we investigate single- and multiple-SpMxV\nframeworks for exploiting cache locality in SpMxV computations. For the\nsingle-SpMxV framework, we propose two cache-size-aware top-down\nrow/column-reordering methods based on 1D and 2D sparse matrix partitioning by\nutilizing the column-net and enhancing the row-column-net hypergraph models of\nsparse matrices. The multiple-SpMxV framework depends on splitting a given\nmatrix into a sum of multiple nonzero-disjoint matrices so that the SpMxV\noperation is performed as a sequence of multiple input- and output- dependent\nSpMxV operations. For an effective matrix splitting required in this framework,\nwe propose a cache- size-aware top-down approach based on 2D sparse matrix\npartitioning by utilizing the row-column-net hypergraph model. For this\nframework, we also propose two methods for effective ordering of individual\nSpMxV operations. The primary objective in all of the three methods is to\nmaximize the exploitation of temporal locality. We evaluate the validity of our\nmodels and methods on a wide range of sparse matrices using both cache-miss\nsimulations and actual runs by using OSKI. Experimental results show that\nproposed methods and models outperform state-of-the-art schemes.\n