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