基于超图分区的分布式稀疏矩阵向量乘数据映射方法

摘要: 本发明属于高性能并行计算领域,具体涉及一种基于超图分区的分布式稀疏矩阵向量乘数据映射方法。背景技术:1、稀疏矩阵运算广泛存在于数值模拟、图计算等领域。其中,稀疏...
基于超图分区的分布式稀疏矩阵向量乘数据映射方法

本发明属于高性能并行计算领域,具体涉及一种基于超图分区的分布式稀疏矩阵向量乘数据映射方法。

背景技术:

1、稀疏矩阵运算广泛存在于数值模拟、图计算等领域。其中,稀疏矩阵向量乘是稀疏线性方程组求解、特征值计算及图算法中的核心计算操作,其执行效率往往成为制约系统性能的关键因素。随着稀疏矩阵规模不断扩大,单个处理节点的计算能力、存储容量和访存带宽难以满足计算需求,通常需要将计算任务划分并映射至分布式系统中的多个处理节点并行执行。然而,稀疏矩阵中非零元素的不规则分布容易造成处理节点间负载不均衡,并引发大量节点间数据通信,从而显著降低系统整体运行效率。因此,合理的数据分区与映射策略是提升分布式稀疏矩阵运算性能的关键。

2、传统的稀疏矩阵数据布局优化方法主要包括数据重排序与数据分区两类。数据重排序方法以反向 cuthill–mckee(rcm)、近似最小度排序等为代表,通过调整矩阵行列顺序降低矩阵带宽或改善数据局部性;数据分区方法则包括一维行列分区、二维块分区、循环或块循环分区及图分区等,主要依据非零元素数量或图边切割代价实现计算负载均衡。然而,数据重排序通常不直接决定任务在处理节点间的分配,传统分区方法也难以准确表征向量元素被多个处理节点共享的通信依赖,因而对通信数据量及节点间通信关系的优化能力有限。

3、分布式稀疏矩阵向量乘的数据分区与映射需要综合考虑计算负载和通信开销。其中,负载不平衡率依据各处理节点所分配的矩阵非零元素数量,衡量节点间计算负载的均衡程度;数据通信量表示完成计算所需在处理节点间传输的向量元素总量;数据通信次数表示存在数据依赖关系的处理节点对数量;最远通信距离表示存在数据依赖关系的节点对之间的最大拓扑距离。以上指标存在耦合,优化时相互制约。为此,本发明引入一种基于超图分区的数据映射方法,在保证负载均衡的同时,协同优化通信量、通信次数和最远通信距离。

技术实现思路

1、本发明提供了一种基于超图分区的分布式稀疏矩阵向量乘数据映射方法解决上述提到的技术问题,具体采用如下的技术方案:

2、一种基于超图分区的分布式稀疏矩阵向量乘数据映射方法,包含以下步骤:

3、依据稀疏矩阵a构建超图,其中  为顶点集合, 为超边集合,第i行对应顶点,且顶点权重,输入向量 对应超边,与之连接的所有顶点集合为;

4、基于递归二分框架对进行k分区,每次二分前将当前子超图与外部子超图的双向数据依赖建模为延迟网并合并至当前超图;

5、计算各顶点相对于左、右外部节点组的加权拓扑依赖得到方向偏好,将偏好最强顶点固定至对应子分区;

6、对当前超图进行二分区,使各分区负载满足负载均衡约束并最小化统一切割代价,所述统一切割代价由超边切割代价与延迟网切割代价组成。

7、进一步地,所述延迟网 的顶点集合为:

8、

9、其中为当前子超图的顶点集合, 为节点对应子超图的顶点集合。

10、进一步地,所述负载均衡约束为,其中分区负载,分区平均负载,ε为允许的最大负载不均衡率。

11、进一步地,所述统一切割代价,其中第一项为超边切割代价,用于优化节点间向量数据通信总量,第二项为延迟网切割代价,用于抑制通信依赖数目的增长,λ(n)和λ(l)分别为超边和延迟网跨越的分区数。

12、进一步地,所述方向偏好,其中,,为顶点v对外部节点的数据依赖强度, 和  为外部节点集合依据当前节点组的拓扑方向划分的子集。

13、进一步地,若δ(v)>0,优先将顶点v映射至左子节点组;

14、若δ(v)<0,优先将顶点v映射至右子节点组;

15、在不破坏负载均衡约束的条件下,将左、右方向偏好最强的顶点分别固定至相应子分区,再对当前超图进行二分区。

16、进一步地,所述顶点i的分区归属同时决定稀疏矩阵第i行、输入向量元素 以及输出向量元素  的所属处理节点;所述稀疏矩阵向量乘 作为迭代算法的核心环节被反复调用执行,期间矩阵a的稀疏结构保持不变,预处理阶段的分区映射结果用于优化整个算法流程的计算效率。

17、本发明所提供的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,将分布式系统中的稀疏矩阵向量乘运算抽象为超图模型,在数据分区映射时同时优化计算负载均衡以及节点间通信量、通信次数以及最远通信距离等关键技术指标,提升分布式系统计算效率。

18、本发明所提供的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,通过在超图递归二分区过程中引入延迟网建模节点间双向数据依赖,并引入了一种分区映射方向选择机制。该方法在保证节点间负载平衡以及减少节点间数据传输总量的基础上,可同时减少节点间数据依赖数量,并避免在递归分区过程中产生的不必要的远距离节点通信需求,从而提升分布式稀疏矩阵向量乘的执行效率。

1.一种基于超图分区的分布式稀疏矩阵向量乘数据映射方法,其特征在于,包含以下步骤:

2.根据权利要求1所述的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,其特征在于,

3.根据权利要求1所述的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,其特征在于,

4.根据权利要求1所述的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,其特征在于,

5.根据权利要求1所述的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,其特征在于,

6.根据权利要求1所述的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,其特征在于,

7.根据权利要求1所述的基于超图分区的分布式稀疏矩阵向量乘数据映射方法,其特征在于,