论文题目：Segmented Merge: A New Primitive for Parallel Sparse Matrix Computations

发表会议：The 17th Annual IFIP International Conference on Network and Parallel Computing (CCF C类会议)

作者列表

1) 戢昊男 中国石油大学(北京) 信息科学与工程学院 计算机科学与技术专业 研20级

2) 卢世博 中国石油大学(北京) 信息科学与工程学院 计算机科学与技术专业 本16级

3) 侯凯希 美国弗吉尼亚理工大学

4) 汪 浩 美国俄亥俄州立大学

5) 刘伟峰 中国石油大学(北京) 信息科学与工程学院 计算机科学与技术系

6) Brian Vinter 丹麦奥胡斯大学

文章摘要

本文提出了一个被称为分段合并的新的并行原语，实现了从q个有序子段到p个主段的并行合并。这q个子段的长度和主段中包含子段的数目都可以是不同的。我们的主要思想是确定一个线程所处理的元素数目，并以二叉树的形式将同一段中的子段合并，直到每个段内只剩一个子段。这种操作可以被广泛的应用于稀疏矩阵的处理中，以解决其中非规则性导致的负载不均衡问题。在两个NVIDIA Turing GPU(RTX 2080和Titan RTX)上进行测试的表明，与NVIDIA cuSPARSE库相比，我们的算法使稀疏矩阵转置(SpTRANS)和稀疏矩阵乘法(SpGEMM)运算的性能分别提高了3.94和2.89倍。

背景与动机

随着分段排序、分段扫描、分段求和等并行分段原语的提出和这些分段原语在并行不规则稀疏矩阵算法上带来的良好性能改进，分段操作受到了研究人员的广泛关注。然而尽管合并算法是计算机科学重要的基础算法之一，分段合并却还没有受到人们的关注。基于我们对稀疏矩阵操作的观察，分段合并原语可能在稀疏矩阵转置(SpTRANS)和稀疏矩阵乘法(SpGEMM)等操作中很有价值。因此，我们在本工作中提出了分段合并原语，并解决了实现并行分段合并操作的两大挑战：一是段的长度和子段的长度不均匀导致的负载均衡问题；二是在超大规模并行的图形处理器(GPU)上向量化问题。

设计与实现

在本文中，我们定义了分段合并原语。

假定我们有一个键值对数组S，包含p个段，

(1)

每个段包含q_i 个子段，

(2)

我们可以得到

(3)

每个子段S_i,j 有n_i,j 个已经根据关键字排序的键值对。我们的分段合并操作就是让每个段内的所有键值对按关键字有序排列。

基于这个定义，我们提出了一个并行分段合并算法，其主要思想是通过固定线程处理的元素数量解决负载均衡的问题，并以二叉树的形式将同一段中的子段两两合并，直到所有子段合并完成。该算法包括三个步骤：

(1)数据预处理(4-15行)：首先记录段和子段的位置，然后为每个线程固定工作量，最后通过运行标准合并路径算法的分区策略为每个线程收集所处理数据的信息；

(2)使用合并路径合并每个线程的两个子序列(16-18行)；单个线程已经包含执行合并操作所需的所有信息，可以有效地合并两个有序的子段。而子段的合并操作通常由多个线程完成，这些线程通过合并路径算法进行合并子段。首先，将与线程对应的子段中的数据进行多次比较，以生成用于分割两个子段的边界，然后根据目标矩阵，将两个子段中的数据按照路径放入输出序列中，完成合并操作。算法图中粉红色虚线框显示了两组子段合并的例子。

(3)迭代合并二叉树上的子段(3-21行)：同一段的每一个子段可视为二叉树的一个叶节点进行合并，可能需要多次迭代。当段内只有一个子段时，迭代结束，分段合并完成。

下图展示了使用分段合并算法将八个子段合并为三个有序段的一个例子。

分段合并实例图

实验结果

本文在两个NVIDIA Turning GPU(RTX 2080和Titan RTX)上对SpTRANS和SpGEMM进行了测试，并将它们与NVIDIA 的cuSPARSE v10.2库中的相应函数进行了比较，数据集从SuiteSparse Matrix Collection中进行选择。

我们的SpTRANS算法是将CSR格式的矩阵转置成CSR格式的矩阵。经测试，我们的算法在两个GPU上对于cuSPARSE算法平均加速比分别达到3.55倍(最高9.64倍)和3.94倍(最高13.09倍)。

SpTRANS实验： cuSPARSE方法和使用分段合并原语方法在两个NVIDIA GPU上的比较。x轴表示被测矩阵的密度(非零元数与行数和列数之积的比率)。

SpGEMM算法计算C=AB，其中A、B和C三个矩阵都是稀疏的。我们使用行-行方法，每个处理单元遍历A行中的非零元，并使用这些值乘以B对应行的所有元素，然后将乘后的元素合并到C的行中。经测试，我们的算法在RTX 2080上，对于cuSPARSE和bhSPARSE算法平均加速比分别达到了2.89x(最高109.15x)和1.26x(最高7.5x)；在Titan RTX上，平均加速分别为2.53倍(高达81.85倍)和1.22倍(最高17.38倍)。

SpGEMM实验： cuSPARSE方法，bhSPARSE方法和采用分段合并方法在两个NVIDIA GPU上的比较。x轴是压缩率，即结果矩阵中中间非零元与非零元的数量之比。

关于作者：

刘伟峰，博士，中国石油大学(北京)信息科学与工程学院教授，院长，欧盟玛丽居里学者。2002年和2006年于中国石油大学(北京)计算机系获学士与硕士学位，2006年至2012年在中国石化石油勘探开发研究院历任助理工程师、工程师和高级研究师，其间主要研究领域为石油地球物理勘探的高性能算法。2016年于丹麦哥本哈根大学获计算科学博士学位，主要研究方向为高性能稀疏线性代数子程序。他的主要研究兴趣为数值线性代数和并行计算，其中尤其关注稀疏矩阵的数据结构、并行算法和软件。 他的研究工作发表于SC、ICS、PPoPP、ASPLOS、IPDPS、JPDC、FGCS和Parco等重要国际会议和期刊。他还是TPDS、SISC和TKDE等多个重要国际期刊审稿人，也是SC、ICS和ICPP等多个重要国际会议的程序委员会委员。他是IEEE和CCF高级会员以及ACM和SIAM会员。联系方式：weifeng.liu@cup.edu.cn