GraphHP:一个图迭代处理的混合平台

doi:10.3969/j.issn.1000-5641.2016.05.013

摘要/Abstract

摘要：

BSP(Bulk Synchronous Parallel, BSP)计算模型是建立大规模迭代式图处理分布式系统的重要基础. 现有平台(如 Pregel、Giraph、Hama)虽然已经实现了较高的可扩展性, 但主机之间高频同步和通信负荷严重影响了并行计算的效率. 为了解决这个关键性问题, 本文提出了一种基于混合式模型的执行平台 GraphHP(Graph Hybrid Processing). 它不仅继承了以顶点为中心的 BSP 编程接口, 而且能够显著减少同步和通信负荷. 通过在图分区内部和分区之间建立混合执行模型, GraphHP 实现了伪超步迭代计算, 把分区内部计算从分布式同步和通信中分离出来. 这种混合执行模型不需要繁重的调度算法或者以图为中心的串行算法, 就能有效减少同步和通信负荷. 最后, 本文评估了经典的 BSP 应用在 GraphHP 平台的实现方式. 实验表明它比现有的 BSP 实现平台效率更高. 本文提出的 GraphHP 平台虽然是基于Hama 实现的, 但它很容易迁移到其他的 BSP 平台.

关键词: 图迭代, 分布式计算, BSP, GraphHP

Abstract:

BSP (Bulk Synchronous Parallel) computing model is an important foundation for the establishment of a large-scale iterative graph processing distributed system. Existing platforms (e.g., Pregel, Giraph, and Hama) have achieved a high scalability, but the high frequency synchronization and communication load between the hosts have seriously affected the efficiency of parallel computing. In order to solve this key problem, this paper proposes a hybrid model based on GraphHP (Graph Hybrid Processing). It not only inherits the BSP programming interface with the vertex as the center, but also can significantly reduce the synchronization and communication load. By establishing the hybrid execution model between the interior and the interval partition of the graph, the GraphHP realizes the pseudo super step iteration calculation, and separates the internal computation from the distributed synchronization and communication. This hybrid execution model does not need heavy scheduling algorithm or the serial algorithm can effectively reduce the synchronization and communication load. Finally, this paper evaluates the implementation of the classic BSP application in the GraphHP platform, and the experiment shows that it is more efficient than the existing BSP platform. Although the GraphHP platform proposed in this paper is based on Hama, it is easy to migrate to other BSP platforms.

Key words: graph iterative, distributed computation, BSP, GraphHP

苏静, 索博, 陈群, 潘魏, 李战怀. GraphHP:一个图迭代处理的混合平台[J]. 华东师范大学学报(自然科学版), doi: 10.3969/j.issn.1000-5641.2016.05.013.

