基于GPU的空间并行算法研究与实现

发布时间：2017-10-14 13:27

  本文关键词：基于GPU的空间并行算法研究与实现

  更多相关文章： GPU 快速排序 R-Tree索引 最近邻搜索 并行计算

【摘要】：GPU(Graphics Processing Units)是由NVIDIA公司研发的一种专门用在移动设备上的微处理器。GPU不仅促进了图像处理等应用领域的发展,而且为图形学以外的其他领域提供了良好的运行平台。因此,从传统问题入手,选择典型算法,使其借助GPU平台得以实现并行加速,就显得十分重要了。论文主要选择了快速排序法(Quicksort)、R-Tree索引和K-近邻连接算法(K-Nearest-Neighbor Join,KNNJ)。快速排序法在分区过程中将消耗大量时间,对其的大多改进并没有从本质上改变分区速度慢的问题。R-Tree是空间数据处理中一种非常常用的索引结构,对于算法加速起着至关重要的作用。KNNJ算法是空间数据查询中最常见的算法之一,一般采用暴力搜索,计算量十分庞大。因此,针对GPU的高性能计算架构,论文对快速排序法、R-Tree索引和KNNJ算法进行了改进和优化。具体研究工作主要集中在以下三个方面:1.通过对传统串行快速排序法的分析比较,选择随机数产生器生成枢轴元素,结合快速排序分区可并行性的特点,对快速排序法分初始化、预处理、重定位、最终排序四个步骤进行处理,实现了基于GPU的快速排序算法的并行改进。2.利用无依赖并行和串行同步计算的形式化定义了GPU并行编程模型,针对此并行抽象模型,提出了R-Tree索引的并行快速构建。在索引构建过程中,引入最小外包框的概念,利用递归网格排序算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象。3.针对K-近邻连接本身存在的可并行性特点,论文基于GPU对其实现并行,共分为四个部分。第一部分是建立索引机制;第二部分是欧氏距离的并行计算;第三部分是对求得距离的并行排序;最后引入KNN扩展框的概念,限定子树索引中所有对象KNNJ查询范围,获得最近的K个对象。论文将这种基于GPU平台的查询算法称为G-rKNNJ(R-Tree based KNNJ)算法。通过以上算法的并行改进,实验结果表明,在不断更改数据参数的情况下,GPU下的算法并行具有一定的可行性和高效性。
【关键词】：GPU 快速排序 R-Tree索引 最近邻搜索 并行计算
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP391.41
【目录】：

• 摘要4-5
• ABSTRACT5-10
• 注释表10-11
• 缩略词11-12
• 第一章 绪论12-17
• 1.1 课题研究背景及意义12-13
• 1.1.1 研究背景12
• 1.1.2 研究意义12-13
• 1.2 国内外研究现状13-15
• 1.3 主要研究内容15-16
• 1.4 论文组织结构16-17
• 第二章 相关理论基础17-29
• 2.1 GPU概述17-22
• 2.1.1 GPU体系架构17-19
• 2.1.2 与多核CPU的区别19-20
• 2.1.3 与超级计算机的区别20-22
• 2.1.4 与分布式集群的区别22
• 2.2 CUDA简介22-26
• 2.2.1 Kernel函数23-24
• 2.2.2 线程结构24-25
• 2.2.3 CUDA存储模型25-26
• 2.3 NVIDIA Nsight简介26-28
• 2.4 本章小结28-29
• 第三章 基于GPU的快速排序法的并行实现29-37
• 3.1 快速排序法简介29-30
• 3.2 串行快速排序及其枢轴元素的选择30-31
• 3.2.1 串行快速排序法30-31
• 3.2.2 枢轴元素选取31
• 3.3 并行快速排序31-36
• 3.3.1 传统并行快速排序31-32
• 3.3.2 基于GPU的并行快速排序32-36
• 3.4 本章小结36-37
• 第四章 GPU下基于R-Tree索引的K-近邻连接算法37-57
• 4.1 K-近邻连接算法简介37-38
• 4.2 KNNJ算法主要流程38-39
• 4.3 基于GPU的R-Tree索引的建立39-49
• 4.3.1 R-Tree节点的距离定义40-41
• 4.3.2 并行计算模型41
• 4.3.3 GPU下R-Tree索引的快速构建41-49
• 4.4 基于GPU的并行KNNJ查询49-56
• 4.4.1 KNNJ并行求距离49-50
• 4.4.2 KNNJ并行距离排序50
• 4.4.3 基于R-Tree索引的KNNJ查询50-52
• 4.4.4 基于扩展框的剪枝策略52-55
• 4.4.5 GPU下基于R-Tree索引的KNNJ查询55-56
• 4.5 本章小结56-57
• 第五章 实验仿真及结果分析57-66
• 5.1 实验环境配置57-59
• 5.1.1 实验平台的搭建57-58
• 5.1.2 实验数据集介绍58-59
• 5.2 实验对比方案59
• 5.3 实验结果分析59-65
• 5.3.1 数据规模对快速排序法的影响60
• 5.3.2 节点数对索引建立的影响60-61
• 5.3.3 数据规模对索引建立的影响61-62
• 5.3.4 K值大小对KNNJ查询的影响62-63
• 5.3.5 索引节点数对KNNJ查询的影响63-64
• 5.3.6 数据规模对KNNJ查询的影响64-65
• 5.4 本章小结65-66
• 第六章 总结与展望66-67
• 6.1 本文主要工作总结66
• 6.2 下一阶段工作展望66-67
• 参考文献67-70
• 致谢70-71
• 在学期间的研究成果及发表的学术论文71

，

本文编号：1031333