基于GPU的最短路径算法的研究和实现

论文摘要

GP GPU（General Purpose Graph Processing Unit）并行计算是近几年高性能计算领域的一个研究热点，主要是利用原有的图形处理器的强大并行计算性能，实现高性能低成本的并行通用计算，高效地完成有海量数据的科学实验计算或企业数据分析。最短路径问题是图论中的一个经典抽象问题，已经广泛应用于城市规划与设计、图形学图像分割、数字导航系统等领域，具有很高的理论研究和实际应用价值。而Floyd-Warshall算法是最短路径问题中求解APSP（All-Pair Shortest Paths）问题的经典算法，能够高效地计算出图中所有节点间的最短路径。Floyd算法可为实际的物流企业配送中心选址过程中提供重要的参考依据。然而Floyd算法的时间复杂度为O(n3)，在实际地图中，随着节点数的增加，计算时间呈指数级增长。因此，将此算法并行化则能明显的加快计算速度，具有较高的科研和实际意义。在此情况下，本文采用GP GPU并行加速的方式实现Floyd算法，可以快速地完成大规模地图中最短路径的寻找，为物流配送中心选址过程提供计算地理重心位置的依据。本文主要完成了如下工作：1、设计了基于GPU的Floyd并行策略，在Tesla M2050型号的GPU下完成CUDA程序的开发，并在同一平台上和原有的Floyd串行程序比较，得到了平均百倍以上的加速比；2、研究了Venkataraman的矩阵分块计算思想，提出并验证此算法在GPU上分块并行的可行性，实现了相应的分块并行计算程序，得到了相对于普通GPU并行的程序平均6倍以上的加速比；3、在实际的地图中运用上述研究成果，快速地计算出图中的全部最短路径，为物流系统在配送中心选址问题提供依据，选出路径总权值最小、费用最少的配送中心地址，实现物流的综合效益最大化。

论文目录

• 摘 要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景及意义
• 1.2 GP GPU概述
• 1.3 国内外研究现状
• 1.4 本文的主要贡献
• 1.5 本文的组织结构
• 1.6 本章小结
• 第二章 GPU简介
• 2.1 GPU的结构
• 2.1.1 GPU相对 CPU 的优势
• 2.1.2 GPU的硬件构造
• 2.1.3 Tesla 体系结构
• 2.1.4 Tesla 通用计算模型
• 2.1.5 Fermi 架构简介
• 2.2 CUDA C简介
• 2.2.1 CUDA的软件开发简介
• 2.2.2 CUDA在Linux的安装、配置、编译及调试
• 2.2.3 CUDA C的程序结构
• 2.2.4 CUDA编程框架
• 2.2.5 kernel核函数的调用
• 2.2.6 CUDA内存机制
• 2.2.7 CUDA线程协作及通信机制
• 2.3 本章小结
• 第三章 基于GPU的FLOYD算法的实现
• 3.1 问题的来源及背景知识
• 3.2 串行的Floyd Warshall算法的实现与改进
• 3.2.1 Floyd Warshall串行算法
• 3.2.2 Floyd Warshall串行算法的实现
• 3.2.3 Floyd Warshall串行算法的实例分析
• 3.3 基于GPU的并行Floyd算法的实现
• 3.3.1 并行设计策略
• 3.3.2 内核函数设计
• 3.3.3 并行的Floyd算法的实现
• 3.4 分块后GPU并行Floyd Warshall算法
• 3.4.1 原矩阵按主模块划分子矩阵
• 3.4.2 分阶段按子矩阵并行计算
• 3.4.3 内存和网格布局
• 3.4.4 内核函数设计
• 3.4.5 分块后并行算法实现
• 3.5 三种实验结果的比较与分析
• 3.5.1 实验平台和数据集说明
• 3.5.2 实验结果
• 3.5.3 实验结果比较与分析
• 3.6 本章小结
• 第四章 物流配送中心选址的最短路径问题
• 4.1 配送中心选址问题简介
• 4.1.1 配送中心的含义和功能
• 4.1.2 选址模型
• 4.1.3 选址方法
• 4.1.4 鲍姆尔沃尔夫模型配合使用解析法
• 4.2 配送中心选址问题中的 APSP 问题
• 4.2.1 APSP串行算法的比较
• 4.2.2 APSP问题中并行算法的选择
• 4.3 利用并行Floyd算法实现配送中心选址
• 4.4 最短路径求和的并行化
• 4.4.1 并行规约加法
• 4.4.2 改进后的并行规约加法
• 4.5 实验结果分析
• 4.6 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 研究成果及发表的学术论文
• 作者和导师简介
• 硕士研究生学位论文答辩委员会决议书