高效图计算框架关键技术研究
发布时间：2024-06-29 07:24
图结构具有很强的表达能力,现实世界中诸多实体以及实体之间的联系可以抽象成图中的顶点和边,通过分析图数据来挖掘有价值的信息,具有重要的现实意义。近几年来,图数据迅速增长,网页搜索、社交网络、生物信息等领域图建模早已达十亿甚至千亿规模。并且,图本身呈现的幂律分布和随机访问等特性,使得在图数据处理过程中很难利用时间和空间局部性。以上问题为设计高效的图计算框架带来了严峻挑战。单机图计算框架以其能够充分利用计算和存储资源、线程间通信更加高效以及编程简洁易懂等优势,逐渐成为研究热点。本文围绕图计算面临的诸多难题,针对单机上高效图计算框架的设计与实现开展了深入研究,主要工作和创新点如下:1.基于闪存的冗余阵列构建方法。闪存相对磁盘具有高带宽、低延迟、随机读写性能好等优势,为了进一步缩短与内存之间的性能差距,为图计算提供高速外部存储,我们探究了高速闪存阵列的构建方法。我们分别选用SATA和PCIe两种接口的固态盘,组成了RAIS0,5和6三种模式下的闪存阵列。然后,分析了队列深度和请求粒度对单块固态盘和闪存阵列性能发挥的影响,测试了挂载四种主流文件系统XFS、EXT4、F2FS和Btr FS后单盘和闪...
【文章页数】：111 页
【学位级别】：博士
【文章目录】：
摘要
Abstract
符号使用说明
第一章 绪论
1.1 课题背景
1.1.1 图数据存储与计算
1.1.2 图计算面临的挑战
1.2 相关工作
1.2.1 基于外存的图计算框架
1.2.2 基于内存的图计算框架
1.2.3 基于异构的图计算框架
1.2.4 图计算相关评测工作
1.3 本文研究的主要内容和贡献
1.4 论文组织结构
第二章 基于闪存的冗余阵列构建方法
2.1 引言
2.2 背景
2.2.1 固态盘
2.2.2 闪存阵列
2.2.3 文件系统
2.3 单块固态盘性能评测
2.3.1 裸设备性能
2.3.2 文件系统下设备性能
2.4 闪存阵列性能评测
2.4.1 裸设备性能
2.4.2 文件系统下设备性能
2.5 闪存阵列构建方法讨论
2.6 本章小结
第三章 基于NUMA架构的外存图计算框架HPGraph
3.1 引言
3.2 背景
3.2.1 图计算编程模型
3.2.2 非统一内存访问特性
3.2.3 闪存阵列
3.3 整体设计
3.3.1 编程模型
3.3.2 基于NUMA特性的数据布局和访问模式
3.3.3 细粒度的edgeblock过滤策略
3.3.4 其它优化
3.4 实验与分析
3.4.1 测试算法和数据集
3.4.2 预处理开销
3.4.3 整体性能评估
3.4.4 相关优化效果
3.4.5 闪存阵列带宽和处理器资源使用情况
3.5 本章小结
第四章 基于众核处理器的内存图计算框架Ants
4.1 引言
4.2 背景
4.2.1 图结构特性
4.2.2 图数据分析
4.2.3 众核处理器架构
4.3 挑战
4.3.1 异构内存和数据布局
4.3.2 缓存一致性和任务调度
4.4 整体设计
4.4.1 编程模型
4.4.2 基于异构内存的数据布局策略
4.4.3 基于Mesh互联的任务调度机制
4.4.4 其它优化
4.5 实验与分析
4.5.1 测试算法和数据集
4.5.2 不同互联模式性能比较
4.5.3 整体性能评估
4.5.4 数据布局优化效果
4.5.5 任务调度优化效果
4.5.6 Open MP实现
4.5.7 多核体系结构上优化效果
4.6 本章小结
第五章 基于内存的快速Truss分解算法p TD
5.1 引言
5.2 问题描述
5.2.1 定义
5.2.2 典型Truss分解算法
5.3 动机
5.4 快速Truss分解算法
5.5 并行及IO相关优化
5.6 实验与分析
5.6.1 实验环境
5.6.2 整体性能评估
5.6.3 并行化处理效果
5.6.4 IO优化效果
5.7 本章小结
第六章 总结与展望
6.1 工作总结
6.2 未来研究工作展望
致谢
参考文献
作者在学期间取得的学术成果
本文编号：3997361
【文章页数】：111 页
【学位级别】：博士
【文章目录】：
摘要
Abstract
符号使用说明
第一章 绪论
1.1 课题背景
1.1.1 图数据存储与计算
1.1.2 图计算面临的挑战
1.2 相关工作
1.2.1 基于外存的图计算框架
1.2.2 基于内存的图计算框架
1.2.3 基于异构的图计算框架
1.2.4 图计算相关评测工作
1.3 本文研究的主要内容和贡献
1.4 论文组织结构
第二章 基于闪存的冗余阵列构建方法
2.1 引言
2.2 背景
2.2.1 固态盘
2.2.2 闪存阵列
2.2.3 文件系统
2.3 单块固态盘性能评测
2.3.1 裸设备性能
2.3.2 文件系统下设备性能
2.4 闪存阵列性能评测
2.4.1 裸设备性能
2.4.2 文件系统下设备性能
2.5 闪存阵列构建方法讨论
2.6 本章小结
第三章 基于NUMA架构的外存图计算框架HPGraph
3.1 引言
3.2 背景
3.2.1 图计算编程模型
3.2.2 非统一内存访问特性
3.2.3 闪存阵列
3.3 整体设计
3.3.1 编程模型
3.3.2 基于NUMA特性的数据布局和访问模式
3.3.3 细粒度的edgeblock过滤策略
3.3.4 其它优化
3.4 实验与分析
3.4.1 测试算法和数据集
3.4.2 预处理开销
3.4.3 整体性能评估
3.4.4 相关优化效果
3.4.5 闪存阵列带宽和处理器资源使用情况
3.5 本章小结
第四章 基于众核处理器的内存图计算框架Ants
4.1 引言
4.2 背景
4.2.1 图结构特性
4.2.2 图数据分析
4.2.3 众核处理器架构
4.3 挑战
4.3.1 异构内存和数据布局
4.3.2 缓存一致性和任务调度
4.4 整体设计
4.4.1 编程模型
4.4.2 基于异构内存的数据布局策略
4.4.3 基于Mesh互联的任务调度机制
4.4.4 其它优化
4.5 实验与分析
4.5.1 测试算法和数据集
4.5.2 不同互联模式性能比较
4.5.3 整体性能评估
4.5.4 数据布局优化效果
4.5.5 任务调度优化效果
4.5.6 Open MP实现
4.5.7 多核体系结构上优化效果
4.6 本章小结
第五章 基于内存的快速Truss分解算法p TD
5.1 引言
5.2 问题描述
5.2.1 定义
5.2.2 典型Truss分解算法
5.3 动机
5.4 快速Truss分解算法
5.5 并行及IO相关优化
5.6 实验与分析
5.6.1 实验环境
5.6.2 整体性能评估
5.6.3 并行化处理效果
5.6.4 IO优化效果
5.7 本章小结
第六章 总结与展望
6.1 工作总结
6.2 未来研究工作展望
致谢
参考文献
作者在学期间取得的学术成果
本文编号：3997361
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3997361.html
