【摘要】 分析了分布式图计算框架的同步和异步计算模式在调度开销和收敛速度上存在的优点与不足.同步计算模式调度开销小,但是收敛较慢;而异步计算模式收敛较快,但调度开销大.基于上述发现,提出一种混合计算模式,能够在分布式环境下有效地结合同步与异步计算模式的优点克服各自不足,以获得最优性能.混合计算模式采用"同步控制流"以降低分布式环境下的调度开销,同时采用"异步数据流"使计算过程使用较新的数据以加快收敛速度.基于多个典型图算法和真实大规模图的评测显示,混合计算模式的性能是原有同步计算模式的1.2倍到2.4倍,计算量平均减少30%;相对于异步计算模式通过减少调度开销,整体性能可以提升至其2.3倍到4.6倍.更多还原

【Abstract】 This paper analyzes the pros and cons of synchronous and asynchronous computation modes of distributed graph computation framework. Synchronous mode has light scheduling overhead but converges slowly; asynchronous mode converges fast but suffers from heavy scheduling overhead. Based on the analysis,this paper proposes a hybrid computation mode,combiningthe two existing modes’ advantages while avoiding their disadvantages to achieve optimal performance in distributed computation environment. Hybrid computation mode uses "synchronous control flow"to reduce scheduling overhead in distributed settings and "asynchronous data flow"to accelerate convergence. Evaluations on several typical applications and real-world datasets showthat hybrid mode outperforms synchronous modeby 1. 2X-2. 4X,with 30% less compute tasks and achieves 2. 3X-4. 6X speedup compared to asynchronous mode by reducing scheduling overhead.更多还原