GraphHP: A hybrid platform for iterative graph processing

doi:10.3969/j.issn.1000-5641.2016.05.013

Abstract

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

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.

References

[ 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]	HU Yue, CAI Yong-li. Analyzing the spatial equity of urban parks’〖KG*6〗social service functioning quantitatively: A case study for the central area of Shanghai [J]. Journal of East China Normal University(Natural Sc, 2017, 2017(1): 91-103.
[2]	YUE Ming-shi. Cells of the weighted Coxeter group\\ $\textbf{(}\widetilde{\bm C}_{\bm n},\widetilde{\bm l}_{\textbf{2}\bm n}\textbf{)}$ in a certain quasi-split case [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(4): 1-10.
[3]	LI Mo-han. Oscillation of certain third-order variable delay damped dynamic equations on time scales [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(4): 11-24.
[4]	KAN Zeng-hui, LIU Chao-shun, LI Zhi-jun. Retrieval of land surface temperature based on Landsat-8 thermal infrared data and heat island effect analysis over the Taihu Lake region [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(4): 129-138.
[5]	FENG Yun-Qing, HOU Lei. High order interpolation function for surface contact problem [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(3): 9-20.
[6]	ZHENG Dao-Sheng. Effcient characterization for M{2,3},M{2,4} and M{2,3,4}and Mf2;3;4g [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(2): 9-19.
[7]	YUAN Yu-Ping, AN Zeng-Long. Support vector machine in the primal space based on\\ the ramp loss function\\[6mm [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(2): 20-29.
[8]	LYU Chang-Qing . The linear arboricity of upper-embedded graph and secondary upper-embedded graph [J]. Journal of East China Normal University(Natural Sc, 2015, 2015(1): 131-135.
[9]	YANG Pai, LIU Xiao-jun. On the kth derivatives of meromorphic functions and rational functions [J]. Journal of East China Normal University(Natural Sc, 2014, 2014(4): 8-17.
[10]	HOU Shuai PAN Wei. Weak signal DOA estimation method based on synthetic spectrum without prior knowledge of source number [J]. Journal of East China Normal University(Natural Sc, 2013, 2013(6): 102-111.
[11]	ZHAO Xian-feng, SHU Yong-lu, ZHOU Yun-hua. Subspace-supercyclicity and common subspace-supercyclic vectors [J]. Journal of East China Normal University(Natural Sc, 2012, 2012(1): 106-112, 120.
[12]	YAO Hong-liang. Local AT-algebras and Their Properties(English) [J]. Journal of East China Normal University(Natural Sc, 2006, 2006(5): 1-7.
[13]	SUN Ying, ZHU De-ming. Reversible Homoclinic and Periodic Orbits Near Heteroclinic Loop [J]. Journal of East China Normal University(Natural Sc, 2006, 2006(5): 13-23.
[14]	XIE Yuan-xi, TANG Jia-shi. Concise Approach for Solving Double Sine-Gordon Equation [J]. Journal of East China Normal University(Natural Sc, 2006, 2006(5): 24-26.
[15]	SHI Yu-ren, WANG Ying-hai, YANG Hong-juan, Lu Ke-pu, DUAN Wen-shan. Exact Solutions of Generalized Burgers' Equation with Variable Coefficients [J]. Journal of East China Normal University(Natural Sc, 2006, 2006(5): 27-33.