Kepler GPU accelerated recursive sorting using dynamic parallelism

This paper focuses on the performance gain obtained on the Kepler graphics processing units (GPUs) for multi-key quicksort. Because multi-key quicksort is a recursive-based algorithm, many of the researchers have found it tedious to parallelize the algorithm on the multi and many core architectures. A survey of the state-of-the-art string sorting algorithms and a robust insight of the Kepler GPU architecture gave rise to an intriguing research idea of matching the template of multi-key quicksort with the dynamic parallelism feature offered by the Kepler-based GPU's. The CPU parallel implementation has an improvement of 33 to 50% and 62 to 75 improvement when compared with 8-bit and 16-bit parallel most significant digit radix sort, respectively. The GPU implementation of multi-key quicksort gives 6× to 18× speed up compared with the CPU parallel implementation of parallel multi-key quicksort. The GPU implementation of multi-key quicksort achieves 1.5× to 3× speed up when compared with the GPU implementation of string sorting algorithm using singleton elements in the literature.