CVR: efficient vectorization of SpMV on x86 processors
CVR: efficient vectorization of SpMV on x86 processors
复制标题
DOI：
10.1145/3168818
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Biwei Xie;Jianfeng Zhan;Xu Liu;Wanling Gao;Zhen Jia;Xiwen He;Lixin Zhang
中科院分区：
文献类型：
--
作者：
Biwei Xie;Jianfeng Zhan;Xu Liu;Wanling Gao;Zhen Jia;Xiwen He;Lixin Zhang
稀疏矩阵向量乘法（Sparse Matrix-vector Multiplication，SpMV）是一种重要的计算内核，广泛应用于高性能计算和数据中心。SpMV的不规则性是一个众所周知的挑战，限制了SpMV与矢量化操作的并行性。现有的工作实现了有限的局部性和矢量化效率与大的预处理开销。为了解决这个问题，我们提出了面向压缩矢量化的稀疏行（CVR），一种新的SpMV表示，目标是有效的矢量化。CVR同时处理输入矩阵内的多个行以提高缓存效率，并将它们分成多个SIMD通道，以便利用现代处理器中的向量处理单元。我们的方法是不敏感的SpMV的稀疏性和不规则性，从而能够处理各种无标度和HPC矩阵。我们在Intel Knights Landing处理器上实现并评估了CVR，并通过使用58个无标度矩阵和HPC稀疏矩阵将其与五种最先进的方法进行了比较。实验结果表明，CVR算法在无标度矩阵和HPC稀疏矩阵情况下分别比现有最佳算法获得了1.70倍（平均1.33倍）和1.57倍（平均1.10倍）的加速比.此外，与最先进的方法相比，CVR通常会产生最低的预处理开销。
Sparse Matrix-vector Multiplication (SpMV) is an important computation kernel widely used in HPC and data centers. The irregularity of SpMV is a well-known challenge that limits SpMV’s parallelism with vectorization operations. Existing work achieves limited locality and vectorization efficiency with large preprocessing overheads. To address this issue, we present the Compressed Vectorization-oriented sparse Row (CVR), a novel SpMV representation targeting efficient vectorization. The CVR simultaneously processes multiple rows within the input matrix to increase cache efficiency and separates them into multiple SIMD lanes so as to take the advantage of vector processing units in modern processors. Our method is insensitive to the sparsity and irregularity of SpMV, and thus able to deal with various scale-free and HPC matrices. We implement and evaluate CVR on an Intel Knights Landing processor and compare it with five state-of-the-art approaches through using 58 scale-free and HPC sparse matrices. Experimental results show that CVR can achieve a speedup up to 1.70 × (1.33× on average) and a speedup up to 1.57× (1.10× on average) over the best existing approaches for scale-free and HPC sparse matrices, respectively. Moreover, CVR typically incurs the lowest preprocessing overhead compared with state-of-the-art approaches.