图算法在GPU上的设计实现与性能分析

论文摘要

利用图形处理器进行通用计算（General Purpose Computation on GPU,GPGPU）是当前高性能计算领域的一个研究热点。目前,GPGPU领域的图算法研究较少且效果不佳,一个重要原因是图算法具有不规则访存、动态数据处理等性质,算法执行时难以预测访存地址和分配数据,增加了在GPU上的设计难度。另一方面,近年来Web信息处理等新兴应用的数据规模急剧增长,图算法在其中的重要性越来越突出,应用越来越广泛,图算法执行效率严重制约着数据处理效率。研究GPU上图算法的设计实现方法,寻找解决其中不规则访存和动态数据处理等问题的通用方法,有助于提高新兴应用中的图算法执行效率,也为具有同类性质的其它算法在GPU上的设计提供参考。本文分析了在GPU上设计实现图算法的研究现状,归纳了在GPU上设计图算法的两个难题,即不规则访存与动态数据处理。针对不规则访存问题,采用数据并行原语思想设计了基于GPU的Min-Reduction数据并行原语,通过设计全局存储器规约和共享存储器规约两个原语模块,综合使用序列地址、循环展开、模板参数编译等技术,快速得出规约结果,并将其应用于Prim最小生成树算法在GPU上的设计实现过程;针对动态数据处理问题,采用层次化设计思想设计了层次化任务分配、层次化工作队列、层次化Kernel调用三种方法,有效降低了空线程消耗、全局存储器访问开销、Kernel调用性能损耗,之后在GPU上设计Moore单源最短路径算法时使用了上述方法。最后从理论和实验两方面分析了算法性能。给出了GPU程序性能模型的建立过程并评估了GPU上Prim算法和Moore算法的性能,验证了应用GPU提高图算法效率的合理性。使用不同规模的多种图数据进行了测试,对比相关文献算法实现,GPU上的Prim算法和Moore算法分别取得了1.86和4.42的最大加速比,验证了本文方法的有效性。

论文目录

表目录

图目录

摘要

ABSTRACT

第一章绪论

1.1 研究背景和意义

1.2 研究现状分析

1.3 论文研究内容

1.4 论文章节组织

第二章相关研究工作

2.1 GPU并行计算架构研究

2.1.1 GPU并行计算架构概述

2.1.2 CUDA平台

2.2 图算法相关技术研究

2.2.1 图算法研究概述

2.2.2 不规则访存与数据并行原语

2.2.3 动态数据处理与层次化策略

2.3 GPU架构上的图数据结构

2.3.1 传统图数据结构

2.3.2 压缩邻接表结构

2.3.3 改进的压缩邻接表

2.4 小结

第三章基于GPU的并行Prim最小生成树算法

3.1 最小生成树问题与Prim算法

3.1.1 最小生成树问题描述

3.1.2 Prim算法流程分析

3.2 GPU Min-Reduction数据并行原语

3.2.1 原语设计思想与结构

3.2.2 全局存储器规约

3.2.3 共享存储器规约

3.3 基于GPU的并行Prim算法的设计

3.3.1 并行化时机与并行化策略

3.3.2 算法总体设计

3.3.3 降距过程设计

3.3.4 CPU预处理与后处理设计

3.4 基于GPU的并行Prim算法的实现

3.4.1 重要数据结构实现

3.4.2 关键步骤实现技术

3.4.3 程序执行完整流程

3.5 小结

第四章基于GPU的并行Moore单源最短路径算法

4.1 单源最短路径问题与Moore算法

4.1.1 单源最短路径问题描述

4.1.2 Moore算法流程分析

4.2 CUDA平台上的层次化策略

4.2.1 基本设计思想

4.2.2 层次化任务分配

4.2.3 层次化工作队列

4.2.4 层次化Kernel调用

4.3 基于GPU的并行Moore算法的设计

4.3.1 并行化时机与并行化策略

4.3.2 算法总体设计

4.3.3 设计方式比较

4.4 基于GPU的并行Moore算法的实现

4.4.1 重要数据结构实现

4.4.2 程序执行完整流程

4.4.3 算法应用实例分析

4.5 小结

第五章性能评估与实验测试

5.1 GPU程序性能评估

5.1.1 性能分析模型的建立

5.1.2 两类算法的性能评估

5.2 实验测试与结果分析

5.2.1 测试环境的建立

5.2.2 测试数据的处理

5.2.3 对比算法的选择

5.2.4 GPU Prim算法测试结果分析

5.2.5 GPU Moore算法测试结果分析

5.3 小结

结束语

一.本文工作总结

二.下一步工作展望

参考文献

作者简历攻读硕士学位期间完成的主要工作

致谢

图算法在GPU上的设计实现与性能分析

论文摘要

论文目录

相关论文文献

猜你喜欢