Item — HN Reader

This is not a fast way to sort on GPU. The fastest known sorting algorithm on CUDA is Onesweep, which uses a lot of sophisticated techniques to take advantage of GPU-style parallelism and work around its limitations.

Linebender is working (slowly) on adapting these ideas to GPUs more portably. There's a wiki page here with some resources:

https://linebender.org/wiki/gpu/sorting/

2 comments

Onesweep paper (Nvidia 2022): https://research.nvidia.com/publication/2022-06_onesweep-fas...

Onesweep GitHub repo: https://github.com/b0nes164/GPUSorting

The second one is Thomas Smith's independent reimplementation of Onesweep. For the official version, see https://github.com/NVIDIA/cccl . The Onesweep implementation is in cub/cub/agent/agent_radix_sort_onesweep.cuh .

To be fair, I took this far more as an exploration on writing CUDA than I did an attempt at the best sorting method.

Yup, nothing wrong with clear exposition about simpler algorithms, there's definitely a place for that. I just thought HN readers should have some more context on whether we were looking at a programming exercise or state of the art algorithms.

Sure but it's still incredibly misleading.

> it's still incredibly misleading

What, exactly, is misleading? The title of the blogpost is "Sorting Algorithms with CUDA" and I didn't get the feeling that the author is touting their "Bottom-up iterative merge sort" is the fastest possible way of sorting with CUDA. There is even a "Future Work" section at the end, implying even the author know it can be done better.

I think the faux-academic style is throwing people off.

If author is taking a truly academic perspective, then a section should be included with background on state of the art, best known performance, etc.

If this is just a blog post (which is more likely) with less rigor, then the style could reflect that better. For instance, calling it an "introduction" or "exercise".

Reread the first paragraph of this blog post.

How many academic papers start with "I went for a NVIDIA recruiting event some days ago, that was a great event and it motivated me to try to rewrite the sorting algorithms using CUDA."