Design Principles for Sparse Matrix Multiplication on the GPU
Design Principles for Sparse Matrix Multiplication on the GPU
复制标题
DOI：
10.1007/978-3-319-96983-1_48
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Carl Yang;A. Buluç;John Douglas Owens
中科院分区：
文献类型：
--
作者：
Carl Yang;A. Buluç;John Douglas Owens
我们在GPU上实现了两种新的稀疏矩阵密集矩阵乘法(SpMM)算法。我们的算法使用流行的压缩稀疏行(CSR)格式的稀疏输入，因此不需要昂贵的格式转换。虽然之前的SpMM工作集中在线程级并行，但我们还关注通过指令级并行和负载平衡隐藏延迟。我们从理论和实验上证明了所提出的SPMM比以前的方法更适合于GPU。我们确定了一种关键的存储器访问模式，该模式允许高效地访问输入和输出矩阵，这对于在SpMM上获得出色的性能至关重要。通过结合这两个因素--(I)基于合并的负载平衡和(Ii)以行为主的合并内存访问--我们在实际数据集上展示了4.1峰值加速比和31.7%的地理加速比。
We implement two novel algorithms for sparse-matrix dense-matrix multiplication (SpMM) on the GPU. Our algorithms expect the sparse input in the popular compressed-sparse-row (CSR) format and thus do not require expensive format conversion. While previous SpMM work concentrates on thread-level parallelism, we additionally focus on latency hiding with instruction-level parallelism and load-balancing. We show, both theoretically and experimentally, that the proposed SpMM is a better fit for the GPU than previous approaches. We identify a key memory access pattern that allows efficient access into both input and output matrices that is crucial to getting excellent performance on SpMM. By combining these two ingredients—(i) merge-based load-balancing and (ii) row-major coalesced memory access—we demonstrate a 4.1peak speedup and a 31.7% geomean speedup over state-of-the-art SpMM implementations on real-world datasets.