Proceedings of the 2015 International Conference on Computer Science and Intelligent Communication

High Performance Approximate Sort Algorithm Using GPUs

Authors
Jun Xiao, Hao Chen, Jianhua Sun
Corresponding Author
Jun Xiao
Available Online July 2015.
DOI
https://doi.org/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/).

Download article (PDF)

Volume Title
Proceedings of the 2015 International Conference on Computer Science and Intelligent Communication
Series
Advances in Computer Science Research
Publication Date
July 2015
ISBN
978-94-62520-84-4
ISSN
2352-538X
DOI
https://doi.org/10.2991/csic-15.2015.28How to use a DOI?
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  - https://doi.org/10.2991/csic-15.2015.28
ID  - Xiao2015/07
ER  -