GraphHP:一个图迭代处理的混合平台

摘要：

BSP(Bulk Synchronous Parallel,BSP)计算模型是建立大规模迭代式图处理分布式系统的重要基础.现有平台(如Pregel、Giraph、Hama)虽然已经实现了较高的可扩展性,但主机之间高频同步和通信负荷严重影响了并行计算的效率.为了解决这个关键性问题,本文提出了一种基于混合式模型的执行平台GraphHP(Graph Hybrid Processing).它不仅继承了以顶点为中心的BSP编程接口,而且能够显著减少同步和通信负荷.通过在图分区内部和分区之间建立混合执行模型,GraphHP实现了伪超步迭代计算,把分区内部计算从分布式同步和通信中分离出来.这种混合执行模型不需要繁重的调度算法或者以图为中心的串行算法,就能有效减少同步和通信负荷.最后,本文评估了经典的BSP应用在GraphHP平台的实现方式.实验表明它比现有的BSP实现平台效率更高.本文提出的GraphHP平台虽然是基于Hama实现的,但它很容易迁移到其他的BSP平台.

关键词：图迭代、分布式计算、BSP、GraphHP

分类号：TP311(计算技术、计算机技术)

资助基金：国家973计划项目2012CB316203;国家863计划项目2015AA015307;国家自然科学基金61332006,61472321,61502390

在线出版日期：2016-12-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：112-120