High Performance Approximate Sort Algorithm Using GPUs
- DOI
- 10.2991/csic-15.2015.28How to use a DOI?
- Keywords
- Sorting, Parallel computing, High performance, GPUs, CUDA
- Abstract
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.
- Copyright
- © 2015, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Jun Xiao AU - Hao Chen AU - Jianhua Sun PY - 2015/07 DA - 2015/07 TI - High Performance Approximate Sort Algorithm Using GPUs BT - Proceedings of the 2015 International Conference on Computer Science and Intelligent Communication PB - Atlantis Press SP - 121 EP - 124 SN - 2352-538X UR - https://doi.org/10.2991/csic-15.2015.28 DO - 10.2991/csic-15.2015.28 ID - Xiao2015/07 ER -