面向图计算的运行时系统的消息聚合技术

doi:10.11772/j.issn.1001-9081.2020081290

计算机应用 ›› 2021, Vol. 41 ›› Issue (4): 984-989.DOI: 10.11772/j.issn.1001-9081.2020081290

所属专题： CCF第35届中国计算机应用大会（CCF NCCA 2020）

• CCF第35届中国计算机应用大会（CCF NCCA 2020） • 上一篇下一篇

面向图计算的运行时系统的消息聚合技术

张鲁飞^1,2, 孙茹君², 秦芳²

1. 清华大学计算机科学与技术系, 北京 100084;
2. 数学工程与先进计算国家重点实验室, 江苏无锡 214125

收稿日期:2020-08-24 修回日期:2020-10-16 发布日期:2020-11-25 出版日期:2021-04-10
通讯作者: 张鲁飞
作者简介:张鲁飞（1986—），男，湖北襄阳人，工程师，博士，主要研究方向：人工智能、操作系统；孙茹君（1990—），女，甘肃兰州人，助理研究员，博士，主要研究方向：人工智能、运行时系统；秦芳（1975—），女，湖南零陵人，高级工程师，硕士，主要研究方向：操作系统。
基金资助:
国家自然科学基金资助项目（61972180）。

Message aggregation technology of runtime system for graph computing

ZHANG Lufei^1,2, SUN Rujun², QIN Fang²

1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi Jiangsu 214125, China

Received:2020-08-24 Revised:2020-10-16 Online:2020-11-25 Published:2021-04-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61972180).

摘要/Abstract

摘要： 图计算应用的通信模式以时空随机的点对点细粒度通信为主，但现有高性能计算机的网络系统应对大量细粒度通信时表现不佳，进而影响整体性能。虽然在应用层进行通信优化可以有效提升图计算应用性能，但这会给应用开发人员带来很大的负担，因此提出并实现结构动态的消息聚合技术，通过构建虚拟拓扑的方法在通信路径上增加中间点从而提升消息聚合的效果。传统的消息聚合策略一般仅在通信源或者目的地上进行，聚合机会有限，而所提技术通过灵活调整虚拟拓扑的结构和配置适应了不同硬件条件和应用特征。同时，还提出并实现了面向图计算的有消息聚合的运行时系统，这使得在程序迭代执行时可以动态选择参数，从而减少开发人员负担。在256节点规模的系统上实验的结果显示，使用所提消息聚合技术优化后的典型图计算应用的性能可得到100%以上的提升。

关键词: 图计算, 运行时系统, 可扩展性, 通信模型, 消息聚合

Abstract: The main communication mode of graph computing applications is spatiotemporally random point-to-point fine-grained communication. However, existing high-performance computer network systems perform poorly when dealing with a large number of fine-grained communications, which affect the overall performance. The communication optimization in application layer can improve the performance of graph computing application effectively, but this brings great burden to application developers. Therefore, a structure-dynamic message aggregation technique was proposed and implemented, which produced a lot of intermediate points in the communication path by building virtual topologies, so as to greatly improve the effect of message aggregation. By contrast, the traditional message aggregation strategy generally performed only at the communication source or destination with limited aggregation chances. In addition, this proposed technique adapted different kinds of hardware conditions and application features by flexibly adjusting the structure and configuration of the virtual topology. At the same time, the runtime system with message aggregation for graph computing was proposed and implemented, which allowed the runtime system to dynamically select parameters when executing iterations, so as to reduce the burden of developers. Experimental results on a system with 256 nodes show that typical graph computing application performance can achieve more than 100% improvement after optimized by the proposed message aggregation technique.

Key words: graph computing, runtime system, scalability, communication model, message aggregation

中图分类号:

TP311

张鲁飞, 孙茹君, 秦芳. 面向图计算的运行时系统的消息聚合技术[J]. 计算机应用, 2021, 41(4): 984-989.

ZHANG Lufei, SUN Rujun, QIN Fang. Message aggregation technology of runtime system for graph computing[J]. Journal of Computer Applications, 2021, 41(4): 984-989.

参考文献

