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下的算法并行具有一定的可行性和高效性。