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

被引：1

作者：

苏静

索博

陈群

潘魏

李战怀

机构：

[1] 西北工业大学计算机学院

来源：

华东师范大学学报(自然科学版) | 2016年 / 05期

关键词：

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

D O I：

暂无

中图分类号：

TP338.8 [分布式计算机];

学科分类号：

081201 ;

摘要：

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

引用

页码：112 / 120

页数：9

共 3 条

[1]

BSPlib: The BSP programming library[J] . Jonathan M.D. Hill,Bill McColl,Dan C. Stefanescu,Mark W. Goudreau,Kevin Lang,Satish B. Rao,Torsten Suel,Thanasis Tsantilas,Rob H. Bisseling.Parallel Computing . 1998 (14)

[2]

Shortest paths algorithms: Theory and experimental evaluation[J] . Boris V. Cherkassky,Andrew V. Goldberg,Tomasz Radzik.Mathematical Programming . 1996 (2)

[3] HIGH-SPEED SWITCH SCHEDULING FOR LOCAL AREA NETWORKS [J].

ANDERSON, TE ;

OWICKI, SS ;

SAXE, JB ;

THACKER, CP .

SIGPLAN NOTICES, 1992, 27 (09) :98-110

← 1 →