High Performance Approximate Sort Algorithm Using GPUs

Jun Xiao, Hao Chen, Jianhua Sun
College of Computer Science and Electronic Engineering, Hunan University, Changsha, China
International Conference on Computer Science and Intelligent Communication (CSIC 2015), 2015


   title={High Performance Approximate Sort Algorithm Using GPUs},

   author={Xiao, Jun and Chen, Hao and Sun, Jianhua and Changsha, China},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: