MATSORT: Fast and Efficient Approximate Matrix Sorting Algorithm for DNN Applications

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.