平台和负载特征感知的在线图分割算法

发布时间：2025-01-09 05:50

　　 分布式图计算在许多领域有着广泛的应用,图分割是分布式图计算的基础.已有分割算法大多只考虑图的简单拓扑特性,它们将图计算系统视为同构系统,或最多考虑CPU计算能力及通信带宽的不同.然而,目前包含GPU的异构计算系统已经越来越普遍,由于GPU独特的并行计算架构和并行计算模式,不考虑GPU计算特点的图分割算法不能获得异构环境下最优的分割方案.本文通过分析及实验发现,计算负载特性对于估算处理节点的图计算时间有很大的帮助.在此基础上,本文提出度变异系数和分片通达度两个负载特征参数,给出了通过数据集采样和离线测试获取负载特征参数到处理器负载计算时间的映射关系的实用方法,并结合以上工作实现了一个平台特性和负载特征感知的在线图分割算法.在真实图数据集上的测试表明,相比于工业界和学术界领先的图分割算法,本文提出的方法可获得最优的图分割方案,可令图计算系统的整体执行时间减少50%～70%.

【文章页数】：16 页

【部分图文】：

图8 采用不同图分割算法后全源最短路径的执行时间

图7采用不同图分割算法后PageRank的执行时间图9采用不同图分割算法后多源BFS的执行时间

图9 采用不同图分割算法后多源BFS的执行时间

图8采用不同图分割算法后全源最短路径的执行时间图10采用不同图分割算法后图路径匹配的执行时间

图1 0 采用不同图分割算法后图路径匹配的执行时间

图9采用不同图分割算法后多源BFS的执行时间可以看出，对于所有的图算法-图数据集组合，P&W＿Alg算法的分割效果最好，即在其生成的分割上运行图算法的时间最短．与METIS和HEA＿Alg生成的分割方案相比，P&W＿Alg生成的分割方案可使PageRank算法的执行时间平均缩短....

图1 1 3种分割算法下的4个节点上的总执行时间

可以看出，对于所有的图算法-图数据集组合，P&W＿Alg算法的分割效果最好，即在其生成的分割上运行图算法的时间最短．与METIS和HEA＿Alg生成的分割方案相比，P&W＿Alg生成的分割方案可使PageRank算法的执行时间平均缩短近50%，可使多源BFS算法的执行时间至少缩短....

本文编号：4025245