4 ms·

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 o

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/ https://linebender.org/wiki/gpu/sorting/

gregw2 2y ago
Onesweep paper (Nvidia 2022): https://research.nvidia.com/publication/2022-06_onesweep-faster-least-significant-digit-radix-sort-gpus https://research.nvidia.com/publication/2022-06_onesweep-fas... Onesweep GitHub repo: https://github.com/b0nes164/GPUSorting https://github.com/b0nes164/GPUSorting
- raphlinus 2y ago
  The second one is Thomas Smith's independent reimplementation of Onesweep. For the official version, see https://github.com/NVIDIA/cccl https://github.com/NVIDIA/cccl . The Onesweep implementation is in cub/cub/agent/agent_radix_sort_onesweep.cuh .
taeric 2y ago
To be fair, I took this far more as an exploration on writing CUDA than I did an attempt at the best sorting method.
- xyzsparetimexyz 2y ago
  Sure but it's still incredibly misleading.
  - diggan 2y ago
    > 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.
    - tantalor 2y ago
      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".
      - tverbeure 2y ago
        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."
- raphlinus 2y ago
  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.

gregw2 2y ago

Onesweep paper (Nvidia 2022): https://research.nvidia.com/publication/2022-06_onesweep-faster-least-significant-digit-radix-sort-gpus https://research.nvidia.com/publication/2022-06_onesweep-fas... Onesweep GitHub repo: https://github.com/b0nes164/GPUSorting https://github.com/b0nes164/GPUSorting

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

taeric 2y ago

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

xyzsparetimexyz 2y ago
Sure but it's still incredibly misleading.
- diggan 2y ago
  > 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.
  - tantalor 2y ago
    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".
    - tverbeure 2y ago
      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."
raphlinus 2y ago
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.