| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 基于消息传递机制的MapReduce图算法研究 |
| 作者 | 潘巍1) 李战怀1) 伍赛2) 陈群1) |
| 作者单位 | 1)(西北工业大学计算机学院 西安 710072) 2)(新加坡国立大学计算机学院 新加坡 119077) |
| 发表年份 | 2011 |
| 发表月份 | 10期(1768—1784) |
| 文章摘要 | 摘要 单机运行环境难以满足基于海量数据的大图算法对时空开销的需求，如何设计高效的面向云计算环境的分布式大图算法越来越受到人们的关注，MapReduce作为云计算的核心计算模式受限于易并行(EP)计算模型的制约不易表达图算法.文中突破了MapReduce基于易并行计算的假设，增强了MapReduce既有的编程规范，新的大同步(BSP)计算模型既能保证兼容旧的MapReduce作业可以无改动的运行，同时引入消息传递机制允许变化的状态数据在并行任务的超级步间进行交互.系统提供高度灵活的消息自定义接口，针对不同应用需求设计了轻量级和重量级两种自适应的消息传递机制，更高效地支持有数据交互需求的包含迭代处理的一大类图算法.在真实大规模图数据集上的实验结果表明，相比于原始的MapReduce作业外部链式处理，该文提出的BSP模型下的内部超级步迭代计算模式大幅降低了大图算法的处理时间. 关键词 云计算；MapReduce；大同步模型；消息传递；图算法；PageRank 中图法分类号 TP311 DOI号: 10.3724/SP.J.1016.2011.01768 |