中间结果累加在稀疏矩阵计算

第三个问题是耗时的中间结果累加。在基于外积的SpGEMM中，结果矩阵C是通过将A的每一行和B的对应列的外积结果相加而得，其中间的外积结果通常是一个稀疏矩阵。在逐行相乘的SpGEMM中，通过将A的每一个非零项与B的对应行的相乘结果相加来获得结果矩阵，中间的相乘结果也是稀疏的。其他两个公式相似。因此，无论选择哪种SpGEMM公式，都会涉及稀疏结构的合并问题，这是一个具有挑战性的问题。

（1）累加器：将保存中间结果的数据结构称为累加器。接下来，以逐行相乘的SpGEMM为例介绍累加器（因为SpGEMM的大部分研究都是基于逐行相乘的计算方法）。目前主要有两种类型的累加器：稠密累加器和稀疏累加器。

在稠密累加器中，一行的中间结果以稠密格式存储在大小为r的数组中，其中r是结果矩阵的列维度。它不需要额外的时间开销来进行哈希、排序和合并操作，但可能不适合大量线程和较大r值的并行。Deveci等人将稠密累加器应用于CPU或KNL，而因为其高内存需求并没有应用于GPU平台。Patwary等人利用稠密累加器对B进行按列划分，以减少内存开销。 Elliott等人提到AMG方法中的延拓矩阵（P）通常是细长形的（又高又窄），因此他们对每个线程使用一个局部的稠密查找数组，并通过页对齐和大小跟踪技术为结果矩阵快速分配内存空间。

在逐行相乘的SpGEMM中，结果矩阵C的每一行都可以表示为，即为稀疏累加器。在稀疏累加器中，一行的中间结果以稀疏格式（如COO和CSR）存储。因此，在使用稀疏累加器的SpGEMM中，随机位置的插入操作会造成昂贵的时间开销。中间结果合并有两种方法：基于排序的方法和基于哈希的方法。

（2）基于排序：基于排序的合并方法是指根据列索引对中间结果进行排序，然后对具有相同列索引的数值项进行求和。基于排序的不同方法之间的区别通常在于所使用的排序算法不同，包括基数排序，归并排序和堆排序。

① 基数排序。Bell等人采用基数排序对中间结果进行排序，而Dalton等人采用B40C基数排序算法，该算法允许指定排序位的数量和位置以加速排序操作。

② 归并排序。在Gremse等人提出的基于GPU加速的SpGEMM中，矩阵B的每一行用矩阵A中对应非零元的数目加权，其合并过程采用类似于归并排序的分层合并实现。在每一层，矩阵行的数量减少一半，但是由于合并其每一行的长度将增加。Winter等人利用ESC方法对某一个块产生的中间结果进行排序，且忽略了矩阵的行边界。在合并阶段利用块的全局顺序完成块的简单排序。最后，采用前缀扫描的方法合并块之间共享的行以生成最终结果。(www.xing528.com)

③ 堆排序。Azad等人将中间结果表示为三元组列表，每个三元组列表均按（j，i）对排序，其中三元组（i，j，val）存储非零项的行索引、列索引和值。通过维护一个大小为k的堆来实现k个三元组列表T1，T2，…，Tk 的k路合并，该堆空间存储每个三元组列表中当前的字典最小项。然后，通过多路合并例程从堆中找到最小的三元组并将其合并到当前结果中。Nagasaka等人实现了一种基于堆排序的稀疏累加器，该稀疏累加器在KNL和多核体系结构中采用单阶段的SpGEMM。在Liu等人提出的稀疏累加器（类似于基于堆排序的累加器）中，每个线程存储多个列索引，然后执行intra-thread-min操作以获得每个线程的局部最小列索引intra-min，同时每个线程获取每个intra-min的中间结果值，接下来每个线程执行inter-thread-min（intra-min）操作，以获得同一warp下所有线程的最小列索引min，最后通过inter-sum［value（min）］获得多个线程min处的规约和。

此外，Liu等人提出了一种基于寄存器感知排序的稀疏累加器和并行分段求和的向量化方法，其中稀疏累加器利用N-to-M模式对寄存器中的数据进行排序，这是首次利用GPU寄存器来实现稀疏累加器和求和。

（3）基于哈希：基于哈希的稀疏累加器首先基于上限估计法分配一块对应大小的存储空间作为哈希表，并使用中间结果的列索引作为键值。然后通过哈希函数将哈希列表压缩为稠密状态，最后根据它们的列索引对结果矩阵每一行的值进行排序，以获得以稀疏格式压缩的最终的结果矩阵。cuSPARSE中的结果累加就是采用了基于哈希的稀疏累积器。Deveci等人设计了一种基于HashMap的两层稀疏累加器，该累加器支持多个向量通道的并行插入或累加，它存储在链接列表结构中，且由4个并行数组、列索引及其在数值阶段的数据组成，哈希值对应于链接列表中的开始索引，同时链接列表中存有下一个元素的索引。他们利用不同的数据结构实现了基于链接列表的线性探测HashMap累加器。Liu等人利用GPU寄存器优化了基于哈希的累加器中每个线程的数据分配。此外，Yasar等人在三角形计数中利用了基于HashMap的累加器。Weber等人使用哈希表且基于BCSR格式存储矩阵C的每一行。Nagasaka等人将哈希表用于对符号阶段每一行非零数的计数和数值阶段结果矩阵值的计算。

此外，Liu等人提出了一种混合并行的结果合并方法。根据计算出的结果矩阵中每行非零数的上限值，分别使用类似于堆排序、双调ESC和归并的方法。

讨论：基于排序的合并和基于哈希的合并是两种常用的合并算法，而哪种是最佳合并算法在数十年来一直是具有争议性的问题。Kim等人通过一系列实验证明当SIMD足够宽时，基于排序的合并将比基于哈希的合并更快。Albutiu等人设计了一种新的大规模并行的排序合并（MPSM）算法，实验结果表明MPSM算法优于哈希合并。但是，Balkesen等人进行的实验表明，基于哈希的合并仍然是占优的，仅当涉及大量数据的合并时，基于排序的合并算法才优于基于哈希的合并。因此，合并算法的效率与矩阵的规模和数据分布是有密切的关系的。