Sparse General Matrix-Matrix Multiplication (SpGEMM) is a key computational kernel in various emerging applications, such as linear algebra, computational chemistry, graph analytics, and deep learning. These applications are memory-bounded that real-world matrix from graph matrix or AI show up to 0.0001% density. Prior row-wise based state-of-the-art accelerator introduces highly-banked cache to
maximize output reuse. However, inefficiently utilize the cache that processes multiple rows concurrently with high-radix and low-throughput mergers, which limits output reuse. To address this problem, this paper proposes a bitonic-sorter-based high-radix and high-throughput merger that maximizes output reuse. We minimize the overhead of high-throughput mergers by removing redundant comparison of bitonic-sorter with a novel one-cycle prediction scheme to optimize it. We further develop a fullypipelined accumulator and aligner to mitigate the long latency penalty. We implement a cycle-accurate simulator based on gem5, which shows 2x, 6x, 47x speedup over prior state-of-the-art Matraptor, GPU, and CPU, respectively.
이 논문에서는 높은 처리량을 가지는 정렬기 기반의 희소 행렬곱 가속기를 다루었다. 기존의 행-우선 데이
터 흐름에서 낮은 처리량을 가지는 정렬기 기반의 가속기가 근본적으로 가지는 비효율성을 지적하고, 높은
처리량을 가지는 정렬기 기반의 가속기를 제시하였다. 특히, 기존의 높은 정렬기 기반의 가속기가 가지는
큰 간접비를 완전히 파이프라인 된 구조로 해결하는 방안을 제시하고, 공동 메모리 구조에서 발생하는 콜드
미스를 줄일 수 있는 방안을 제시하였다. 결과적으로 제안된 가속기는 기존의 가속기인 Matraptor, GPU,
CPU에 비하여 2배, 6배, 47배 더 빠른 속도를 보임을 확인하였다.
