异构多核图计算系统研究

发布时间：2023-10-06 17:46

　　随着互联网的发展和大数据时代的到来,对海量大规模数据进行快速分析的需求变得更加迫切,图作为一种抽象数据结构,许多实际应用中的大数据都是以图的形式呈现,使用图数据结构来描述数据间的关系,如社交网络关系挖掘、电子商务推荐系统、交通事故对路网的影响等大规模图计算问题。此外,许多非图数据结构的大数据,也常常会被转换为图模型后再进行处理和分析,面向大规模图数据处理的研究正成为学术界和工业界广泛关注的焦点。为适应图数据规模巨大、动态变化等特点,实现大规模图数据的高效分析计算,近年来在计算模型和运行时优化方面(包括分布式系统、异构系统等)涌现出许多具有前瞻性的技术和图计算系统。基于此,设计实现高性能图计算系统具有理论研究和实际应用的重要意义。本文针对异构多核架构的图计算系统进行了深入的研究,主要工作如下:第一,目前GPU图计算的研究分为专用的图计算系统和通用的图计算框架,前者使用GPU加速某一种特定的图算法,如广度优先搜索算法,后者侧重于设计适用于各种不同的图算法的通用计算架构。这两类系统都取得了很好的研究成果,但它们之间在设计、实现、优化等方面存在哪些异同点,仍然缺乏清晰的认识。通用图计算框架可以...

【文章页数】：112 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 异构图计算系统概要
    1.2 国内外研究现状
        1.2.1 单机图计算系统
        1.2.2 GPU加速的图计算系统
        1.2.3 分布式图计算系统
    1.3 本文主要工作
    1.4 本文组织结构
第2章 相关技术背景介绍
    2.1 大规模图计算模型
        2.1.1 以顶点为中心的计算模型
        2.1.2 GAS计算模型
        2.1.3 以边为中心的计算模型
    2.2 GPU体系结构
        2.2.1 GPU和CUDA
        2.2.2 GPU线程调度机制
    2.3 图的相关概念与常见的图算法
        2.3.1 图的基本概念
        2.3.2 图的存储
        2.3.3 常见的图算法
    2.4 本章小结
第3章 专用和通用GPU图计算系统分析
    3.1 通用图计算系统Gunrock
    3.2 专用图计算系统Enterprise
    3.3 评估与分析
        3.3.1 总体性能
        3.3.2 负载均衡
        3.3.3 同步操作
        3.3.4 内存子系统
        3.3.5 讨论分析
    3.4 本章小结
第4章 GPU图计算系统设计与优化
    4.1 引言
    4.2 Pregel图计算系统简介
    4.3 Medusa图计算系统
        4.3.1 Medusa编程模型
        4.3.2 Medusa消息缓存
        4.3.3 Medusa存在的问题
    4.4 系统设计与实现
        4.4.1 执行流程介绍
        4.4.2 编程接口
        4.4.3 运行时系统
        4.4.4 示例图算法
        4.4.5 系统性能分析
    4.5 优化方法
        4.5.1 负载均衡优化策略
        4.5.2 消息缓存存储结构优化策略
    4.6 实验评估
        4.6.1 整体性能
        4.6.2 近似排序算法性能分析
        4.6.3 数据重映射策略性能评估
    4.7 本章小结
第5章 多核图计算系统设计
    5.1 引言
    5.2 系统设计与实现
        5.2.1 基于协程的编程模型
        5.2.2 消息传递机制
        5.2.3 图编程模型
        5.2.4 数据存储
        5.2.5 数据访问模式
        5.2.6 I/O优化策略
        5.2.7 系统执行流程
    5.3 实验分析
        5.3.1 图数据集
        5.3.2 实验平台介绍
        5.3.3 实验过程介绍
        5.3.4 性能分析
    5.4 本章小结
结论
参考文献
附录A 读学位期间所发表的学术论文
附录B 读学位期间所参加的科研项目
致谢



本文编号：3852171