1203

Designing efficient sorting algorithms for manycore GPUs

Nadathur Satish,Mark Harris,Michael Garland
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}

}

Download Download (PDF)   View View   Source Source   

4418

views

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
Rating: 2.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: