计算机科学技术学报 ›› 2021,Vol. 36 ›› Issue (4): 778-791.doi: 10.1007/s11390-021-1356-2

所属专题: Data Management and Data Mining

• • 上一篇    下一篇

TransGPerf:利用迁移学习建模分布式图计算性能

Songjie Niu, Student Member, CCF, and Shimin Chen*, Senior Member, IEEE   

  1. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100049, China
  • 收稿日期:2021-02-02 修回日期:2021-07-10 出版日期:2021-07-05 发布日期:2021-07-30
  • 通讯作者: Shimin Chen E-mail:chensm@ict.ac.cn
  • 作者简介:Songjie Niu received her B.E. degree from Beijing Institute of Technology, Beijing, in 2014. She is a Ph.D. candidate at Institute of Computing Technology, Chinese Academy of Sciences, Beijing. Her research interests include graph computation, database systems, and big data processing. She is a student member of CCF.

TransGPerf: Exploiting Transfer Learning for Modeling Distributed Graph Computation Performance

Songjie Niu, Student Member, CCF, and Shimin Chen*, Senior Member, IEEE        

  1. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2021-02-02 Revised:2021-07-10 Online:2021-07-05 Published:2021-07-30
  • Contact: Shimin Chen E-mail:chensm@ict.ac.cn
  • About author:Songjie Niu received her B.E. degree from Beijing Institute of Technology, Beijing, in 2014. She is a Ph.D. candidate at Institute of Computing Technology, Chinese Academy of Sciences, Beijing. Her research interests include graph computation, database systems, and big data processing. She is a student member of CCF.

1、研究背景(context)。
图数据模型已被广泛用于分析包括网络图、社交网络和语义网在内的大范围真实数据集。由于性能优势和快速增加的存储容量,分布式内存图处理已成为一种很有前景的图数据分析的解决方案。近年来,越来越多的分布式内存图处理平台被提出。分布式内存图处理的性能建模可以帮助执行时间预测、资源规划、性能分析和计算优化。
2、目的(Objective):准确描述该研究的目的,说明提出问题的缘由,表明研究的范围和重要性。
对分布式图计算的性能进行建模具有挑战性。显式的公式形式很难捕捉系统中多样的因素和它们复杂的交互作用。统计学习方法需要大量的训练样本来生成准确的预测模型。然而,运行所需的图计算测试以获得训练样本是非常耗时的。我们的目标是利用来自源场景的先验知识,通过可操纵数量的训练数据,对目标图计算场景的性能进行建模。
3、方法(Method):简要说明研究课题的基本设计,结论是如何得到的。
我们提出了一种用于分布式内存图处理性能建模的迁移学习方案TransGPerf,主要部件如下。基本建模:综合考虑影响分布式内存图处理性能的各种因素,在收集的大量训练样本的基础上,建立了一个源MLP模型;迁移建模:迁移网络结构在源MLP模型后增加残差层,以捕捉目标场景与源场景预测函数的差异;特征提取器:提出了一组具有代表性的特征来捕获分布式内存图处理的特性。
4、结果(Result&Findings):简要列出该研究的主要结果,有什么新发现,说明其价值和局限。叙述要具体、准确,尽量给出量化数据而不只是定性描述,并给出结果的置信值(如果有)。
实验结果表明,我们提出的方法TransGPerf能够为广泛的图计算任务产生较为准确的性能模型。它对PowerGraph和GraphX性能建模的MAPE分别达到了9.2%和7.1%,对迁移到六种具有代表性算法之一的MAPE达到了6.4-16.9%。TransGPerf的模型效果优于文献中提出的其他应用的迁移学习方法。对于PowerGraph和GraphX,MAPE分别降低了7.3-42.4%和3.88-25.69%;对于迁移到其中一种算法,MAPE最多降低了36.4%。
5、结论(Conclusions):简要地说明经验,论证取得的正确观点及理论价值或应用价值,是否还有与此有关的其它问题有待进一步研究,是否可推广应用,其应用价值如何?
图计算的性能建模是一个具有挑战性的新领域。我们提出了一种新的迁移学习方法TransGPerf,它利用分布式内存图处理源域的知识,来为具有有限样本的目标域建立性能模型。它降低了运行大量目标任务的成本。实验结果表明,TransGPerf能有效地支持广泛的分布式内存图处理迁移学习任务。

