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. To address the above challenges, in this work, we propose HiSpMV to accelerate imbalanced SpMV on HBM-equipped FPGAs. First, we design a hybrid row distribution network to enable both inter-row and intra-row distribution to achieve more balance. Second, we implement fully pipelined floating-point accumulation on the output vector using a combination of an adder tree and circular buffer. Third, we design a hybrid buffering technique to optimize the input vector loading from off-chip memory by dynamically switching between private partitioned buffers and shared ping-pong buffers. Lastly, we also developed an automation framework to automatically generate the optimized HiSpMV accelerator based on the user configurations. Experimental results demonstrate that HiSpMV achieves a geomean speedup of 13.7x (up to 60x) for highly imbalanced matrices, compared to state-of-the-art SpMV accelerator Serpens on the AMD-Xilinx Alveo U280 HBM-based FPGA. Compared to Intel MKL running on a 24-core Xeon Silver 4214 CPU, HiSpMV achieves a geomean speedup of 5.5x. Compared to cuSPARSE running on an NVIDIA 1080ti GPU, HiSpMV achieves a geomean of 2.1x better performance per watt.