论文部分内容阅读
基于多核CPU和众核GPU的高性能计算平台已经成为高性能计算领域的主流计算平台,极大地推动着大量科学和工程应用的进步。稀疏矩阵乘法(Sparse GEneral Matrix Multiplication,SpGEMM)是图计算、线性代数、机器学习等大量科学和工程应用中的一个关键算子。包含SpGEMM算法的应用有多源广度优先算法、代数多重网格法、马尔科夫聚类算法等。提升SpGEMM算法的性能对于提升这些科学和工程应用的性能具有重要意义。但是SpGEMM算法中存在大量不规则的访存和计算,而现有高性能计算平台主要由多核CPU或众核GPU构成,在这些计算平台上优化SpGEMM算法面临大量挑战。为了应对这些挑战,本文采用硬件体系结构与SpGEMM算法特征紧密结合的研究方法,分析现有SpGEMM算法存在的问题,并提出了两个分别针对多核CPU和众核GPU架构的SpGEMM优化算法。此外,本文还提出一种预估结果矩阵稀疏结构的方法,可以用来提升SpGEMM的性能,同时降低其对内存的使用量。本文的具体工作和创新点如下:1)针对多核CPU架构提出基于二元行合并算法和乒乓缓冲区的SpGEMM优化算法。本文结合CPU架构和SpGEMM算法特征,发现现有基于CPU的SpGEMM算法存在访存不够高效的问题。为了解决这个问题,本文提出一种基于二元行合并算法和乒乓缓冲区实现的新型汇聚方法BRMerge,并基于BRMerge提出两个SpGEMM库。BRMerge首先将计算每个结果行需要的中间列表连续地存储在一块乒乓缓冲区中,随后将这些中间列表在两个乒乓缓冲区之间按照树状结构两两合并,直到得到一个列表作为结果行。BRMerge在CPU架构上的优势是具有流式访存模式、最小化的TLB缺失率、以及合理高的L1/L2缓存命中率。这些架构优势使BRMerge能具有较高的访存带宽和缓存利用率,从而极大提升了BRMerge的访存效率,进而提升其性能。实验结果表明,基于BRMerge所提的SpGEMM算法比现有最先进的SpGEMM算法平均提速1.42倍。2)针对众核GPU架构提出一个高度优化的SpGEMM计算框架。本文结合GPU架构和SpGEMM算法特点,分析了两个先进的SpGEMM库(即nsparse和sp ECK),发现其中七类未能充分发挥GPU计算资源的问题。基于这些发现,本文提出了七类对应的优化,并将这些优化整合在一起,设计了一个高度优化的SpGEMM计算框架Op Sparse。本文提出的七类优化是:1)通过提高对共享内存的利用率来优化分箱方法(binning method);2)通过减少对哈希表的访问次数来优化哈希方法;3)通过设置适当的分箱范围来改进哈希方法中哈希冲突率和GPU硬件利用率之间的权衡;4)通过最小化所需元数据(metadata)的全局内存使用量,同时使用合并的内存分配而非多个单独的内存分配,来减少在GPU上分配全局内存的开销;5)通过将全局内存分配与GPU内核执行相重叠来提高主机和设备的执行并行性;6)通过操纵内核启动顺序来优化GPU中流多处理器的负载平衡;以及7)优化GPU内核配置以实现GPU内核的理论满占用率。实验结果表明,Op Sparse比现有两个先进的SpGEMM库nsparse和sp ECK分别平均提速1.43倍和1.52倍。3)提出一种预估SpGEMM结果矩阵稀疏结构的方法。SpGEMM结果矩阵的稀疏结构(SpGEMM的输出结构)指的是每个结果行的非零元素个数,这个信息对提升SpGEMM的性能和降低SpGEMM对内存空间的使用量具有重要意义。不过精确地计算输出结构的代价很大。现有预估方法主要通过采样结果矩阵的一个样本矩阵中的非零元素个数来预估整个结果矩阵的非零元素个数,再利用每个结果行需要的乘法次数预估输出结构。本文发现样本结果矩阵的非零元素个数和需要的乘法次数具有强烈的正相关关系。基于这个发现,本文提出同时利用样本结果矩阵的非零元素个数和所需乘法次数来预估SpGEMM的输出结构。此外,本文提出利用行式乘法数据流来优化所提方法的计算开销。实验结果表明,本文所提预估方法对SpGEMM输出结构的预估准确度远远高于现有预估方法;本文所提方法的计算时间平均仅为现有最先进SpGEMM算法总计算时间的0.72%。