GPU sample sort

Details GPU sample sort GPU sample sort

2009-09-30

arxiv.org/abs/0909.5649v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we present the design of a sample sort algorithm for manycore GPUs. Despite being one of the most efficient comparison-based sorting algorithms for distributed memory architectures its performance on GPUs was previously unknown. For uniformly distributed keys our sample sort is at least 25% and on average 68% faster than the best comparison-based sorting algorithm, GPU Thrust merge sort, and on average more than 2 times faster than GPU quicksort. Moreover, for 64-bit integer keys it is at least 63% and on average 2 times faster than the highly optimized GPU Thrust radix sort that directly manipulates the binary representation of keys. Our implementation is robust to different distributions and entropy levels of keys and scales almost linearly with the input size. These results indicate that multi-way techniques in general and sample sort in particular achieve substantially better performance than two-way merge sort and quicksort.

Affiliated with

Also associated with

No associations

Rating

GPU sample sort does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with GPU sample sort, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and GPU sample sort will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-590331