SU Jing, SUO Bo, CHEN Qun, PAN Wei, LI Zhan-huai. GraphHP: A hybrid platform for iterative graph processing[J]. Journal of East China Normal University(Natural Sc, doi: 10.3969/j.issn.1000-5641.2016.05.013.

参考文献

[ 1 ] SALIHOGLU S, WIDOM J. Optimizing graph algorithms on pregel-like systems [J]. Proceedings of the VLDB Endowment, 2014, 7(7): 577-588.
[ 2 ] SALIHOGLU S, WIDOM J. GPS: A graph processing system [C]//Proceedings of the 25th International Conference on Scientific and Statistical Database Management. ACM, 2013, Article No 22, doi: 10.1145/2484838.2484843.
[ 3 ] BAO N T, SUZUMURA T. Towards highly scalable pregel-based graph processing platform with x10 [C]//Proceedings of the 22nd International Conference on World Wide Web. ACM, 2013: 501-508.
[ 4 ] CHEN R S, YANG M, WENG X T, et al. Improving large graph processing on partitioned graphs in the cloud [C]//Proceedings of the 3rd ACM Symposium on Cloud Computing. ACM, 2012, Article No 3, doi: 10.1145/2391229.2391232.
[ 5 ] GOUDREAU M W, LANG K, RAO S B, et al. Portable and efficient parallel computing using the bsp model [J]. Computers IEEE Transactions on, 1999, 48(7): 670-689.
[ 6 ] HILL J M D, MCCOL B, STEFANESCU D C, et al. BSPlib: The BSP programming library [J]. Parallel Computing, 1998, 24(14): 1947-1980.
[ 7 ] GREGOR D, LUMSDAINE A. The Parallel BGL: A generic library for distributed graph computations [C]//Proceedings of the Parallel Object-Oriented Scientific Computing (POOSC). 2005: 1-18.
[ 8 ] CHAN A, DEHNE F. CGMGRAPH/CGMLIB: Implementing and testing CGM graph algorithms on PC clusters and shared memory machines [J]. Lecture Notes in Computer Science, 2003, 2840: 117-125.
[ 9 ] WANG G Z, XIE W L, DEMERS A, et al. Asynchronous large-scale graph processing made easy [C]//Proceedings of the 6th Biennial Conference on Innovative Data Systems Research (CIDR). 2013: 58-70.
[10] SHAO B, WANG H, LI Y. Trinity: A distributed graph engine on a memory cloud [C]//Proceedings of the ACM-SIGMOD International Conference on Management of Data. ACM, 2013: 505-516.
[11] CHENG R, HONG J, KYROLA A, et al. Kineograph: Taking the pulse of a fast-changing and connected world [C]//Proceedings of the 7th ACM European Conference on Computer Systems. ACM, 2012: 85-98.
[12] DEMETRESCU C. USA road network [EB/OL]. (2005-10-12)[2016-04-01]. http://www.dis.uniroma1.it/challenge9/download.shtml.
[13] DAVIS T. The University of Florida sparse matrix collection [EB/OL]. (2011-10-13)[2016-04-01]. http://www.cise.ufl.edu/research/sparse/matrices/.
[14] KARYPIS G, KUMAR V. A fast and high quality multilevel scheme for partitioning irregular graphs [J]. SIAM J Sci Comput, 1998, 20(1): 359-392.
[15] KARYPIS G, KUMAR V. A coarse-grain parallel formulation of multilevel k-way graph partitioning algorithm [C]//Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing. 1997: 1-12.
[16] TIAN Y Y, BALMIN A, CORSTEN S A, et al. From “think like a vertex” to “think like a graph” [J]. Proceedings of the VLDB Endowment, 2013, 7(3): 193-204.
[17] CHERKASSKY B V, GOLDBERG A V, RADZIK T. Shortest paths algorithms: Theory and experimental evaluation [J]. Mathematical Programming, 1996, 73(2): 129-174.
[18] ANDERSON T, OWICKI S, SAXE J, et al. High-speed switch scheduling for local-area networks [J]. ACM Sigplan Notices, 1993, 11(4): 319-352.
[19] KHAYYAT Z, AWARA K, ALONAZI A, et al. Mizan: A system for dynamic load balancing in large-scale graph processing [C]//Proceedings of the 8th ACM European Conference on Computer Systems. ACM, 2013: 169-182.

[1]	徐阳, 王志杰, 钱诗友. 基于分布式平台Spark的空间文本查询分析[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 120-134,153.
[2]	潘宇晨, 李宇明, 张春熙, 张蓉, 洪道诚. 基于分布式数据库Cedar的高效工单管理系统设计与实现[J]. 华东师范大学学报(自然科学版), 2018, 2018(3): 88-96.
[3]	陈明珠, 王晓桐, 房俊华, 张蓉. 支持非等值连接的分布式数据流处理系统[J]. 华东师范大学学报(自然科学版), 2017, 2017(5): 11-19.
[4]	贺磊，徐静. 多元线性模型中回归系数矩阵的可估函数和协方差阵的同时Bayes估计及优良性[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 1-10.
[5]	陈媛媛，牟善志，王国平. 一些图的无符号拉普拉斯谱半径[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 26-31.
[6]	赵天义. Gauss-Bonnet引力中黑洞的膜范式[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 64-70.
[7]	张顺尧，陈易. 基于城市微气候测析的建筑外部空间围合度研究——以上海市大连路总部研发集聚区国歌广场为例[J]. 华东师范大学学报(自然科学版), 2016, 2016(6): 1-26.
[8]	陈文, 张凯, 钱海峰. 更高效的选择密文安全基于身份的双接收者加密方案[J]. 华东师范大学学报(自然科学版), 2016, 2016(6): 145-156.
[9]	郭凤鸣, 李兵. 远距离停车场系统无线信道传播损耗分析[J]. 华东师范大学学报(自然科学版), 2016, 2016(6): 173-181.
[10]	刘艳. 气候变化下我国蔓藓属(Meteorium)适生分布的预测[J]. 华东师范大学学报(自然科学版), 2016, 2016(6): 192-202.
[11]	储佳佳, 郭进伟, 刘柏众, 张晨东, 钱卫宁. 高可用数据库系统中的分布式一致性协议[J]. 华东师范大学学报(自然科学版), 2016, 2016(5): 1-9.
[12]	胡爽, 周欢, 钱卫宁. 内存数据库事务提交的关键技术与挑战[J]. 华东师范大学学报(自然科学版), 2016, 2016(5): 18-26.
[13]	隆飞, 翁海星, 高明, 张召. 基于LSM Tree的分布式索引实现[J]. 华东师范大学学报(自然科学版), 2016, 2016(5): 36-44.
[14]	王敏, 彭承晨, 李蓉蓉, 彭煜玮. 基于数据关联的分布式对象代理数据库划分方法[J]. 华东师范大学学报(自然科学版), 2016, 2016(5): 45-55.
[15]	钱招明, 王雷, 余晟隽, 宫学庆. 分布式系统中 Semi-Join 算法的实现[J]. 华东师范大学学报(自然科学版), 2016, 2016(5): 75-80.