Seyrek matris-vektor çarpımında önbellek yerellği sağlayan yöntem ve modeller

The sparse matrix-vector multiplication (SpMxV) is an important kernel operationwidely used in linear solvers. The same sparse matrix is multiplied by a dense vec-tor repeatedly in these solvers to solve a system of linear equations. High performancegains can be obtained if we can take the advantage of today?s deep cache hierarchyin SpMxV operations. Matrices with irregular sparsity patterns make it difficult toutilize data locality effectively in SpMxV computations. Different techniques are pro-posed in the literature to utilize cache hierarchy effectively via exploiting data local-ity during SpMxV. In this work, we investigate two distinct frameworks for cache-aware/oblivious SpMxV: single matrix-vector multiply and multiple submatrix-vectormultiplies. For the single matrix-vector multiply framework, we propose a cache-sizeaware top-down row/column-reordering approach based on 1D sparse matrix parti-tioning by utilizing the recently proposed appropriate hypergraph models of sparsematrices, and a cache oblivious bottom-up approach based on hierarchical clusteringof rows/columns with similar sparsity patterns. We also propose a column compres-sion scheme as a preprocessing step which makes these two approaches cache-line-sizeaware. The multiple submatrix-vector multiplies framework depends on the partition-ing the matrix into multiple nonzero-disjoint submatrices. For an effective matrix-to-submatrix partitioning required in this framework, we propose a cache-size awaretop-down approach based on 2D sparse matrix partitioning by utilizing the recentlyproposed fine-grain hypergraph model. For this framework, we also propose a trav-eling salesman formulation for an effective ordering of individual submatrix-vectormultiply operations. We evaluate the validity of our models and methods on a widerange of sparse matrices. Experimental results show that proposed methods and mod-els outperforms state-of-the-art schemes.