关键词: 性能建模, 分布式图计算, 深度学习, 迁移学习

Abstract: It is challenging to model the performance of distributed graph computation. Explicit formulation cannot easily capture the diversified factors and complex interactions in the system. Statistical learning methods require a large number of training samples to generate an accurate prediction model. However, it is time-consuming to run the required graph computation tests to obtain the training samples. In this paper, we propose TransGPerf, a transfer learning based solution that can exploit prior knowledge from a source scenario and utilize a manageable amount of training data for modeling the performance of a target graph computation scenario. Experimental results show that our proposed method is capable of generating accurate models for a wide range of graph computation tasks on PowerGraph and GraphX. It outperforms transfer learning methods proposed for other applications in the literature.

Key words: performance modeling, distributed graph computation, deep learning, transfer learning

[1] Malewicz G, Austern M H, Bik A J C, Dehnert J C, Horn I, Leiser N, Czajkowski G. Pregel:A system for large-scale graph processing. In Proc. the 2010 ACM SIGMOD International Conference on Management of Data, June 2010, pp.135-146. DOI:10.1145/1807167.1807184.
[2] Gonzalez J E, Low Y, Gu H, Bickson D, Guestrin C. PowerGraph:Distributed graph-parallel computation on natural graphs. In Proc. the 10th USENIX Symposium on Operating Systems Design and Implementation, October 2012, pp.17-30.
[3] Xin R S, Gonzalez J E, Franklin M J, Stoica I. GraphX:A resilient distributed graph system on Spark. In Proc. the 1st International Workshop on Graph Data Management Experiences and Systems, June 2013, Article No. 2. DOI:10.1145/2484425.2484427.
[4] Niu S, Chen S. Optimizing CPU cache performance for Pregel-like graph computation. In Proc. the 31st IEEE International Conference on Data Engineering Workshops, April 2015, pp.149-154. DOI:10.1109/ICDEW.2015.7129568.
[5] Han M, Daudjee K, Ammar K, Özsu M T, Wang X, Jin T. An experimental comparison of Pregel-like graph processing systems. Proc. VLDB Endow., 2014, 7(12):1047-1058. DOI:10.14778/2732977.2732980.
[6] Iosup A, Hegeman T, Ngai W L et al. LDBC graphalytics:A benchmark for large-scale graph analysis on parallel and distributed platforms. Proc. VLDB Endow., 2016, 9(13):1317-1328. DOI:10.14778/3007263.3007270.
[7] Ngai W L, Hegeman T, Heldens S, Iosup A. Granula:Toward fine-grained performance analysis of largescale graph processing platforms. In Proc. the 5th International Workshop on Graph Data-management Experiences & Systems, May 2017, Article No. 8. DOI:10.1145/3078447.3078455.
[8] Herodotou H, Lim H, Luo G, Borisov N, Dong L, Cetin F B, Babu S. Starfish:A self-tuning system for big data analytics. In Proc. the 5th Biennial Conference on Innovative Data Systems Research, January 2011, pp.261-272.
[9] Venkataraman S, Yang Z, Franklin M J, Recht B, Stoica I. Ernest:Efficient performance prediction for large-scale advanced analytics. In Proc. the 13th USENIX Symposium on Networked Systems Design and Implementation, March 2016, pp.363-378.
[10] Pan S J, Yang Q. A survey on transfer learning. IEEE Trans. Knowledge and Data Engineering, 2010, 22(10):1345-1359. DOI:10.1109/TKDE.2009.191.
[11] Weiss K R, Khoshgoftaar T M, Wang D. A survey of transfer learning. J. Big Data, 2016, 3:Article No. 9. DOI:10.1186/s40537-016-0043-6.
[12] Tzeng E, Hoffman J, Zhang N, Saenko K, Darrell T. Deep domain confusion:Maximizing for domain invariance. arXiv:1412.3474, 2014. https://arxiv.org/pdf/1412.3474.pdf, May 2021.
[13] Long M, Cao Y, Wang J, Jordan M I. Learning transferable features with deep adaptation networks. In Proc. the 32nd International Conference on Machine Learning, July 2015, pp.97-105.
[14] Long M, Zhu H, Wang J, Jordan M I. Deep transfer learning with joint adaptation networks. In Proc. the 34th International Conference on Machine Learning, August 2017, pp.2208-2217.
[15] Sun B, Saenko K. Deep CORAL:Correlation alignment for deep domain adaptation. In Proc. the 2016 European Conference on Computer Vision Workshops, October 2016, pp.443-450. DOI:10.1007/978-3-319-49409-835.
[16] He K, Zhang X, Ren S, Sun J. Deep residual learning for image recognition. In Proc. the 2016 IEEE Conference on Computer Vision and Pattern Recognition, June 2016, pp.770-778. DOI:10.1109/CVPR.2016.90.
[17] Barker K J, Pakin S, Kerbyson D J. A performance model of the Krak hydrodynamics application. In Proc. the 2006 International Conference on Parallel Processing, August 2006, pp.245-254. DOI:10.1109/ICPP.2006.11.
[18] Kerbyson D J, Alme H J, Hoisie A, Petrini F, Wasserman H J, Gittings M L. Predictive performance and scalability modeling of a large-scale application. In Proc. the 2001 ACM/IEEE Conference on Supercomputing, November 2001, Article No. 37. DOI:10.1145/582034.582071.
[19] Sundaram-Stukel D, Vernon M K. Predictive analysis of a wavefront application using logGP. In Proc. the 1999 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May 1999, pp.141-150. DOI:10.1145/301104.301117.
[20] Bhattacharyya A, Hoefler T. PEMOGEN:Automatic adaptive performance modeling during program runtime. In Proc. the 23rd International Conference on Parallel Architectures and Compilation, August 2014, pp.393-404. DOI:10.1145/2628071.2628100.
[21] Bhattacharyya A, Kwasniewski G, Hoefler T. Using compiler techniques to improve automatic performance modeling. In Proc. the 2015 International Conference on Parallel Architectures and Compilation, October 2015, pp.468-479. DOI:10.1109/PACT.2015.39.
[22] Calotoiu A, Beckingsale D, Earl C W, Hoefler T, Karlin I, Schulz M, Wolf F. Fast multi-parameter performance modeling. In Proc. the 2016 IEEE International Conference on Cluster Computing, September 2016, pp.172-181. DOI:10.1109/CLUSTER.2016.57.
[23] Sun J, Sun G, Zhan S, Zhang J, Chen Y. Automated performance modeling of HPC applications using machine learning. IEEE Trans. Computers, 2020, 69(5):749-763. DOI:10.1109/TC.2020.2964767.
[24] Pan S J, Tsang I W, Kwok J T, Yang Q. Domain adaptation via transfer component analysis. IEEE Trans. Neural Networks, 2011, 22(2):199-210. DOI:10.1109/TNN.2010.2091281.
[25] Sun B, Feng J, Saenko K. Return of frustratingly easy domain adaptation. In Proc. the 30th AAAI Conference on Artificial Intelligence, February 2016, pp.2058-2065.
[26] Tzeng E, Hoffman J, Darrell T, Saenko K. Simultaneous deep transfer across domains and tasks. In Proc. the 2015 IEEE International Conference on Computer Vision, December 2015, pp.4068-4076. DOI:10.1109/ICCV.2015.463.
[27] Long M, Zhu H, Wang J, Jordan M I. Unsupervised domain adaptation with residual transfer networks. In Proc. the 30th Annual Conference on Neural Information Processing Systems, December 2016, pp.136-144.
[28] Leskovec J, Sosič R. SNAP:A general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol., 2016, 8(1):Article No. 1. DOI:10.1145/2898361.
[29] Chakrabarti D, Zhan Y, Faloutsos C. R-MAT:A recursive model for graph mining. In Proc. the 4th SIAM International Conference on Data Mining, April 2004, pp.442-446. DOI:10.1137/1.9781611972740.43.
[30] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. In Proc. the 1999 ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, August 30-September 3, 1999, pp.251-262. DOI:10.1145/316188.316229.
[31] Leskovec J, Chakrabarti D, Kleinberg J M, Faloutsos C. Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication. In Proc. the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, October 2005, pp.133-145. DOI:10.1007/1156412617.
[32] Park H, Kim M. TrillionG:A trillion-scale synthetic graph generator using a recursive vector model. In Proc. the 2017 ACM International Conference on Management of Data, May 2017, pp.913-928. DOI:10.1145/3035918.3064014.
[33] Boldi P, Vigna S. The webgraph framework I:Compression techniques. In Proc. the 13th International Conference on World Wide Web, May 2004, pp.595-602. DOI:10.1145/988672.988752.
[1] 王新峰、周翔、饶家华、张柱金、杨跃东. 基于迁移学习的DNA甲基化缺失数据补齐[J]. 计算机科学技术学报, 2022, 37(2): 320-329.
[2] 张鑫, 陆思源, 王水花, 余翔, 王甦菁, 姚仑, 潘毅, 张煜东. 通过新型深度学习架构诊断COVID-19肺炎[J]. 计算机科学技术学报, 2022, 37(2): 330-343.
[3] Songjie Niu, Dongyan Zhou. SOOP:支持二阶随机游走的高效的分布式图计算[J]. 计算机科学技术学报, 2021, 36(5): 985-1001.
[4] Sheng-Luan Hou, Xi-Kun Huang, Chao-Qun Fei, Shu-Han Zhang, Yang-Yang Li, Qi-Lin Sun, Chuan-Qing Wang. 基于深度学习的文本摘要研究综述[J]. 计算机科学技术学报, 2021, 36(3): 633-663.
[5] Lan Chen, Juntao Ye, Xiaopeng Zhang. 基于多特征超分网络的布料褶皱合成[J]. 计算机科学技术学报, 2021, 36(3): 478-493.
[6] Yu-Jie Yuan, Yukun Lai, Tong Wu, Lin Gao, Li-Gang Liu. 回顾形状编辑技术:从几何角度到神经网络方法[J]. 计算机科学技术学报, 2021, 36(3): 520-554.
[7] Wei Du, Yu Sun, Hui-Min Bao, Liang Chen, Ying Li, Yan-Chun Liang. 基于迁移学习与深度学习的人类血液分泌蛋白预测框架[J]. 计算机科学技术学报, 2021, 36(2): 234-247.
[8] Jun Gao, Paul Liu, Guang-Di Liu, Le Zhang. 基于深度学习与波束偏转的穿刺针定位与增强算法[J]. 计算机科学技术学报, 2021, 36(2): 334-346.
[9] Hua Chen, Juan Liu, Qing-Man Wen, Zhi-Qun Zuo, Jia-Sheng Liu, Jing Feng, Bao-Chuan Pang, Di Xiao. CytoBrain:基于深度学习技术的宫颈癌筛查系统[J]. 计算机科学技术学报, 2021, 36(2): 347-360.
[10] Jason Liu, Pedro Espina, Xian-He Sun. 关于储存系统建模和优化的综述[J]. 计算机科学技术学报, 2021, 36(1): 71-89.
[11] Andrea Caroppo, Alessandro Leone, Pietro Siciliano. 用于老年人面部表情识别的深度学习模型和传统机器学习方法的对比研究[J]. 计算机科学技术学报, 2020, 35(5): 1127-1146.
[12] Ying Li, Jia-Jie Xu, Peng-Peng Zhao, Jun-Hua Fang, Wei Chen, Lei Zhao. ATLRec:用于跨领域推荐的注意力对抗迁移学习网络[J]. 计算机科学技术学报, 2020, 35(4): 794-808.
[13] 梁盾, 郭元晨, 张少魁, 穆太江, 黄晓蕾. 车道检测-新结果和调查研究[J]. 计算机科学技术学报, 2020, 35(3): 493-505.
[14] Zheng Zeng, Lu Wang, Bei-Bei Wang, Chun-Meng Kang, Yan-Ning Xu. 一种基于多重残差网络的随机渐进式光子映射的降噪方法[J]. 计算机科学技术学报, 2020, 35(3): 506-521.
[15] Zhou Xu, Shuai Pang, Tao Zhang, Xia-Pu Luo, Jin Liu, Yu-Tian Tang, Xiao Yu, Lei Xue. 基于平衡分布适应迁移学习的跨项目缺陷预测[J]. 计算机科学技术学报, 2019, 34(5): 1039-1062.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 周笛;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] 陈世华;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] 李万学;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] 孙钟秀; 商陆军;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[5] 章萃; 赵沁平; 徐家福;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[6] 王建潮; 魏道政;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[7] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[8] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[9] 郑国梁; 李辉;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[10] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: