Article Preview
TopIntroduction
Sorting is one of the widely studied algorithmic problems in the computer science (Cormen, Leiserson, Rivest, & Stein 2001; Martin, 1971). It appears in a wide variety of applications and evolves with various computational architectures (Akl, 1985). Hence, the efficient implementations of sorting algorithms profoundly influence the performance of those applications. As the computer architecture evolved, there is a continuing requirement to design efficient sorting algorithms to use the underlying hardware's computing power. Current high-end graphics processing units (GPUs), contain up to hundreds cores per chip, are very popular in the high performance computing community. GPU is a massively multi-threaded processor and expects the thousands of concurrent threads to fully utilize its computing power. The ease of access GPUs by using Compute Unified Device Architecture (CUDA) (NVIDIA, 2009), as opposite to graphic APIs, has made the supercomputing available to the mass. The advantages of the computing power and memory bandwidth for modern GPUs have made porting applications on it become a very important issue.
Several excellent results for sorting algorithms on GPUs are obtained, including the internal and external sorting algorithms (Govindaraju, Gray, Kumar, & Manocha, 2006; Leischner, Osipov, & Sanders, 2010; Satish, Harris, & Garland, 2009). Among the internal sorting algorithms, CUDPP radix sort (Satish, Harris, & Garland, 2009) is currently the fastest sorting on GPUs and GPU sample sort (Leischner, Osipov, & Sanders, 2010) is considerably the fastest comparison-based sorting on GPUs. Comparing to CUDPP radix sort, GPU sample sort is more flexible and suitable for sorting the keys with a large size and is more robust over various data distributions, although it is slower than CUDPP radix sort on 32-bit keys. Both of them are the art of implementations for sorting algorithms on GPUs. However, the implementations for most of sorting algorithms on GPUs, including above algorithms, need either an extra space or the atomic operation support by GPUs.
In this paper, we address the above problems and propose a comparison-based sorting, shellsort, on GPUs, namely CUDA shellsort, that releases those constraints. In CUDA shellsort, we exploited the inherently embarrassing parallelism among each pass of shellsort and used the per-thread registers to accelerate the insertion operation on each subsequence (block) within a shellsort pass. Until the parallelism of a shellsort pass was insufficient (ex. <2048 concurrent threads), we switched it to the bitonic merge sort to sort blocks concurrently (ex. 2048-element blocks). After all blocks had sorted by the bitonic merge sort, an odd-even bitonic merge was used to rearrange the out-of-order data elements between two adjacent blocks. We demonstrated how to impose a block-wise structure on the parallel shellsort algorithm, bitonic merge sort, and odd-even bitonic merge. We also used registers to maintain a heap structure to avoid the shared memory bank conflict and result the efficient memory bandwidth utilization while keeping high GPU cores occupancy. The implementation of CUDA shellsort extracts the computing power of GPU cores, shared memory, and register file. CUDA shellsort needs O(logn) (n is a ratio of a size of input sequence and a given threshold) passes of memory access and is nearly the same as O(logkn) passes of the multi-way approach suggested by the literature (Leischner, Osipov, & Sanders, 2010). In the experimental tests, under the uniform distribution, CUDA shellsort is, on average, 37% faster than Thrust mergesort and two times faster than GPU quicksort. The performance of CUDA shellsort is nearly the same as that of GPU sample sort up to 32 million data elements, but only needs a constant space usage. These results showed that CUDA shellsort is one of the fastest comparison-based sorting on GPUs and is robust over various data distributions evaluated as by the literature (Helman, Bader, & JaJa, 1998).