基于消息传递机制的MapReduce图算法研究

被引：44

作者：

潘巍 ^{[1
]}

李战怀 ^{[1
]}

伍赛 ^{[2
]}

陈群 ^{[1
]}

机构：

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

[2] 新加坡国立大学计算机学院

来源：

计算机学报 | 2011年 / 34卷 / 10期

关键词：

云计算; MapReduce; 大同步模型; 消息传递; 图算法; PageRank;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

单机运行环境难以满足基于海量数据的大图算法对时空开销的需求,如何设计高效的面向云计算环境的分布式大图算法越来越受到人们的关注,MapReduce作为云计算的核心计算模式受限于易并行(EP)计算模型的制约不易表达图算法.文中突破了MapReduce基于易并行计算的假设,增强了MapReduce既有的编程规范,新的大同步(BSP)计算模型既能保证兼容旧的MapReduce作业可以无改动的运行,同时引入消息传递机制允许变化的状态数据在并行任务的超级步间进行交互.系统提供高度灵活的消息自定义接口,针对不同应用需求设计了轻量级和重量级两种自适应的消息传递机制,更高效地支持有数据交互需求的包含迭代处理的一大类图算法.在真实大规模图数据集上的实验结果表明,相比于原始的MapReduce作业外部链式处理,该文提出的BSP模型下的内部超级步迭代计算模式大幅降低了大图算法的处理时间.

引用

页码：1768 / 1784

页数：17

共 7 条

[1] MapReduce in MPI for Large-scale graph algorithms
Plimpton, Steven J.
Devine, Karen D.
[J]. PARALLEL COMPUTING, 2011, 37 (09) : 610 - 632
[2] MapReduce and parallel DBMSs[J] . Michael Stonebraker,Daniel Abadi,David J. DeWitt,Sam Madden,Erik Paulson,Andrew Pavlo,Alexander Rasin.Communications of the ACM . 2010 (1)
[3] MapReduce[J] . Jeffrey Dean,Sanjay Ghemawat.Communications of the ACM . 2010 (1)
[4] Interpreting the data: Parallel analysis with Sawzall[J] . Carlos A. Varela,Paolo Ciancarini,Kenjiro Taura,Rob Pike,Sean Dorward,Robert Griesemer,Sean Quinlan.Scientific Programming . 2005 (4)
[5] Software and the Concurrency Revolution[J] . Herb Sutter,James Larus.Queue . 2005 (7)
[6] A BRIDGING MODEL FOR PARALLEL COMPUTATION
VALIANT, LG
[J]. COMMUNICATIONS OF THE ACM, 1990, 33 (08) : 103 - 111
[7] Spark:cluster computing with working sets. ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al. Proceedings of the HotCloud’’10 . 2010

← 1 →