Designing efficient sorting algorithms for manycore GPUs
University of California, Berkeley
Parallel and Distributed Processing Symposium, International In Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, pp. 1-10, (2009).
@conference{satish2009designing,
title={Designing efficient sorting algorithms for manycore GPUs},
author={Satish, N. and Harris, M. and Garland, M.},
booktitle={Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on},
pages={1–10},
issn={1530-2075},
year={2009},
organization={IEEE}
}
We describe the design of high-performance parallel radix sort and merge sort routines for manycore GPUs, taking advantage of the full programmability offered by CUDA. Our radix sort is the fastest GPU sort reported in the literature, and is up to 4 times faster than the graphics-based GPUSort. It is also highly competitive with CPU implementations, being up to 3.5 times faster than comparable routines on an 8-core 2.33 GHz Intel Core2 Xeon system. Our merge sort is the fastest published comparison-based GPU sort and is also competitive with multi-core routines. To achieve this performance, we carefully design our algorithms to expose substantial fine-grained parallelism and decompose the computation into independent tasks that perform minimal global communication. We exploit the high-speed on-chip shared memory provided by NVIDIA
November 5, 2010 by hgpu
