high performance computing on graphics processing units: hgpu.org

Sorting is a fundamental problem in computer science, and the strict sorting usually means a strict order with ascending or descending. However, some applications in reality don’t require the strict ascending or descending order and the approximate ascending or descending order just meets the requirement. Graphics processing units (GPUs) have become accelerators for parallel computing. In this paper, based on the popular CUDA parallel computing architecture, we propose high performance approximate sort algorithm running on multicore GPUs. The algorithm divides the distribution interval of input data into multiple small intervals, and then uses the processing cores of GPUs to map the data into the different intervals in parallel. Finally by combining the small intervals, we can make the data between the different intervals in order state and the data in the same interval is disorder state. Thus we can get the approximate sorting result and the result is characterized by a general order but local disorder. By utilize the massive core of GPUs to parallel sort data, the algorithm can greatly shorten the execution time. Radix sort is the fastest GPUs-based sorting and the experimental results show that our approximate sort algorithm is two times as fast as the radix sort and far exceeds all the GPUs-based sorting.