点击数: 更新日期: 2023-11-10
中文题目：平衡分布式稀疏矩阵向量乘法中的计算和通信
论文题目：Balancing Computation and Communication in Distributed Sparse Matrix-Vector Multiplication
录用会议：CCGRID 2023: International Symposium on Cluster, Cloud and Grid Computing (CCF C类)
原文DOI：10.1109/CCGrid57682.2023.00056
原文链接：https://ieeexplore.ieee.org/abstract/document/10171520
录用/见刊时间：2023年5月1日
封面图片：
封面摘要：平衡分布式稀疏矩阵向量乘法中的计算和通信
该研究成果由刘伟峰团队完成，目前已被CCGRID : International Symposium on Cluster, Cloud and Grid Computing (CCF C类)接受录用并发表。
作者列表：
1） 米宏丽 中国石油大学（北京）信息科学与工程学院 计算机科学与技术专业 本科 20
2） 余湘锐 中国石油大学（北京）信息科学与工程学院 计算机科学与技术专业 本科 19
3） 俞啸松 中国石油大学（北京）信息科学与工程学院 计算机技术专业 硕 19
4） 吴双元 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 讲师
3） 刘伟峰 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 教授
摘要:
稀疏矩阵向量乘法 (SpMV) 是许多科学和工程问题中的基本运算。 当处理的稀疏矩阵足够大时，应该使用分布式存储系统来加速SpMV。 目前，分布式SpMV的优化技术主要集中在通过图或超图分割进行重新排序。然而，尽管重新排序总体上可以减少通信量，但分布式平台上的计算和通信仍然存在负载平衡挑战，尚未得到很好的解决。
在本文中，我们提出了两种在分布式集群上优化 SpMV 的策略：（1）调整节点上行块的数量以平衡计算量，以及（2）调整对角块的列数以平衡任务和减少计算节点之间的通信。 实验结果表明，与经典的分布式 SpMV 实现及其通过图分割重新排序的变体相比，我们的算法分别实现了平均 77.20 倍和 5.18 倍（高达 460.52 倍和 27.50 倍）的加速。 此外，我们的方法比最近提出的混合分布式 SpMV 算法平均加速 19.56 倍（高达 48.49 倍）。 此外，我们的算法比这些现有的分布式 SpMV 方法具有明显更好的可扩展性。
背景与动机:
在分布式SpMV中，部分矩阵A和两个向量x和y被分配在所使用的集群的节点上。多种方法可以生成不同的子矩阵和子向量，在分布式环境中运行SpMV时，节点之间发生通信。在收到x所需的分量后，每个进程可以并行计算SpMV，最后生成得到的向量y，并在需要时进行通信。操作步骤如下:
1)首先子矩阵和子向量被发送给每个进程。
2进程之间相互通信，每个进程将xj发送给具有非零元素Aij的进程。如图1所示
3) yi*+= Aij 乘以进程中的xj，其中yi*是中间结果。
4)将中间结果yi*发送给最终的yi进程。
5)将接收到的yi*相加，得到最终结果yi。
图表 1 将一个 16×16 的矩阵和一个长度为 16 的向量均匀分布在四节点集群上进行分布式SpMV计算时的通信过程（图示中仅列出节点3的通信过程）
挑战：第一，如图1所示，分布式SpMV操作各个进程间需要进行大量的通信，这是分布式SpMV的限制因素之一。第二，通讯负载不均衡的问题也一直限制分布式SpMV的性能，第三，矩阵的多样性和不规则性可能导致矩阵划分到每个节点后计算不平衡。尽管图2是已经经过图分割以及矩阵重排后进行的划分，但我们仍然能够发现，各节点间存在计算负载不均衡的问题，目前，还没有有效的优化策略来实现分布式SpMV的理想性能。这促使我们对分布式SpMV在图分割的基础上进一步做出通信以及计算负载均衡的优化
主要内容:
基于上述挑战，我们提出一种名为DistSpMV_Balanced的优化策略，主要分为以下4个步骤，如图3所示：
1． 使用图分割对稀疏矩阵对应的超图进行划分并重排，减少通信量。
2． 调整对角线块的列数，再次扩大对角块中非零元的数量以减少通信量。
3． 将矩阵划分为本地矩阵及远程矩阵，远程矩阵调整行块数来平衡计算量。
4． 使用 MPI+OpenMP 混合编程模式，实现两层并行，并在进程以及线程间对分布式 SpMV 进行计算负载均衡优化。
图表 2 DistSpMV_Balanced 算法的示例。
实验结果及分析:
分别采用简单的分布式SpMV算法（DistSpMV）、采用图分割技术的分布式SpMV算法（DistSpMV_Reordered）以及采用本文提出的优化策略算法（DistSpMV_Balanced）三种算法情况下20个矩阵的性能对比如图3所示。
图表 3 DistSpMV,DistSpMV_Reordered,DistSpMV_Balanced三种算法性能对比图
DistSpMV,DistSpMV_Reordered,DistSpMV_Balanced三种算法各个进程之间的通信量热力图4如下：
结论: 图表 4 DistSpMV,DistSpMV_Reordered,DistSpMV_Balanced三种算法进程间通信量对比图
我们的算法与18年混合分布式SpMV（称为DistSpMV_Hybird）性能对比如如图5所示，我们的方法比DistSpMV_Hybird 算法平均加速 19.56 倍（高达 48.49 倍）
图表 5 与DistSpMV_Hybird 算法的性能对比图
预处理时间的对比：我们的算法对比使用图分割技术的DistSpMV_Reordered 算法性能有很大提升，但预处理时间最高为1.31倍，最低仅为1.05倍。
图表 6 与DistSpMV_Reordered算法与处理时间的对比
作者简介:
刘伟峰，博士、中国石油大学（北京）教授、博士生导师，欧盟玛丽居里学者。2002年和2006年于中国石油大学（北京）计算机系获学士与硕士学位。2006年至2012年在中国石化石油勘探开发研究院历任助理工程师、工程师和高级研究师，其间主要研究领域为石油地球物理勘探的高性能算法。2016年于丹麦哥本哈根大学获计算科学博士学位，主要研究方向为数值线性代数和并行计算，其中尤其关注稀疏矩阵的数据结构、并行算法和软件。研究工作发表于SC、PPoPP、DAC、ASPLOS、ICS、IPDPS、ICPP、TPDS、JPDC、FGCS和Parco等重要国际会议和期刊。担任TPDS、SISC和TKDE等多个重要国际期刊审稿人，以及SC、ICS、IPDPS和ICPP等多个重要国际会议的程序委员会委员。他是IEEE高级会员、CCF高级会员、ACM和SIAM会员。