Sparse Matrix-Vector Multiplication Based on Online Arithmetic

Abstract

Online arithmetic, where computations are performed from the most significant digit first, has shown benefits in improving throughput and latency within high-performance computing. This computational mode is particularly beneficial for intensive data processing in sequential operations, enabling streaming computations. One such intensive operation is sparse matrix-vector multiplication (SpMV) which finds extensive application in various engineering fields. SpMVs are often carried out in compressed formats such as coordinate encoding format that inherently follows a sequential approach to execute multiply-and-accumulate (MAC) operations of sparse elements. Therefore, this paper proposes an online MAC unit, through a novel algorithm and architecture. Moreover, a SpMV unit is developed by integrating the proposed online MAC unit. The performance and efficiency of the proposed MAC design are evaluated against state-of-the-art MAC designs, synthesized using the TSMC 45 nm CMOS standard cell library with the Synopsis Design Compiler. Results demonstrate the superiority of the proposed MAC unit in terms of delay, area-delay product, and energy consumption. Besides, the SpMV employing the online MAC is compared with counterpart SpMV designs implemented in both ASIC and FPGA. The proposed SpMV design outperforms conventional designs in various performance metrics, achieving a speed-up of $1.69\times $ and energy reductions of up to 60.4% compared to other SpMV designs for 8-bit precision. Moreover, various sparse matrix datasets with different properties are used to evaluate the SpMV using the online MAC unit, considering metrics such as power, delay, hardware resources, and energy consumption.

Keywords

• Computer arithmetic
• adder
• multiplier
• multiply-and-accumulate (MAC) unit
• most-significant-digit first arithmetic
• energy consumption