SpArch: Efficient Architecture for Sparse Matrix Multiplication
Zhekai Zhang∗, Hanrui Wang∗, Song Han ∗Equal Contributions. EECS Massachusetts Institute of Technology Cambridge, MA, US {zhangzk, hanrui, William J. Dally Electrical Engineering Stanford University / NVIDIA Stanford, CA, US
Abstract
Generalized Sparse Matrix-Matrix Multiplication (SpGEMM) is a ubiquitous task in various engineering and scientific applications. However, inner product based SpGEMM introduces redundant input fetches for mismatched nonzero operands, while outer product based approach [1] suffers from poor output locality due to numerous partial product matrices. Inefficiency in the reuse of either inputs or outputs data leads to extensive and expensive DRAM access.
中文速览
稀疏矩阵乘法（SpGEMM）广泛用于深度学习、图计算和科学仿真，但因数据分布稀疏、访存不规则，在CPU/GPU上严重受限于内存带宽。现有的外积（outer product）加速器虽然能复用输入数据，却会产生海量中间"部分矩阵"，反而造成大量片外DRAM读写。SpArch通过四项协同优化来同时提升输入和输出的数据局部性：设计基于比较器阵列的流水线合并器，让部分矩阵在片上边生产边合并；提出"矩阵压缩"表示法，将部分矩阵数量减少三个数量级；用Huffman树调度器安排近最优的合并顺序；再配合预取行缓冲器以近最优替换策略弥补输入复用的损失。在20个真实基准测试上，SpArch比现有最优加速器减少2.8倍DRAM访问，并分别实现对OuterSPACE、MKL、cuSPARSE等平台4×至1285×的速度提升和6×至435×的能耗节省，为稀疏矩阵计算提供了一条高效的专用硬件加速路径。
原文 arXiv:2002.08947;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2002.08947v1