图计算中基于一致性约束条件的迭代模型研究
|
摘要
迭代计算是数值计算中有效的逼近方式,能够拟合多种计算模型.在大数据分析领域尤其是图计算中,迭代计算能够抽象描述大部分图算法,对结构化数据挖据和关联分析至关重要.随着数据规模的增长,很多精确算法的时空复杂度已经难以满足现实需求,迭代计算的算法越来越丰富.并行迭代是图计算的主要实现形式,已有的图并行策略大多数是同步模型,少量异步模型,对于一致性约束条件下的迭代研究较少.研究内容重点关注图计算模型中迭代执行技术,分析了同步迭代和异步迭代的适用性,以及不同一致性下的异步迭代方式,针对已有异步迭代方式的不足提出了自适应的弱一致异步执行模型,并进行了验证性实验.实验证明:该模型能有效提高部分图算法的执行效率,尤其是收敛速度和效果.
The time and space complexity of many accurate algorithms is difficult to meet the realistic demands, while approximating algorithms are alternative choices. Iterative computing is an effective approximating method in numerical computing. A variety of algorithms and models can be classified into it. With the increase of data scale, iterative algorithms are blooming and developing. Graph computing is a natural way to express and analyze relationships. There are numerous graph algorithms being described as iterative models. Parallel iterating is regular in large graph computing. Graph iterating methods have different parallel execution models. Most of the existing parallel graph computing implementations are synchronous, and a few of them are asynchronous models. However, there are few studies about consistency constraints in graph iterating. In this paper, we discuss the iterative computing technique in graph computing model. We analyze the applicability of synchronous and asynchronous iterations, and study the asynchronous iterative methods under different consistency, as well as experimental proving. We propose an adaptive asynchronous execution model which is weakly consistent. It overcomes the shortcomings of existing asynchronous iterative methods. Experiments of this model were done in parallel and have shown that the model can effectively improve some graph algorithms, especially the iterating and converging speed.
The time and space complexity of many accurate algorithms is difficult to meet the realistic demands, while approximating algorithms are alternative choices. Iterative computing is an effective approximating method in numerical computing. A variety of algorithms and models can be classified into it. With the increase of data scale, iterative algorithms are blooming and developing. Graph computing is a natural way to express and analyze relationships. There are numerous graph algorithms being described as iterative models. Parallel iterating is regular in large graph computing. Graph iterating methods have different parallel execution models. Most of the existing parallel graph computing implementations are synchronous, and a few of them are asynchronous models. However, there are few studies about consistency constraints in graph iterating. In this paper, we discuss the iterative computing technique in graph computing model. We analyze the applicability of synchronous and asynchronous iterations, and study the asynchronous iterative methods under different consistency, as well as experimental proving. We propose an adaptive asynchronous execution model which is weakly consistent. It overcomes the shortcomings of existing asynchronous iterative methods. Experiments of this model were done in parallel and have shown that the model can effectively improve some graph algorithms, especially the iterating and converging speed.
引文
[1]Milaszewicz J.Improving Jacobi and Gauss-Seidel iterations[J].Linear Algebra and Its Applications,1987,93(8):161-170
[2]Zhou Tie,Xu Shufang,Zhang Pingwen,et al.Computing Method[M].Beijing:Tsinghua University Press,2006:103-104(in Chinese)(周铁,徐树方,张平文,等.计算方法[M].北京:清华大学出版社,2006:103-104)
[3]Cheatham T,Fahmy A,Stefanescu D,et al.Bulk synchronous parallel computing-A paradigm for transportable software[G]Tools and Environments for Parallel and Distributed Systems.New York:Springer,1996:61-76
[4]Gerbessiotis A,Valiant L.Direct bulk-synchronous parallel algorithms[J].Journal of Parallel and Distributed Computing,1994,22(2):251-267
[5]Malewicz G,Austern M,Bik A,et al.Pregel:A system for large-scale graph processing[C]Proc of the 29th ACMSIGMOD Int Conf on Management of Data.New York:ACM,2010:135-146
[6]Xin R,Gonzales J,Franklin M,et al.GraphX:A resilient distributed graph system on Spark[C]Proc of the 1st Int Workshop on Graph Data Management Experiences and Systems.New York:ACM,2013:2:1-6
[7]Ewen S,Tzoumas K,Kaufmann M,et al.Spinning fast iterative data flows[J].Proceedings of the VLDBEndowment,2012,5(11):1268-1279
[8]Li Chao,Chen Jianxia,Yang Zhi,et al.Asynchronous PageRank computation in Spark[C]Proc of the 11th Conf on Complex,Intelligent,and Software Intensive Systems.Cham,Switzeland:Springer,2017:567-573
[9]Wang Guozhang,Xie Wenlei,Demers A,et al.Asynchronous large-scale graph processing made easy[C/OL]Proc of the 6th Biennial Conf on Innovative Data Systems Research.2013[2017-06-29].http:cidrdb.org/cidr2013/Papers/CIDR13_Paper58.pdf
[10]Gonzalez J,Low Y,Gu Haijie,et al.Distributed graphparallel computation on natural graphs[C]Proc of the 10th USENIX Symp on Operating Systems Design and Implementation.Berkeley,CA:USENIX Association,2012:No.2
[11]Shi Xuanhua,Luo Xuan,Liang Junling,et al.Frog:Asynchronous graph processing on GPU with hybrid coloring model[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(1):29-42
[12]Wang Yangzihao,Davidson A,Pan Yuechao,et al.Gunrock:A high-performance graph processing library on the GPU[C]Proc of the 21st ACM SIGPLAN Symp on Principles and Practice of Parallel Programming.New York:ACM,2016:11:1-12
[13]Xie Chenning,Chen Rong,Guan Haibing,et al.Sync or async:Time to fuse for distributed graph-parallel computation[J].ACM SIGPLAN Notices,2015,50(8):194-204
[14]Don C,Peter D,Prabhakar R,et al.Random walks on weighted graphs and applications to on-line algorithms[J].Journal of the ACM,1993,40(3):421-453
[15]Page L,Brin S,Motwani R,et al.The PageRank citation ranking:Bringing order to the Web,SIDL-WP-1999-0120[R].Palo Alto:Stanford InfoLab,1999
[16]Friedgut E,Bourgain J.Sharp thresholds of graph properties,and the k-SAT problem[J].Journal of the American Mathematical Society,1999,12(4):1017-1054
[17]Fedorenko R.The speed of convergence of one iterative process[J].USSR Computational Mathematics and Mathematical Physics,1964,4(3):227-235
[18]Szyld D.The mystery of asynchronous iterations convergence when the spectral radius is one,Report 98-102[R].Philadelphia,PA:Department of Mathematics,Temple University,1998
[19]Frommer A,Szyld D.On asynchronous iterations[J].Journal of Computational and Applied Mathematics,2000,123(1):201-216
[20]Low Y.GraphLab:A distributed abstraction for large scale machine learning[D].Berkeley:University of California,Berkeley,2013
[21]Leskovec J,Krevl A.SNAP Datasets:Stanford Large Network Dataset Collection[OL].2014[2017-08-25].http:snap.stanford.edu/data
[2]Zhou Tie,Xu Shufang,Zhang Pingwen,et al.Computing Method[M].Beijing:Tsinghua University Press,2006:103-104(in Chinese)(周铁,徐树方,张平文,等.计算方法[M].北京:清华大学出版社,2006:103-104)
[3]Cheatham T,Fahmy A,Stefanescu D,et al.Bulk synchronous parallel computing-A paradigm for transportable software[G]Tools and Environments for Parallel and Distributed Systems.New York:Springer,1996:61-76
[4]Gerbessiotis A,Valiant L.Direct bulk-synchronous parallel algorithms[J].Journal of Parallel and Distributed Computing,1994,22(2):251-267
[5]Malewicz G,Austern M,Bik A,et al.Pregel:A system for large-scale graph processing[C]Proc of the 29th ACMSIGMOD Int Conf on Management of Data.New York:ACM,2010:135-146
[6]Xin R,Gonzales J,Franklin M,et al.GraphX:A resilient distributed graph system on Spark[C]Proc of the 1st Int Workshop on Graph Data Management Experiences and Systems.New York:ACM,2013:2:1-6
[7]Ewen S,Tzoumas K,Kaufmann M,et al.Spinning fast iterative data flows[J].Proceedings of the VLDBEndowment,2012,5(11):1268-1279
[8]Li Chao,Chen Jianxia,Yang Zhi,et al.Asynchronous PageRank computation in Spark[C]Proc of the 11th Conf on Complex,Intelligent,and Software Intensive Systems.Cham,Switzeland:Springer,2017:567-573
[9]Wang Guozhang,Xie Wenlei,Demers A,et al.Asynchronous large-scale graph processing made easy[C/OL]Proc of the 6th Biennial Conf on Innovative Data Systems Research.2013[2017-06-29].http:cidrdb.org/cidr2013/Papers/CIDR13_Paper58.pdf
[10]Gonzalez J,Low Y,Gu Haijie,et al.Distributed graphparallel computation on natural graphs[C]Proc of the 10th USENIX Symp on Operating Systems Design and Implementation.Berkeley,CA:USENIX Association,2012:No.2
[11]Shi Xuanhua,Luo Xuan,Liang Junling,et al.Frog:Asynchronous graph processing on GPU with hybrid coloring model[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(1):29-42
[12]Wang Yangzihao,Davidson A,Pan Yuechao,et al.Gunrock:A high-performance graph processing library on the GPU[C]Proc of the 21st ACM SIGPLAN Symp on Principles and Practice of Parallel Programming.New York:ACM,2016:11:1-12
[13]Xie Chenning,Chen Rong,Guan Haibing,et al.Sync or async:Time to fuse for distributed graph-parallel computation[J].ACM SIGPLAN Notices,2015,50(8):194-204
[14]Don C,Peter D,Prabhakar R,et al.Random walks on weighted graphs and applications to on-line algorithms[J].Journal of the ACM,1993,40(3):421-453
[15]Page L,Brin S,Motwani R,et al.The PageRank citation ranking:Bringing order to the Web,SIDL-WP-1999-0120[R].Palo Alto:Stanford InfoLab,1999
[16]Friedgut E,Bourgain J.Sharp thresholds of graph properties,and the k-SAT problem[J].Journal of the American Mathematical Society,1999,12(4):1017-1054
[17]Fedorenko R.The speed of convergence of one iterative process[J].USSR Computational Mathematics and Mathematical Physics,1964,4(3):227-235
[18]Szyld D.The mystery of asynchronous iterations convergence when the spectral radius is one,Report 98-102[R].Philadelphia,PA:Department of Mathematics,Temple University,1998
[19]Frommer A,Szyld D.On asynchronous iterations[J].Journal of Computational and Applied Mathematics,2000,123(1):201-216
[20]Low Y.GraphLab:A distributed abstraction for large scale machine learning[D].Berkeley:University of California,Berkeley,2013
[21]Leskovec J,Krevl A.SNAP Datasets:Stanford Large Network Dataset Collection[OL].2014[2017-08-25].http:snap.stanford.edu/data