A comparison-free sorting algorithm on CPUs and GPUs.
Saved in:
| Title: | A comparison-free sorting algorithm on CPUs and GPUs. |
|---|---|
| Authors: | Abdel-Hafeez, Saleh1 sabdel@just.edu.jo, Gordon-Ross, Ann2,3 anngordonross@ufl.edu, Abubaker, Samer1 |
| Source: | Journal of Supercomputing. Nov2018, Vol. 74 Issue 11, p6369-6400. 32p. |
| Subjects: | Algorithm software, Implementation of Computer-Based Models, The (Book), Parallel Computing: Methods, Algorithms & Applications (Book), Efficient Parallel Algorithms (Book), Speed |
| Abstract: | This paper presents a new sorting algorithm that sorts input data elements without any comparison operations between the data—comparison-free sorting. Our algorithm’s time complexity is on the order of O(N) for both single- and multi-threaded CPU and many-core GPU implementations. Our results show speedups on average of 4.6 × , 4 × , and 3.5 × for single-threaded CPU, 8-threaded CPU, and many-threaded GPU implementations, respectively, for input sizes ranging from 27 to 230 elements as compared to common sorting algorithms for a wide variation of element distributions, ranging from all unique elements to a single repeated element. In addition, our proposed algorithm more efficiently utilizes the GPU architecture as compared to a multi-core CPU architecture, showing a speedup of approximately 4 × for input sizes ranging from 27 to 230 elements. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Supercomputing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
Be the first to leave a comment!
