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

Research on Graph Partitioning in Heterogeneous Computing Environment

作　　者：李琪 李虎雄 钟将[2] 英昌甜 李青 LI Qi;LI Hu-Xiong;ZHONG Jiang;YING Chang-Tian;LI Qing(Department of Computer Science and Engineering,Shaoxing University,Shaoxing,Zhejiang 312000;Department of Computer Science,Chongqing University,Chongqing 400030)

机构地区：[1]绍兴文理学院计算机科学与工程系,浙江绍兴312000 [2]重庆大学计算机学院,重庆400030

出　　处：《计算机学报》2021年第8期1751-1766,共16页Chinese Journal of Computers

基　　金：国家自然科学基金青年科学基金项目(62002226);国家自然科学基金专项项目(6194100039);浙江省自然科学基金(LHQ20F020001);浙江省基础公益研究计划项目(LGG18F030003);绍兴文理学院校级科研项目研究成果(2019LG1004)资助。

摘　　要：复杂网络的研究已经广泛地应用到生物、计算机等各个学科领域.如今,网络规模十分巨大,如何对这些大规模图数据进行有效率的挖掘计算,是研究复杂网络的首要任务.并行计算技术是现在最成熟、应用最广、最可行的计算加速技术之一.而图划分技术是提高并行计算性能的有效手段.图划分问题的研究是随着实际应用的需求而驱动.针对异构计算环境下的分布式集群,本文提出了一种异构感知的流式图划分算法.该方法既考虑到集群中网络带宽及节点计算能力的不同,同时又考虑到了以InfiniBand为代表的高速网络环境下核之间的共享资源的竞争.实验以图算法BFS、SSSP和PageRank为例,相对于未考虑异构环境的流算法,图计算效率分别平均提高了38%、45.7%、61.8%.同时针对流式图划分过程中邻点缓存查找效率低下问题,本文又设计了一种邻边结构的缓存查找算法,在相同条件下,图划分的效率平均提高了13.4%.仿真实验结果表明,本文设计的异构感知图划分算法实现了异构集群环境下图计算效率的提升.Large graph datasets are becoming increasingly popular nowadays.For example,graphs like Web Graphs,Biological Networks,and Social Networks,are often at the scale of hundreds of billions or even a trillion edges,and they are continuously growing.How to mine and calculate these large-scale graph data efficiently is the primary task of studying complex network.Parallel computing technology is one of the most mature,widely used and feasible computing acceleration technologies.Graph partitioning is an effective way to improve the performance of parallel computing.The increasing popularity and ubiquity of various large graph datasets have caused renewed interest for graph partitioning.Existing graph partitioners either scale poorly against large graphs or disregard the impact of the underlying hardware topology.A few solutions have shown that the nonuniform network communication costs may affect the performance greatly.Since the cost of partitioning the entire graph is strictly prohibitive,there are some recent tentative works towards streaming graph partitioning which run faster,are easily parallelized,and can be incrementally updated.Most of the existing works on streaming partitioning assume that worker nodes within a cluster are homogeneous in nature.Unfortunately,this assumption does not always hold.Experiments show that these homogeneous algorithms suffer a significant performance degradation when running at heterogeneous environment.The research of graph partitioning is driven by the demand of practical application.Aiming at the distributed cluster in heterogeneous computing environment,we propose a streaming graph partitioning algorithm based on heterogeneous aware.The method not only considers the difference of network bandwidth and node compute ability in the cluster,but also considers the competition for shared resources between cores in high-speed network environment represented by InfiniBand.Taking BFS,SSSP and PageRank as examples,compared with the streaming algorithm without considering the heterogeneous

关 键 词：异构计算 图划分 云计算 复杂网络 图计算 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]