Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sorting algorithms with CUDA

ashwanirathee.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Sorting algorithms with CUDA

#11

Post by giovannibonetti »

almostgotcaught wrote: post #7
giovannibonetti wrote: post #3

For a more convenient way to use GPUs for algorithms like this, the Futhark language [1] can be very valuable. It is a very high-level language that compiles to GPU instructions, which can be accessed as Python libraries. In their website there is an example of a merge sort implementation [2]. [1] https://futhark-lang.org/ [2] https://futhark-lang.org/examples/merge-sort.html

Do you use futhark in prod? Do you use it at all actually?

I don't use it at all currently because the problems it solves do not come up at my job. But if they did, I would gladly use it.

If your job involves a lot of heavy number crunching it might be useful.

Re: Sorting algorithms with CUDA

#12

Post by winwang »

giovannibonetti wrote: post #11
almostgotcaught wrote: post #7

Earlier quoted context omitted.

Do you use futhark in prod? Do you use it at all actually?

I don't use it at all currently because the problems it solves do not come up at my job. But if they did, I would gladly use it. If your job involves a lot of heavy number crunching it might be useful.

I don't use it because it didn't seem stable for CUDA when I tried it out.

As for number crunching, I'd probably use CuPy (outside of the typical ML stuff).

Re: Sorting algorithms with CUDA

#13

Post by spenczar5 »

As the other posts have said, this isn't the right algorithm. Onesweep and its kin are cool but intimidating. The magic is easier to understand if one looks into the core algorithm: radix sort.

A very readable explanation is here: https://gpuopen.com/download/publications/Introduction_to_GP...

It turns out that radix sort can be implemented in a way that is very straightforward to parallelize. It's a beautiful and elegant approach and worth knowing about!

Re: Sorting algorithms with CUDA

#14

Post by pca006132 »

gregw2 wrote: post #8

The TL;DR is the implementer was able to get use GPUs to get merge sort speedups that exceeded CPUs once the number of elements being sorted was >10,000,000. thrust::sort is an Nvidia C++ library; I am not clear whether it is related to CUDA or not actually; the article author started out with CUDA implementing a merge sort, but once it was slower than CPU the author tried thrust::sort library and was able to get a f…

1. Parallel radix sort (CPU or GPU) can also be pretty fast. For input distributions without too much pattern and keys that are not too large, radix sort is probably the fastest if you can use it.

2. For typical applications, memory transfer speed matters more than sorting performance on the GPU. If most of your work is done on the CPU, transfering the memory to the GPU may take more time than sorting the array. Not sure if unified memory (apple M series chips and AMD new APU) can remedy this though.

Re: Sorting algorithms with CUDA

#15

Post by winwang »

gregw2 wrote: post #8

The TL;DR is the implementer was able to get use GPUs to get merge sort speedups that exceeded CPUs once the number of elements being sorted was >10,000,000. thrust::sort is an Nvidia C++ library; I am not clear whether it is related to CUDA or not actually; the article author started out with CUDA implementing a merge sort, but once it was slower than CPU the author tried thrust::sort library and was able to get a f…

Not a database engine, but I'm processing distributed dataframes (~400TB). We're seeing a perf/price ratio around 3x~4x, though it's only a limited sample of workloads/datasets. (Note: we are not sorting, yet)

As far as I can tell, it's less so that the payoff is small, but that the payoff is small considering the maturity/scarcity of GPU programming, and availability of GPUs (esp. on-prem).

Re: Sorting algorithms with CUDA

#17

Post by jedbrooke »

nice! this reminds me of a small project I did in college implementing bitonic sort[0] in CUDA for a gpu accelerated Burrow-Wheelers transform

https://github.com/jedbrooke/cuda_bwt

I believe I got the implementation for bitonic sort here: https://gist.github.com/mre/1392067

[0]: https://en.wikipedia.org/wiki/Bitonic_sorter

Re: Sorting algorithms with CUDA

#18

Post by taeric »

raphlinus wrote: post #5

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/

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

Re: Sorting algorithms with CUDA

#20

Post by almostgotcaught »

giovannibonetti wrote: post #11
almostgotcaught wrote: post #7

Earlier quoted context omitted.

Do you use futhark in prod? Do you use it at all actually?

I don't use it at all currently because the problems it solves do not come up at my job. But if they did, I would gladly use it. If your job involves a lot of heavy number crunching it might be useful.

Lololol then why are you recommending it like you know anything about it? I will never understand this kind of comment on hn - like you don't get why hyping something up that you don't actually understand is bad?
Post reply on HN