Research And Implementation Of Space Parallel Algorithm Based On GPU

GPU(Graphics Processing Units) is a microprocessor developed by NVIDIA, which is used in mobile devices. GPU not only promotes the development of image processing and other applications, but also provides a good operating platform for other fields. Therefore, it is very important to select a typical algorithm, which is based on the GPU platform to realize parallel acceleration.Quicksort, R-Tree index and K-Nearest-Neighbor Join are the main methods in this thesis. Quicksort method will consume a lot of time in the process of partitioning. There are more improvements, but the problem of the slow speed of partition still cannot be sorted. R-Tree is a very common index structure in spatial data processing, and plays an important role in the acceleration of the algorithm. KNNJ algorithm is one of the most common algorithms in spatial data query. However, the general use of violence search method, the calculation is very large.For the high performance computing architecture of GPU, the thesis mainly focuses on the analysis and research of the fast sorting method, R-Tree index and KNNJ algorithm. The research work of this thesis is mainly focused on the following three aspects:1. Through the analysis and comparison of the traditional serial quicksort, the random number generator is selected to generate the pivot element, according to the features of quicksort can be parted, the quicksort is executed by four steps: initialization, preprocessing, repositioning and final sequencing. The parallel improvement of the quicksort is realized based on GPU.2. The parallel programming model of GPU is defined based on the Independent Parallel and Serial Synchronization, and the R-Tree index is proposed according to the abstract model. In the construction of index, the thesis introduces the concept of the minimum bounding box, and uses the Sort-tile-recursive algorithm to quickly establish the spatial partition function, which makes the index construct conform to the Independent Parallel and Serial Synchronization model.3. In view of the characteristics of the KNNJ, making it to achieve parallel based on GPU and it is divided into four parts. The first is the establishment of index. The second is to compute Euclidean distance. The third part is the sorting of the distance. Finally, we give the concept of KNN extension box, narrow the scope of inquiry, and obtain the nearest object set of K for each object. In this thesis, the method is called G-rKNNJ(R-Tree based KNNJ) algorithm.Through the parallel improvements of above algorithms, the results show that the algorithms are feasible and efficient when continuous changing data parameters.