ASA: A ccelerating S parse A ccumulation in Column-wise SpGEMM
ASA: A ccelerating S parse A ccumulation in Column-wise SpGEMM
复制标题
ASA：加速 S 解析 Column-wise SpGEMM 中的累积
DOI：
10.1145/3543068
复制
发表时间：
2022
影响因子：
1.6
通讯作者：
Guo, Xiaochen
中科院分区：
文献类型：
--
作者：
Zhang, Chao;Bremer, Maximilian;Chan, Cy;Shalf, John;Guo, Xiaochen
稀疏线性代数是许多不同应用中的重要核心。在各种稀疏通用矩阵-矩阵乘法（SpGEMM）算法中，Gustavson 的列式 SpGEMM 在读取输入矩阵时具有良好的局部性，并且可以通过将输出矩阵的不同列的计算分布到不同的处理器来轻松并行化。然而，按列 SpGEMM 中的稀疏累加 (SPA) 步骤（合并每次乘以行索引的部分和）仍然是性能瓶颈。最先进的软件实现在 SPA 中使用哈希表进行部分求和搜索，这使得 SPA 成为 SpGEMM 执行时间的最大贡献者。导致 SPA 成为瓶颈的三个原因：（1）哈希探测需要依赖于数据的分支，而分支预测器很难正确预测； (2)部分和的累加依赖于哈希探测的结果，这使得难以隐藏哈希探测延迟； (3)哈希冲突需要耗时的线性搜索和优化来减少这些冲突，需要准确估计输出矩阵每列中的非零数。这项工作提出了 ASA 架构来加速 SPA。 ASA 通过以下方式克服了 SPA 的挑战：(1) 通过 ISA 扩展使用单个指令执行部分和搜索和累加，以消除哈希探测中数据相关的分支；(2) 使用专用片上缓存以流水线方式执行搜索和累加；(3) 依靠组关联缓存的并行搜索功能来减少搜索延迟；(4) 延迟溢出条目的合并。因此，与马尔可夫聚类应用程序及其 SpGEMM 内核的最先进的软件实现相比，ASA 分别实现了平均 2.25 倍和 5.05 倍的加速。与最先进的哈希加速器设计相比，ASA 在 SpGEMM 内核中实现了平均 1.95 倍的加速。
Sparse linear algebra is an important kernel in many different applications. Among various sparse general matrix-matrix multiplication (SpGEMM) algorithms, Gustavson’s column-wise SpGEMM has good locality when reading input matrix and can be easily parallelized by distributing the computation of different columns of an output matrix to different processors. However, the sparse accumulation (SPA) step in column-wise SpGEMM, which merges partial sums from each of the multiplications by the row indices, is still a performance bottleneck. The state-of-the-art software implementation uses a hash table for partial sum search in the SPA, which makes SPA the largest contributor to the execution time of SpGEMM. There are three reasons that cause the SPA to become the bottleneck: (1) hash probing requires data-dependent branches that are difficult for a branch predictor to predict correctly; (2) the accumulation of partial sum is dependent on the results of the hash probing, which makes it difficult to hide the hash probing latency; and (3) hash collision requires time-consuming linear search and optimizations to reduce these collisions require an accurate estimation of the number of non-zeros in each column of the output matrix.This work proposes ASA architecture to accelerate the SPA. ASA overcomes the challenges of SPA by (1) executing the partial sum search and accumulate with a single instruction through ISA extension to eliminate data-dependent branches in hash probing, (2) using a dedicated on-chip cache to perform the search and accumulation in a pipelined fashion, (3) relying on the parallel search capability of a set-associative cache to reduce search latency, and (4) delaying the merging of overflowed entries. As a result, ASA achieves an average of 2.25× and 5.05× speedup as compared to the state-of-the-art software implementation of a Markov clustering application and its SpGEMM kernel, respectively. As compared to a state-of-the-art hashing accelerator design, ASA achieves an average of 1.95× speedup in the SpGEMM kernel.