首页|异构计算环境中图划分算法的研究

异构计算环境中图划分算法的研究

Research on Graph Partitioning in Heterogeneous Computing Environment

扫码查看
原文链接
  • NETL
  • NSTL
  • 维普
  • 万方数据
复杂网络的研究已经广泛地应用到生物、计算机等各个学科领域.如今,网络规模十分巨大,如何对这些大规模图数据进行有效率的挖掘计算,是研究复杂网络的首要任务.并行计算技术是现在最成熟、应用最广、最可行的计算加速技术之一.而图划分技术是提高并行计算性能的有效手段.图划分问题的研究是随着实际应用的需求而驱动.针对异构计算环境下的分布式集群,本文提出了一种异构感知的流式图划分算法.该方法既考虑到集群中网络带宽及节点计算能力的不同,同时又考虑到了以InfiniBand为代表的高速网络环境下核之间的共享资源的竞争.实验以图算法BFS、SSSP和PageRank为例,相对于未考虑异构环境的流算法,图计算效率分别平均提高了38％、45.7％、61.8％.同时针对流式图划分过程中邻点缓存查找效率低下问题,本文又设计了一种邻边结构的缓存查找算法,在相同条件下,图划分的效率平均提高了 13.4％.仿真实验结果表明,本文设计的异构感知图划分算法实现了异构集群环境下图计算效率的提升.

李琪、李虎雄、钟将、英昌甜、李青

展开 >

绍兴文理学院计算机科学与工程系 浙江绍兴 312000

重庆大学计算机学院 重庆 400030

异构计算 图划分 云计算 复杂网络 图计算

620022266194100039LHQ20F020001LGG18F0300032019LG1004

2021

10.11897/SP.J.1016.2021.01751

计算机学报
中国计算机学会 中国科学院计算技术研究所

计算机学报

CSTPCDCSCD北大核心
影响因子：3.18
ISSN：0254-4164
年,卷(期)：2021.44(8)
  • 1
  • 2