基于bsp模型的分布式图计算系统性能优化研究

《基于bsp模型的分布式图计算系统性能优化研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据指导小组成员名单：臧斌宇教授陈海波教授张为华副教授万方数据云计算中虚拟机动态迁移的研究目录目录=善⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1嘲觥⋯．．v-第一章引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯-．．烹X■．!：．：．．：⋯⋯⋯12．1Pregel系统⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯102．1．2Pregel计算模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．102．2．1Gimph⋯⋯⋯⋯⋯⋯．⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯．14万方数据云计算中虚拟机动态迁移的研究目录3．2．2消息队列数据竞争激烈⋯⋯

2、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯193．2．3重复计算和数据通信(对拉模型应用)⋯⋯⋯⋯⋯⋯⋯⋯203．2分布式只读共享内存⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯213．2．1图组织结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．2l3．2．2顶点计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯223．2．3数据通信⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯223．2．3收敛条件判断⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯233'3分布式只读共享内存的实现⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯233．4与PowerGraph的比较⋯⋯⋯⋯⋯⋯

3、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯243．5对多核架构的支持⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯263．6评测⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯273．6．1实验环境⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯273．6．2图算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯273．6．3消除重复计算和重复消息⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯283．6．4总体性能提升⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯283．6．5运行时间分解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯293．7小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

4、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．3l第四章分布式图计算系统计算模型优化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯324．1同步和异步计算模型比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯324．1．1同步计算模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯324．1．2异步计算模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯334．1．3两种计算模型的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．344．2混合计算模型及其优化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯354．2．1混合计算模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯354．2．2冗余激活问题⋯⋯⋯⋯⋯⋯⋯⋯⋯

5、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯364．2．3细粒度版本追踪技术⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯374．2．4无锁版本追踪技术⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯384．3性能评测⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯394．3．1实验环境⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯394．3．2总体性能提升⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯40lT万方数据云计算中虚拟机动态迁移的研究目录4．3．3可扩展性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯404．3．4版本追踪消除冗余激活的效果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4l4．4小结⋯

6、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．42第五章总结与分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯435．1创新与贡献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯435．2进一步的研究设想⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯435．2．1结合“边切分”和“顶点切分”⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯445．2．2适应性的计算模型选择⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯44参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．45致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一

7、49IlI万方数据基于BSP模型的分布式图计算系统性能优化研究摘要在社交网络关系挖掘、网页排序、推荐系统以及自然语言处理等大规模数据挖掘和机器学习应用的推动下，使用图数据结构来描述数据及数据之间关系的分布式图计算模型获得了日益广泛的应用。图算法由于需要多轮迭代，各顶点数据间存在复杂联系，计算过程依赖点对点通信，因此以MapReduce及其开源实现Hadoop为代表的传统面向数据并行(Data—parallel)的计算模型难以提供高效的支持。为解决对于图计算的迫切需要和现有的计算平台无法满足大规模图计算需求的问题，Google

8、公司提出了基于整体同步模型(BulkSynchronousParallel)的Pregel。Pregel提出像项点一样思考的编程模型，用户只需提供一个简单的compute函数，系统负责处理顶点调度和数据通信等。Pregel将图计算任务的执行抽象成～个超步(superstep，也称轮)，每一