Sorting
With special contributions from Michael Garland
Abstract
This chapter covers two types of sorting methods that rearrange keys (and their associated values) on GPUs into a desired order in parallel. The first type of sorting method is radix sort, which sorts keys by distributing them across buckets. We show that using the shared memory for output tiling and applying thread coarsening improves coalescing and reduces the overhead of the global exclusive scan. Although radix sort has the advantage of having a computational complexity that is lower than O(N*log(N)), it does not work for keys with complex ordering requirements. Therefore we also briefly look at the parallelization of comparison-based sorting that is applicable to ...
Get Programming Massively Parallel Processors, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
