Lu, Xuanhao, Ahrar, Alireza, Rahimi Azghadi, Mostafa, Genov, Roman, and Amirsoleimani, Amirali (2025) MATSORT: Fast and Efficient Approximate Matrix Sorting Algorithm for DNN Applications. In: Proceedings IEEE International Symposium on Circuits and Systems. From: ISCAS 2025: IEEE International Symposium on Circuits and Systems, 25-28 May 2025, London, UK.

PDF (Published Version) - Published Version Restricted to Repository staff only

Abstract

This paper proposes Matrix Sorting (MATSORT), a novel algorithm for compressing sparse matrices to enable efficient execution of sparse Multiply-Accumulate (MAC) operations in parallel computing architectures for Deep Neural Networks (DNNs). Pruning in DNNs often results in weight matrices with a large proportion of zero weights, leading to significant resource and time wastage when processed by parallel computing architecture. MATSORT outperforms state-of-the-art (SoTA) techniques in both compression speed and compression rate - two key factors for efficient sparse MAC operations. The algorithm employs an approximate sorting method and a novel merging strategy, reducing the sorting time complexity while resolving long-standing element conflict issues. These optimizations achieve nearly 100% compression rates across all tested matrices, substantially enhancing power and resource efficiency. Evaluation results show that MATSORT delivers a maximum speedup of 441× for a 1280 × 1280 matrix and a minimum speedup of 1.63× for a 110 × 128 matrix, outperforming existing methods.

Actions (Repository Staff Only)

Item Control Page