苏静,索博,陈群,潘魏,李战怀

(西北工业大学计算机学院,西安710072)

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

苏静,索博,陈群,潘魏,李战怀

(西北工业大学计算机学院,西安710072)

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

图迭代;分布式计算;BSP;GraphHP

0 引言

目前越来越多的大数据应用都聚焦于具有复杂数据依赖关系的图模型,如各种社交网络、Web图、生物基因网络等都需要利用图模型进行计算处理.图模型的计算离不开迭代,迭代的本质就是对目前系统的一系列状态进行改变,特别是在大规模数据集中运行这类算法时,就需要一种快速执行并行迭代的技术.设计和实现大规模分布式……