Toward Greener Matrix Operations by Lossless Compressed Formats

Sparse matrix-vector multiplication (SpMV) is a fundamental operation in machine learning, scientific computing, and graph algorithms. In this paper, we investigate the space, time, and energy efficiency of SpMV using various compressed formats for large sparse matrices, focusing specifically on Boolean matrices and real-valued vectors. Through extensive analysis and experimentation on server and edge devices, we observed that different matrix compression formats entail distinct trade-offs among space efficiency, execution time, and energy consumption. Notably, selecting the appropriate compressed format can reduce energy consumption by an order of magnitude on both servers and single-board computers. Moreover, our experiments reveal that while data parallelism can improve execution speed and energy efficiency, optimizing both simultaneously poses interesting challenges. Specifically, we demonstrate that for certain compression schemes, the optimal degree of parallelism for minimizing execution time does not coincide with that for energy efficiency. This finding aligns with recent results in the literature, thus challenging the prevailing assumption of a straightforward linear correlation between execution time and energy usage. Overall, our findings advocate for software engineers to adopt compressed data structures as important instruments in the development of more energy-efficient software components, extending beyond SpMV.