Acceleration of Sparse Matrix-Vector Multiplication by Region Traversal

Abstract

Sparse matrix-vector multiplication (shortly SpM×V) is one of most common subroutines in numerical linear algebra. The problem is that the memory access patterns during SpM×V are irregular, and utilization of the cache can suffer from low spatial or temporal locality. Approaches to improve the performance of SpM×V are based on matrix reordering and register blocking. These matrix transformations are designed to handle randomly occurring dense blocks in a sparse matrix. The efficiency of these transformations depends strongly on the presence of suitable blocks. The overhead of reorganization of a matrix from one format to another is often of the order of tens of executions of
SpM×V. For this reason, such a reorganization pays off only if the same matrix A is multiplied by multiple different vectors, e.g., in iterative linear solvers.
This paper introduces an unusual approach to accelerate SpM×V. This approach can be combined with other acceleration approaches and
consists of three steps:
1) dividing matrix A into non-empty regions,
2) choosing an efficient way to traverse these regions (in other words, choosing an efficient ordering of partial multiplications),
3) choosing the optimal type of storage for each region.
All these three steps are tightly coupled. The first step divides the whole matrix into smaller parts (regions) that can fit in the cache. The second step improves the locality during multiplication due to better utilization of distant references. The last step maximizes the machine computation performance of the partial multiplication for each region.
In this paper, we describe aspects of these 3 steps in more detail (including fast and time-inexpensive algorithms for all steps). Our
measurements prove that our approach gives a significant speedup for almost all matrices arising from various technical areas.