high performance computing on graphics processing units: hgpu.org

We present a new technique for sorting data into spatial bins or buckets using a graphics processing unit (GPU). Our method takes unsorted point data as input and scatters the points, in sorted order, into a set of bins. This is a key operation in the construction of spatial data structures, which are essential for applications such as particle simulation or collision detection. Our technique achieves better performance scaling than previous methods by exploiting geometry shaders to progressively trim the size of the working set. We also leverage predicated rendering functionality to allow early termination without CPU/GPU synchronization. Furthermore, unlike previous techniques, our method can guarantee sorted output without requiring sorted input. This allows our method to be used to implement a form of bucket sort using the GPU.