面向PowerGraph的性能优化研究与实现
发布时间：2021-08-31 17:21
互联网的迅速发展使得网络图成为了研究和分析的热点,而机器学习和数据挖掘等面向图数据结构的技术也已经在社交网络分析、网络搜索、自然语言处理和推荐系统等领域得到了广泛的应用。PowerGraph提出了GAS（Gather Apply Scatter）抽象以及点切割的图分区算法。本论文分析了图算法执行过程中消息传输模型及数据缓存机制的网络通信行为,发现PowerGraph中原有的消息传输模型仅采用推送模式,可能导致Master副本无法及时从Mirror副本获取到最新消息,或者Mirror副本可能会传送多条消息给Master副本;除此之外,在PowerGraph点切割分区方法下原本的数据缓存机制只能够减少计算开销,却无法减少网络开销,而且开发人员必须自己实现缓存相关的代码,导致开发人员的使用成本也有所增高。针对上述问题,本文做了详尽的分析调研并提出了相应的解决方案,主要内容包括以下两个方面。为了解决PowerGraph消息传输模型的问题,本文提出了一种新的模型:首先,由Mirror副本接收的消息总是存储在本地,并且将与新接收到的消息合并,直到Mirror副本被调度后才将合并后的消息发送给Mas...
【文章来源】：电子科技大学四川省 211工程院校 985工程院校 教育部直属院校
【文章页数】：76 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 绪论
1.1 研究工作的背景
1.2 国内外研究现状
1.3 主要研究内容
1.4 论文组织结构
第二章 图计算框架概述
2.1 单机图计算系统
2.1.1 GraphChi
2.1.2 X-stream
2.1.3 Grid Graph
2.2 分布式图计算系统
2.2.1 Pregel
2.2.2 Giraph
2.2.3 GPS
2.2.4 Pregel+
2.2.5 GraphX
2.3 PowerGraph及其优化
2.3.1 PowerGraph架构简介
2.3.1.1 GAS模型
2.3.1.2 执行引擎
2.3.1.3 点切割图分区
2.3.2 PowerGraph相关优化
2.4 本章小结
第三章 消息传输机制中的拉取模型
3.1 现有机制存在的问题
3.2 系统设计
3.2.1 消息传输
3.2.2 迭代流程
3.2.3 模型设计
3.3 系统实现
3.4 本章小结
第四章 基于单副本集中式缓存的迭代加速技术
4.1 原系统中的分布式缓存机制
4.2 分布式缓存机制的不足
4.3 缓存机制的设计
4.3.1 多副本缓存机制
4.3.2 单副本缓存机制
4.3.3 缓存机制的空间影响
4.4 缓存机制的适用范围
4.4.1 图着色应用
4.4.2 消息传递应用
4.4.3 其它应用
4.5 数据缓存机制与消息拉取模型的合并
4.6 本章小结
第五章 实验评估
5.1 实验配置
5.1.1 实验使用的集群环境
5.1.2 实验使用的图应用
5.1.3 实验使用的数据集
5.2 实验结果
5.2.1 不同应用的实验结果
5.2.1.1 消息拉取模型与原系统的比较
5.2.1.2 数据缓存机制与原系统的比较
5.2.1.3 合并后的系统与原系统的比较
5.2.2 不同数据集的实验结果
5.2.2.1 消息拉取模型与原系统的比较
5.2.2.2 数据缓存机制与原系统的比较
5.2.2.3 合并后的系统与原系统的比较
5.2.3 不同机器数的实验结果
5.2.3.1 消息拉取模型与原系统的比较
5.2.3.2 数据缓存机制与原系统的比较
5.2.3.3 合并后的系统与原系统的比较
5.3 本章小结
第六章 总结与展望
6.1 全文总结
6.2 后续工作展望
致谢
参考文献
攻硕期间取得的研究成果
本文编号：3375301
【文章来源】：电子科技大学四川省 211工程院校 985工程院校 教育部直属院校
【文章页数】：76 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 绪论
1.1 研究工作的背景
1.2 国内外研究现状
1.3 主要研究内容
1.4 论文组织结构
第二章 图计算框架概述
2.1 单机图计算系统
2.1.1 GraphChi
2.1.2 X-stream
2.1.3 Grid Graph
2.2 分布式图计算系统
2.2.1 Pregel
2.2.2 Giraph
2.2.3 GPS
2.2.4 Pregel+
2.2.5 GraphX
2.3 PowerGraph及其优化
2.3.1 PowerGraph架构简介
2.3.1.1 GAS模型
2.3.1.2 执行引擎
2.3.1.3 点切割图分区
2.3.2 PowerGraph相关优化
2.4 本章小结
第三章 消息传输机制中的拉取模型
3.1 现有机制存在的问题
3.2 系统设计
3.2.1 消息传输
3.2.2 迭代流程
3.2.3 模型设计
3.3 系统实现
3.4 本章小结
第四章 基于单副本集中式缓存的迭代加速技术
4.1 原系统中的分布式缓存机制
4.2 分布式缓存机制的不足
4.3 缓存机制的设计
4.3.1 多副本缓存机制
4.3.2 单副本缓存机制
4.3.3 缓存机制的空间影响
4.4 缓存机制的适用范围
4.4.1 图着色应用
4.4.2 消息传递应用
4.4.3 其它应用
4.5 数据缓存机制与消息拉取模型的合并
4.6 本章小结
第五章 实验评估
5.1 实验配置
5.1.1 实验使用的集群环境
5.1.2 实验使用的图应用
5.1.3 实验使用的数据集
5.2 实验结果
5.2.1 不同应用的实验结果
5.2.1.1 消息拉取模型与原系统的比较
5.2.1.2 数据缓存机制与原系统的比较
5.2.1.3 合并后的系统与原系统的比较
5.2.2 不同数据集的实验结果
5.2.2.1 消息拉取模型与原系统的比较
5.2.2.2 数据缓存机制与原系统的比较
5.2.2.3 合并后的系统与原系统的比较
5.2.3 不同机器数的实验结果
5.2.3.1 消息拉取模型与原系统的比较
5.2.3.2 数据缓存机制与原系统的比较
5.2.3.3 合并后的系统与原系统的比较
5.3 本章小结
第六章 总结与展望
6.1 全文总结
6.2 后续工作展望
致谢
参考文献
攻硕期间取得的研究成果
本文编号：3375301
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3375301.html
