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

《基于gpu的空间并行算法研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP312论文编号：102871616-S008学科分类号：081200硕士学位论文基于GPU的空间并行算法研究与实现研究生姓名潘茜学科、专业计算机科学与技术研究方向数据管理与知识工程指导教师张育平副教授南京航空航天大学研究生院计算机科学与技术学院二О一六年三月NanjingUniversityofAeronauticsandAstronauticsTheGraduateSchoolCollegeofComputerScienceandTechnologyResearchandImplementationofSpaceParallelAlgo

2、rithmbasedonGPUAThesisinComputerScienceandTechnologybyPANQianAdvisedbyAssociateProf.ZHANGYupingSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringMarch,2016南京航空航天大学硕士学位论文摘要GPU(GraphicsProcessingUnits)是由NVIDIA公司研发的一种专门用在移动设备上的微处理器。GPU不仅促进了图像处理等应用领域的发展，而

3、且为图形学以外的其他领域提供了良好的运行平台。因此，从传统问题入手，选择典型算法，使其借助GPU平台得以实现并行加速，就显得十分重要了。论文主要选择了快速排序法(Quicksort)、R-Tree索引和K-近邻连接算法(K-Nearest-NeighborJoin,KNNJ)。快速排序法在分区过程中将消耗大量时间，对其的大多改进并没有从本质上改变分区速度慢的问题。R-Tree是空间数据处理中一种非常常用的索引结构，对于算法加速起着至关重要的作用。KNNJ算法是空间数据查询中最常见的算法之一，一般采用暴力搜索，计算量十分庞大。因此，针对GPU的高性能计算架

4、构，论文对快速排序法、R-Tree索引和KNNJ算法进行了改进和优化。具体研究工作主要集中在以下三个方面：1.通过对传统串行快速排序法的分析比较，选择随机数产生器生成枢轴元素，结合快速排序分区可并行性的特点，对快速排序法分初始化、预处理、重定位、最终排序四个步骤进行处理，实现了基于GPU的快速排序算法的并行改进。2.利用无依赖并行和串行同步计算的形式化定义了GPU并行编程模型，针对此并行抽象模型，提出了R-Tree索引的并行快速构建。在索引构建过程中，引入最小外包框的概念，利用递归网格排序算法以快速确立空间划分函数，使得索引构建符合无依赖并行和串行同步计

5、算抽象。3.针对K-近邻连接本身存在的可并行性特点，论文基于GPU对其实现并行，共分为四个部分。第一部分是建立索引机制；第二部分是欧氏距离的并行计算；第三部分是对求得距离的并行排序；最后引入KNN扩展框的概念，限定子树索引中所有对象KNNJ查询范围，获得最近的K个对象。论文将这种基于GPU平台的查询算法称为G-rKNNJ(R-TreebasedKNNJ)算法。通过以上算法的并行改进，实验结果表明，在不断更改数据参数的情况下，GPU下的算法并行具有一定的可行性和高效性。关键字：GPU，快速排序，R-Tree索引，最近邻搜索，并行计算i基于GPU的空间并行算

6、法研究与实现ABSTRACTGPU(GraphicsProcessingUnits)isamicroprocessordevelopedbyNVIDIA,whichisusedinmobiledevices.GPUnotonlypromotesthedevelopmentofimageprocessingandotherapplications,butalsoprovidesagoodoperatingplatformforotherfields.Therefore,itisveryimportanttoselectatypicalalgorithm,w

7、hichisbasedontheGPUplatformtorealizeparallelacceleration.Quicksort,R-TreeindexandK-Nearest-NeighborJoinarethemainmethodsinthisthesis.Quicksortmethodwillconsumealotoftimeintheprocessofpartitioning.Therearemoreimprovements,buttheproblemoftheslowspeedofpartitionstillcannotbesorted.R

8、-Treeisaverycommonindexstructureinspatia