Abstract
Efficient implementations of various sorting algorithms on Graphics Processing Unit (GPU) had been studied for years, owing to their technical importance in many applications. However, as the computational power of GPU and data size increases, the performance gap of computation and communication enlarges exponentially. As the result, the data movement between host (CPU) and device (GPU) becomes the performance bottleneck. For sorting algorithms, the time of data movement can take over 60% of total execution time when the data size is larger than 220 on Fermi C2070. In this thesis, we propose a framework to enhance the performance of GPU sorting algorithms, which utilizes the streams concurrency technique to overlap the communication and computation time. First, data are partitioned into buckets. Each bucket has roughly the same size and data in each bucket has partial order to the data in other buckets. Second, data in each bucket are sorted separately on GPU using preferred sorting algorithms. Last, the sorting and data output are overlapped to hide the communication time. The major challenge of this framework is in the first step: to partition the data into ordered buckets of roughly equal size. The sample sort algorithm is employed to resolve this problem. Three sorting algorithms were implemented to justify the effectiveness of this framework: radix sort, merge sort, and bitonic sort. Experiments show that nearly 25% time performance improvement of radix sort can be obtained when n=2^28. For merge sort, the improvement is 8% ; and for bitonic sort, up to 8.32% performance improvement can be achieved.