PANA: A Fine-Grained Runtime-Adaptive Load Balancing for Parallel SpMV on multicore CPUs

Abstract

SpMV has been widely utilized and is regarded as a significant kernel in various scientific and engineering computing applications, where its parallel performance is heavily influenced by matrix sparsity and hardware architecture. Despite extensive prior research, static partitioning strategies that narrowly target computation or memory access remain a key performance bottleneck, severely stifling performance advancement of SpMV on modern multicore CPUs. This paper presents PANA, a fine-grained runtime-adaptive load balancing for parallel SpMV that operates at the micro-operation level. It employs fine-grained partitioning and a dynamic runtime adjustment mechanism to achieve balanced per-core computation and memory access. Experiments on 2,898 SuiteSparse matrices show that PANA outperforms CAMLB, CSR5, MKL, Merge, CVR, and SpV8 on the Intel Xeon Gold 6542Y, with average speedups of 1.36x, 1.75x, 2.09x, 1.49x, 2.11x, and 3.98x (up to 23.96x, 28.39x, 50.98x, 32.09x, 99.51x, and 142.59x). On the AMD EPYC 9654, PANA outperforms CAMLB, CSR5, AOCL, Merge, CVR, and SpV8 with average speedups of 1.44x, 2.47x, 7.62x, 1.69x, 2.86x, and 7.72x (up to 35.43x, 74.17x, 307.97x, 60.25x, 358.78x, and 437.05x).