HotSort: A New GPU Sorting Algorithm

Earlier this year I determined I was going to need a specialized sorting algorithm in order to complete another GPU project.

I needed a sorter that was portable, in-place, supported key-vals wider than 32-bits and could sort binned (tiled) independent data sets output by other GPU kernels.

But most of all, the sorting algorithm had to be uber-fast on small GPUs.

A number of months later HotSort was completed. I’ve achieved most of my design goals and exceeded a few of them.

The HotSort algorithm outperforms the current GPU champ — Thrust Radix Sort — by a large margin up until ~8m elements on an NVIDIA Kepler GTX 680 GPU. You can see some performance plots here. The implementation shows similar advantages on both small and large Fermi and GT200 devices.

When simultaneously sorting subarrays containing 1k to 1m elements then HotSort can achieve sustained sorting rates from 1 billion to over 10 billion keys/sec. on a Kepler GTX 680. This is exactly what I wanted.

I’m currently testing support for wider key-val sizes — u32b32, u64 and u64b32.

Also, for those of you with eagle eyes, you can see that the algorithm shows significant roll-off after its peak throughput. Clearly that implies the algorithm is not exhibiting O(nlgn) complexity past this point. Don’t fret, the roll-off will be fixed and HotSort will become competitive on very large arrays.

I’m expecting the sorting gurus from NVIDIA — Merrill, Baxter, Harris, Garland, et al. — to improve their own truly awesome implementations now that they have a target. Always good to have a competitor!

Watch here for more updates on HotSort!