A communication-reduced and computation-balanced framework for fast graph computation
A communication-reduced and computation-balanced framework for fast graph computation作者机构：College of Mathematics and Computer Science FuZhou University Fuzhou 350116 China Wuhan National Laboratory for Optoelectronics School of Computer Science and Technology Huazhong University of Science and Technology Wuhan 430074 China Shenzhen Huazhong University of Science and Technology Research Institute Shenzhen 518300 China Department of Computer Science & Engineering University of Texas at Arlington Arlington TX 76019 USA
出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)
年 卷 期：2018年第12卷第5期
页 面：887-907页
核心收录：
学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 082903[工学-林产化学加工工程] 08[工学] 0829[工学-林业工程] 0802[工学-机械工程] 0835[工学-软件工程] 082201[工学-制浆造纸工程] 0701[理学-数学] 0822[工学-轻工技术与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 080201[工学-机械制造及其自动化]
基 金：supported by NSFC 61772216, Shenzhen science and technology plan project Wuhan application basic research project supported by Key Laboratory of Information Storage System, Ministry of Education and State Key Laboratory of Computer Architecture
主 题：graph computation communication decrease computation balance
摘 要：The bulk synchronous parallel （BSP） model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graphprocessing frameworks, such as Pregel, GPS and Giraph, routinely suffer from high communication costs. These high communication costs mainly stem from the fine-grained message-passing communication model. In order to address this problem, we propose a new computation model with low communication costs, called LCC-BSE We use this model to design and implement a high-performance distributed graphprocessing framework called LCC-Graph. This framework eliminates high communication costs in existing distributed graph-processing frameworks. Moreover, LCC-Graph also balances the computation workloads among all compute nodes by optimizing graph partitioning, significantly reducing the computation time for each superstep. Evaluation of LCC-Graph on a 32-node cluster, driven by real-world graph datasets, shows that it significantly outperforms existing distributed graph-processing frameworks in terms of runtime, particularly when the system is supported by a highbandwidth network. For example, LCC-Graph achieves an order of magnitude performance improvement over GPS and GraphLab.
维普期刊数据库