TaiChi: A Hybrid Compression Format for Binary Sparse Matrix-Vector Multiplication on GPU
TaiChi: A Hybrid Compression Format for Binary Sparse Matrix-Vector Multiplication on GPU
复制标题
DOI：
10.1109/tpds.2022.3170501
复制
发表时间：
2022
影响因子：
5.3
通讯作者：
Jianhua Gao;Weixing Ji;Zhaonian Tan;Yizhuo Wang;Feng Shi
中科院分区：
文献类型：
--
作者：
Jianhua Gao;Weixing Ji;Zhaonian Tan;Yizhuo Wang;Feng Shi
二进制稀疏矩阵向量乘法（Binary Sparse Matrix-Vector Multiplication，SpMV）是网络链接分析、整数分解、压缩感知、谱图理论等领域的一个重要计算核心。在400个稀疏矩阵上测试了几种流行的基于GPU的SpMV实现，我们观察到数据传输到GPU内存占总计算时间的很大一部分。对于二进制稀疏矩阵，常数值1的传递可以很容易地消除。然而，压缩索引数组一直是一个巨大的挑战。本文提出了一种新的压缩格式太极，以进一步减少索引数据副本，提高性能的SpMV，特别是对角占优的二进制稀疏矩阵。首先将输入矩阵划分为相对密集和超稀疏区域。然后，密集区域通过标记“0“进行反向编码，而超稀疏区域通过标记"1“进行编码。我们还根据我们的划分和编码格式设计了一种仅使用二进制矩阵加法和减法的新SpMV算法。在真实二进制稀疏矩阵上的测试结果表明，本文提出的二进制矩阵混合编码方法显著减少了数据传输量，提高了内核执行速度。它在GTX 1080 Ti上实现了5.63倍和3.84倍的最高传输和内核执行加速比，在Tesla V100上实现了3.39倍和3.91倍。
Binary Sparse Matrix-Vector Multiplication (SpMV) is a heavy computational kernel in weblink analysis, integer factorization, compressed sensing, spectral graph theory, and other domains. Testing several popular GPU-based SpMV implementations on 400 sparse matrices, we observed that data transfer to GPU memory accounts for a large part of the total computation time. The transfer of constant value 1s can be easily eliminated for binary sparse matrices. However, compressing index arrays has always been a great challenge. This paper proposes a new compression format TaiChi to further reduce index data copies and improve the performance of SpMV, especially for diagonally dominant binary sparse matrices. Input matrices are firstly partitioned into relatively dense and ultra-sparse areas. Then the dense areas are encoded inversely by marking ``0"s, while the ultra-sparse area is encoded by marking ``1"s. We also designed a new SpMV algorithm only using addition and subtraction for binary matrices based on our partition and encoding format. Evaluation results on real-world binary sparse matrices show that our hybrid encoding for binary matrix significantly reduces the data transfer and speeds up the kernel execution. It achieves the highest transfer and kernel execution speedups of 5.63x and 3.84x on GTX 1080 Ti, 3.39x and 3.91x on Tesla V100.