HiSpMV: Hybrid Row Distribution and Vector Buffering for Imbalanced SpMV Acceleration on FPGAs

Sparse matrix-vector multiplication (SpMV) is a fundamental operation in numerous applications such as scientific computing, machine learning, and graph analytics. While recent studies have made great progress in accelerating SpMV on HBM-equipped FPGAs, there are still multiple remaining challenges to efficiently accelerate imbalanced SpMV where the distribution of non-zeros in the sparse matrix is imbalanced across different rows. First, the imbalanced workload distribution among the parallel processing elements (PEs) leads to PE under-utilization and performance degradation. Second, the read-after-write dependency of the long-latency floating-point accumulation on the output vector causes pipeline stalls inside the PE, and existing scheduling solutions for balanced matrices no longer work effectively for imbalanced ones. Third, the memory access latency for the often overlooked input vector becomes a new performance bottleneck after the SpMV acceleration.