基于活跃度布局的图处理访存优化

发布时间：2023-07-01 11:44

　　伴随着图处理的快速发展,包括数据规模、数据类型,以及图应用在内的多方面因素,显著影响着访存特征。图处理的过程一般分为多次迭代进行,每一次迭代过程中同时存在着活跃数据和不活跃数据,而当前图处理主要的研究方向是通过努力获取访问数据的局部性,减少随机访问请求以提高I/O速度,这主要是针对活跃数据的优化工作,但是处理过程中暂不参与处理的数据,也会给存储系统造成负担,其同样受图处理访存高随机性的影响,很难在图处理过程中削减,因此为了更好地优化图处理,在提高活跃数据访问速度的同时,需要考虑减少不活跃数据的传输量。通过综合分析活跃数据和不活跃数据的特征,基于顶点的活跃度提出一种通用的图数据布局策略VAL。它同时兼顾活跃数据和不活跃数据的分布,使它们分别采用不同的方法组织,一方面高效缓存活跃数据,另一方面有效调度不活跃数据。首先基于中介中心性划分活跃和不活跃顶点集,接着对活跃顶点集集中编排,聚集存储,提高局部性,然后根据度中心性和直接邻接关系两种数据特征重编排不活跃顶点集,提高不活跃数据的局部性,最后针对布局后的不活跃数据设计了一种新的筛选策略,使得CPU请求数据时不仅提高了数据访问速度,也充分去除无...

【文章页数】：55 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
    1.3 主要工作和论文组织结构
2 当前图处理数据组织的分析
    2.1 GraphChi的数据组织和访问
    2.2 X-Stream的数据组织和访问
    2.3 GridGraph的数据组织和访问
    2.4 不活跃数据对图处理的影响
    2.5 图数据布局方法
    2.6 本章小结
3 基于活跃度的数据布局策略
    3.1 整体设计
    3.2 活跃顶点集的划分
    3.3 不活跃顶点的布局
    3.4 对不活跃数据的筛选方法
    3.5 实现方案
    3.6 本章小结
4 测试与结果分析
    4.1 测试环境与方案
    4.2 测试与分析
    4.3 本章小结
5 总结与展望
    5.1 工作总结
    5.2 研究展望
致谢
参考文献
附录1 攻读硕士学位期间发表的论文和专利
附录2 攻读硕士学位期间参与的科研项目



本文编号：3836192