CUDA Papers

A collection of research papers and projects utilizing CUDA technology

Designing Efficient Sorting Algorithms for Manycore GPUs

http://mgarland.org/files/papers/nvr-2008-001.pdf

Abstract

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 and our merge sort is the fastest comparison-based sort reported in the literature. Our radix sort is up to 4 times faster than the graphics-based GPUSort and 2 times faster than other CUDA-based radix sorts. It is also highly competitive with even the most carefully optimized multi-core CPU sorting 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’s Tesla architecture and efficient data-parallel primitives, particularly parallel scan. While targeted at GPUs, these algorithms should also be well-suited for other manycore processors.

Authors

Nadathur Satish, University of California, Berkeley

Mark Harris, Michael Garland, NVIDIA Corporation

Leave a Reply