文献类型：期刊文献

中文题名：异构计算环境中图划分算法的研究

英文题名：Research on Graph Partitioning in Heterogeneous Computing Environment

作者：李琪[1];李虎雄[1];钟将[2];英昌甜[1];李青[2]

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

年份：2021

卷号：44

期号：8

起止页码：1751

中文期刊名：计算机学报

外文期刊名：Chinese Journal of Computers

收录：CSTPCD、、CSCD2021_2022、EI(收录号：20213210756260)、Scopus、北大核心、CSCD、北大核心2020

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

语种：中文

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

外文关键词：heterogeneous computing;graph partition;cloud computing;complex network;graph computing

中文摘要：复杂网络的研究已经广泛地应用到生物、计算机等各个学科领域.如今,网络规模十分巨大,如何对这些大规模图数据进行有效率的挖掘计算,是研究复杂网络的首要任务.并行计算技术是现在最成熟、应用最广、最可行的计算加速技术之一.而图划分技术是提高并行计算性能的有效手段.图划分问题的研究是随着实际应用的需求而驱动.针对异构计算环境下的分布式集群,本文提出了一种异构感知的流式图划分算法.该方法既考虑到集群中网络带宽及节点计算能力的不同,同时又考虑到了以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 environment,the efficiency of graph computing is improved by 38%,45.7%and 61.8%,respectively.At the same time,in the process of streaming graph partitioning,aiming at the low efficiency of searching neighbor vertices in the cache,we design a cache searching algorithm with adjacent edge structure,which improves the efficiency of graph partitioning by 13.4%on average under the same conditions.Extensive experiments are conducted on a moderate sized computing cluster with real-world web and social network graphs.The results demonstrate that the proposed approach achieves significant improvement compared with the state-of-the-art solutions.