ADEM: Accelerating Sparse Matrix Multiplication with Adaptive Dataflow and Efficient Merging

Abstract

Sparse Matrix-Sparse Matrix Multiplication (SpMSpM) is a crucial computational kernel widely used in scientific computing and machine learning. The varying sparse patterns across different matrices pose significant challenges for conventional accelerators with fixed dataflow architectures. Although recent studies have explored dynamic dataflow approaches to better capture memory access patterns under diverse sparsity conditions, these solutions still struggle to simultaneously improve data reuse, load balance, and merging efficiency. To address these limitations, we present an SpMSpM accelerator based on adaptive dataflow and efficient merging (ADEM). ADEM is carefully designed from four key aspects. First, we propose the segmented fiber tree (SFT) data structure, which extends the conventional fiber tree through further partitioning to better support our dataflow paradigm while enhancing data reuse. We then present a cache-aware dataflow to mitigate memory overflow issues. Furthermore, ADEM decouples the multiplication and merging phases, utilizing the SFT structure to enable fine-grained task scheduling for improved load balancing. Finally, the accelerator incorporates heterogeneous merging units specifically optimized for handling two distinct types of merging operations, thereby significantly improving merger utilization. Compared with the state-of-the-art baseline system, ADEM achieves average speedups of 1.25 ×, 1.73 ×, and 1.16 × on VGG-16, ResNet-50, and SuiteSparse workloads, respectively.