面向图计算系统的异步计算-加载模型
|
摘要
本文提出了全新的异步计算-加载模型,该模型是对核外(out-of-core)图计算系统的进一步优化.在异步计算-加载模型中,计算过程和I/O加载过程并行进行,较长的I/O加载时间能够"隐藏"数据计算时间,从用户程序角度来看,整体系统的运行时间几乎只有I/O加载时间,从而提高系统性能;此外,本文的异步模型能够根据不同的访问需求和硬件特性创建不同的线程组:计算线程和I/O加载线程.计算线程数量由服务器计算能力决定,I/O线程数量由服务器的I/O处理能力决定,这样既保证充分利用硬盘带宽又保证高效的计算;异步模型利用LIBAIO引擎的batch机制使得各线程的工作负载更加均衡.实验结果说明,与原先的同步模型相比,本文的模型能将整体系统性能提升高达一倍,并且有更好的带宽利用率和负载平衡性.
In this paper,we present asynchronous( ASYNC) computation-loading model,which is an optimization to out-of-core graph computing systems. Computation and I/O loading phases can be parallelized in the ASYNC model,and the longer I/O loading time hides the computation time,so there is only I/O loading phase from the perspective of the users; Moreover,according to access requirements and hardware features,the ASYNC model differentiates threads into two groups: computing threads and I/O threads. The quantity of threads in each group depends on the abilities of the based servers: the computing ability decides the computing threads while the I/O processing ability decides the I/O threads. Both full I/O bandwidth and effective computation can be guaranteed by this strategy. Workload among threads are more balanced in the ASYNC model because it uses LIBAIO as I/O engine for its batch mechanism.The experimental results show that our new asynchronous( ASYNC) computation-loading model can outperform the synchronous model used in prior systems by up to 2 X,and has better I/O bandwidth and workload balance.
In this paper,we present asynchronous( ASYNC) computation-loading model,which is an optimization to out-of-core graph computing systems. Computation and I/O loading phases can be parallelized in the ASYNC model,and the longer I/O loading time hides the computation time,so there is only I/O loading phase from the perspective of the users; Moreover,according to access requirements and hardware features,the ASYNC model differentiates threads into two groups: computing threads and I/O threads. The quantity of threads in each group depends on the abilities of the based servers: the computing ability decides the computing threads while the I/O processing ability decides the I/O threads. Both full I/O bandwidth and effective computation can be guaranteed by this strategy. Workload among threads are more balanced in the ASYNC model because it uses LIBAIO as I/O engine for its batch mechanism.The experimental results show that our new asynchronous( ASYNC) computation-loading model can outperform the synchronous model used in prior systems by up to 2 X,and has better I/O bandwidth and workload balance.
引文
[1]Gonzalez J E,Low Y,Gu H,et al. Powergraph:distributed graphparallel computation on natural graphs[C]//Operating System Design and Implementation(OSDI),2012,12(1):2-15.
[2]Chen R,Shi J,Chen Y,et al. Powerlyra:differentiated graph computation and partitioning on skewed graphs[C]//Proceedings of the Tenth European Conference on Computer Systems(EuroSys),ACM,2015:1-15.
[3]Han M,Daudjee K. Giraph unchained:barrierless asynchronous parallel execution in pregel-like graph processing systems[J]. Proceedings of the International Conference on Very Large Data Bases(VLDB)Endowment,2015,8(9):950-961.
[4]Xiao Di,Chen Rong. Efficient elastic distributed graph computing system[EB/OL]. http://www. paper. edu. cn/releasepaper/content/201705-135.
[5]Kyrola A,Blelloch G E,Guestrin C. Graphchi:large-scale graph computation on just a pc[C]//Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation(OSDI). USENIX Association,2012:31-46.
[6]Roy A,Mihailovic I,Zwaenepoel W. X-stream:edge-centric graph processing using streaming partitions[C]//Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles(SOSP),2013:472-488.
[7]Zhu X,Han W,Chen W. GridGraph:large-scale graph processing on a single machine using 2-level hierarchical partitioning[C]//USENIX Annual Technical Conference(USENIX ATC),2015:375-386.
[8]Page L,Brin S,Motwani R,et al. The PageRank citation ranking:bringing order to the web[R]. Stanford InfoLab,1999.
[9]Kumar P,Huang H H. Falcon:Scaling io performance in multissd volumes[C]//USENIX Annual Technical Conference(USENIX ATC),2017:41-53.
[10]Bell N,Garland M. Implementing sparse matrix-vector multiplication on throughput-oriented processors[C]//Proceedings of the Conference on High Performance Computing Networking,Storage and Analysis(SC),2009:18-28.
[4]肖迪,陈榕.高效弹性分布式图计算系统[EB/OL]. http://www. paper. edu. cn/releasepaper/content/201705-135.
1 http://law.di.unimi.it/webdata/clueweb12/
2 http://lse.sourceforge.net/io/aio.html
3 http://wufei.org/2016/09/16/linux-io-data-flow/
4 http://law.di.unimi.it/webdata/uk-union-2006-06-2007-05
5 http://law.di.unimi.it/webdata/gsh-2015/
6 http://law.di.unimi.it/webdata/eu-2015/
[2]Chen R,Shi J,Chen Y,et al. Powerlyra:differentiated graph computation and partitioning on skewed graphs[C]//Proceedings of the Tenth European Conference on Computer Systems(EuroSys),ACM,2015:1-15.
[3]Han M,Daudjee K. Giraph unchained:barrierless asynchronous parallel execution in pregel-like graph processing systems[J]. Proceedings of the International Conference on Very Large Data Bases(VLDB)Endowment,2015,8(9):950-961.
[4]Xiao Di,Chen Rong. Efficient elastic distributed graph computing system[EB/OL]. http://www. paper. edu. cn/releasepaper/content/201705-135.
[5]Kyrola A,Blelloch G E,Guestrin C. Graphchi:large-scale graph computation on just a pc[C]//Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation(OSDI). USENIX Association,2012:31-46.
[6]Roy A,Mihailovic I,Zwaenepoel W. X-stream:edge-centric graph processing using streaming partitions[C]//Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles(SOSP),2013:472-488.
[7]Zhu X,Han W,Chen W. GridGraph:large-scale graph processing on a single machine using 2-level hierarchical partitioning[C]//USENIX Annual Technical Conference(USENIX ATC),2015:375-386.
[8]Page L,Brin S,Motwani R,et al. The PageRank citation ranking:bringing order to the web[R]. Stanford InfoLab,1999.
[9]Kumar P,Huang H H. Falcon:Scaling io performance in multissd volumes[C]//USENIX Annual Technical Conference(USENIX ATC),2017:41-53.
[10]Bell N,Garland M. Implementing sparse matrix-vector multiplication on throughput-oriented processors[C]//Proceedings of the Conference on High Performance Computing Networking,Storage and Analysis(SC),2009:18-28.
[4]肖迪,陈榕.高效弹性分布式图计算系统[EB/OL]. http://www. paper. edu. cn/releasepaper/content/201705-135.
1 http://law.di.unimi.it/webdata/clueweb12/
2 http://lse.sourceforge.net/io/aio.html
3 http://wufei.org/2016/09/16/linux-io-data-flow/
4 http://law.di.unimi.it/webdata/uk-union-2006-06-2007-05
5 http://law.di.unimi.it/webdata/gsh-2015/
6 http://law.di.unimi.it/webdata/eu-2015/