Faster Radix Sort via Virtual Memory and Write-Combining

Details Faster Radix Sort via Virtual Memory and Write-Combining Faster Radix Sort via Virtual Memory and Write-Combining

2010-08-17

arxiv.org/abs/1008.2849v2

Computer Science

Data Structures and Algorithms

Scientific paper

Sorting algorithms are the deciding factor for the performance of common operations such as removal of duplicates or database sort-merge joins. This work focuses on 32-bit integer keys, optionally paired with a 32-bit value. We present a fast radix sorting algorithm that builds upon a microarchitecture-aware variant of counting sort. Taking advantage of virtual memory and making use of write-combining yields a per-pass throughput corresponding to at least 88 % of the system's peak memory bandwidth. Our implementation outperforms Intel's recently published radix sort by a factor of 1.5. It also compares favorably to the reported performance of an algorithm for Fermi GPUs when data-transfer overhead is included. These results indicate that scalar, bandwidth-sensitive sorting algorithms remain competitive on current architectures. Various other memory-intensive applications can benefit from the techniques described herein.

Affiliated with

Also associated with

No associations

Rating

Faster Radix Sort via Virtual Memory and Write-Combining 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 Faster Radix Sort via Virtual Memory and Write-Combining, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Radix Sort via Virtual Memory and Write-Combining will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-397569