A Locality-Activated Matrix Reordering Framework for SpMV

Sparse Matrix-Vector Multiplication (SpMV) is a fundamental kernel in many scientific and graph applications, and its performance is often limited by the poor locality of input-vector accesses. Matrix reordering is an efficient approach for improving such locality; however, existing methods, such as GOrder, suffer from two major limitations: they are applied without estimating whether a matrix has sufficient relabeling headroom, and they can incur substantial preprocessing overhead on large graphs. To address these issues, we propose a locality-activated parallel matrix reordering framework consisting of two components. First, we introduce a reuse-distance-based locality headroom predictor that estimates the potential SpMV speedup after applying matrix reordering; reordering is activated only when the expected benefit is sufficiently large. Second, we propose a two-phase parallel matrix reordering algorithm, termed pGOrder. It decomposes the sequential greedy process of GOrder into global coarse-grained batch generation and local fine-grained refinement. In the first phase, reuse-aware vertex batches are generated on the GPU according to global reuse signals. In the second phase, the ordering within each batch is refined concurrently on multi-core CPUs. Experimental results show that the proposed predictor effectively identifies matrices with meaningful locality headroom, and pGOrder preserves most of the locality benefit of GOrder while substantially reducing order-generation overhead. On the selected matrices, pGOrder retains over 95% of GOrder’s average SpMV speedup while requiring less than 5% of its order-generation time.