[1] 王虹旭, 吴斌, 刘旸. 基于Spark的并行图数据分析系统[J]. 计算机科学与探索,2015,9(9):1066-1074.(WANG H X,WU B, LIU Y. Parallel graph data analysis system based on Spark[J]. Journal of Frontiers of Computer Science and Technology,2015,9(9):1066-1074.)
[2] HOEFLER T, SCHNEIDER T. Optimization principles for collective neighborhood communications[C]//Proceedings of the 2012 International Conference for High Performance Computing, Networking, Storage and Analysis. Piscataway:IEEE, 2012:1-10.
[3] LU Y,CHENG J,YAN D,et al. Large-scale distributed graph computing systems:an experimental evaluation[J]. Proceedings of the VLDB Endowment,2014,8(3):281-292.
[4] LUMSDAINE A, GREGOR D, HENDRICKSON B, et al. Challenges in parallel graph processing[J]. Parallel Processing Letters,2007,17(1):5-20.
[5] XIE C, YAN L, LI W, et al. Distributed power-law graph computing:theoretical and empirical analysis[C]//Proceedings of the 27th International Conference on Neural Information Processing Systems. Cambridge:MIT Press,2014:1673-1681.
[6] MALEWICZ G,AUSTERN M H,BIK A J C,et al. Pregel:a system for large-scale graph processing[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York:ACM,2010:135-146.
[7] SALIHOGLU S,WIDOM J. GPS:a graph processing system[C]//Proceedings of the 25th International Conference on Scientific and Statistical Database Management. New York:ACM,2013:No. 22.
[8] EDMONDS N,WILLCOCK J,LUMSDAINE A. Expressing graph algorithms using generalized active messages[C]//Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York:ACM,2013:289-290.
[9] AVERY C. Giraph:large-scale graph processing infrastructure on Hadoop[J]. Proceedings of the Hadoop Summit,2011,11(3):5-9.
[10] WILLCOCK J J,HOEFLER T,EDMONDS N G,et al. Active pebbles:parallel programming for data-driven applications[C]//Proceedings of the 2011 International Conference on Supercomputing. New York:ACM,2011:235-244.
[11] NELSON J,HOLT B,MYERS B,et al. Latency-tolerant software distributed shared memory[C]//Proceedings of the 2015 USENIX Annual Technical Conference. Berkeley:USENIX Association, 2015:291-305.
[12] FIDEL A,AMATO N M,RAUCHWERGER L. The STAPL parallel graph library[C]//Proceedings of the 2012 International Workshop on Languages and Compilers for Parallel Computing. Berlin:Springer,2012:46-60.
[13] KUMAR S,SABHARWAL Y,GARG R,et al. Optimization of all-to-all communication on the Blue Gene/L supercomputer[C]//Proceedings of the 37th International Conference on Parallel Processing. Piscataway:IEEE,2008:320-329.
[14] LIN H,ZHU X,YU B,et al. ShenTu:processing multi-trillion edge graphs on millions of cores in seconds[C]//Proceedings of the 2018 International Conference for High Performance Computing, Networking, Storage and Analysis. Piscataway:IEEE,2018:706-716.
[15] WESOLOWSKI L, VENKATARAMAN R, GUPTA A, et al. TRAM:optimizing fine-grained communication with topological routing and aggregation of messages[C]//Proceedings of the 43rd International Conference on Parallel Processing. Piscataway:IEEE,2014:211-220.
[16] DI STEFANO L, BULGARELLI A. A simple and efficient connected components labeling algorithm[C]//Proceedings of the 10th International Conference on Image Analysis and Processing. Piscataway:IEEE,1999:322-327.
[17] CHAKRABARTI D, ZHAN Y, FALOUTSOS C. R-MAT:a recursive model for graph mining[C]//Proceedings of the 2004 SIAM International Conference on Data Mining. Philadelphia, PA:SIAM,2004:442-446.
[18] SESHADHRI C,PINAR A,KOLDA T G. An in-depth study of stochastic Kronecker graphs[C]//Proceedings of the IEEE 11th International Conference on Data Mining. Piscataway:IEEE, 2011:587-596.
[19] GREGOR D,LUMSDAINE A. Lifting sequential graph algorithms for distributed-memory parallel computation[J]. ACM SIGPLAN Notices,2005,40(10):423-437.

面向图计算的运行时系统的消息聚合技术

Message aggregation technology of runtime system for graph computing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李皎, 张秀山, 宁远航. 降低跨分片交易比例的区块链分片方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1889-1896.
[2]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[3]	孙栋, 王彪, 徐云. 基于RDMA的区块传输机制设计与实现[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 484-489.
[4]	史志才, 王益涵, 张晓梅, 陈珊珊, 陈计伟. 可扩展及可证安全的射频识别认证协议[J]. 计算机应用, 2019, 39(3): 774-778.
[5]	陈婉杰, 盛益强. 基于网络表示学习的非单一维度的社区发现算法[J]. 计算机应用, 2019, 39(12): 3467-3475.
[6]	肖文, 胡娟. 基于数据集稀疏度的频繁项集挖掘算法性能分析[J]. 计算机应用, 2018, 38(4): 995-1000.
[7]	吴文燕, 姜鑫, 王晓锋, 刘渊. 虚拟化与数字仿真融合的多尺度网络复现技术[J]. 计算机应用, 2018, 38(3): 746-752.
[8]	金鹏飞, 牛保宁, 张兴忠. 高效的多关键词匹配最优路径查询算法KSRG[J]. 计算机应用, 2017, 37(2): 352-359.
[9]	赵军, 徐晓燕. 基于GraphX的分布式幂迭代聚类[J]. 计算机应用, 2016, 36(10): 2710-2714.
[10]	韩国梁, 盛茂家, 包丛笑, 李星. IPv4网络与IPv6互联网的无状态通信机制[J]. 计算机应用, 2015, 35(8): 2113-2117.
[11]	周晓云, 覃雄派, 王秋月. 大数据评测基准的研发现状与趋势[J]. 计算机应用, 2015, 35(4): 1137-1142.
[12]	代亮许宏科陈婷钱超粱殿鹏. 基于MapReduce的多元线性回归预测模型[J]. 计算机应用, 2014, 34(7): 1862-1866.
[13]	熊焕亮曾国荪吴沧海匡桂娟何火娇. 延迟可扩展性与并行执行时间的关系[J]. 计算机应用, 2014, 34(3): 663-667.
[14]	张顺陈海进. 轻量级的无线射频识别安全认证协议[J]. 计算机应用, 2012, 32(07): 2010-2014.
[15]	胡红宇艾灵仙. 安全高效的群组密钥协商协议[J]. 计算机应用, 2010, 30(9): 2401-2403.