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

31–40 of 44 posts

Re: Sorting algorithms with CUDA

#31

Post by anonymoushn »

yorwba wrote: post #29
anonymoushn wrote: post #28

Earlier quoted context omitted.

I always ask in these threads, what sort of data do you have that cannot be divided into several integers, such that sorting by those integers according to some priority implements your comparator correctly, and also your comparator is not so expensive as to be impractical? on one occasion someone replied "sorting unicode strings in collation order" but it doesn't seem like recomputing the collation inside of each co…

A sequence of integers such that sorting by those integers implements the comparator correctly is precisely what the Unicode Collation Algorithm produces as its sort key. https://www.unicode.org/reports/tr10/#Scope

Yes.

Re: Sorting algorithms with CUDA

#32

Post by diggan »

xyzsparetimexyz wrote: post #22
taeric wrote: post #18

Earlier quoted context omitted.

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

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.

Re: Sorting algorithms with CUDA

#33

Post by 73kl4453dz »

jandrewrogers wrote: post #23
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…

Modern database engines are bandwidth bound. Moving data to and from GPUs is expensive and slow by database engine standards so any performance gain due to higher memory bandwidth is usually lost in the data transfer overhead and much lower effective I/O bandwidth. Every database co-processor, not just GPUs, have had the same issue.

As they say, a coprocessor is a box that turns your cpu-bound problem into an i/o-bound problem.

Re: Sorting algorithms with CUDA

#34

Post by raphlinus »

taeric wrote: post #18
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.

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.

Re: Sorting algorithms with CUDA

#35

Post by tantalor »

diggan wrote: post #32
xyzsparetimexyz wrote: post #22

Earlier quoted context omitted.

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".

Re: Sorting algorithms with CUDA

#36

Post by ltbarcly3 »

Let me save you the time: Someone wrote a sorting algorithm on a GPU. It was slow. It's not state of the art and they aren't an expert. It's not clear that they know how to use a GPU effectively. This is just someone's personal playing with GPU programming. (Not judging, but there's literally nothing interesting here at all to most people who would be attracted by the title. It's just a personal blog post.)

Re: Sorting algorithms with CUDA

#37

Post by shiandow »

anonymoushn wrote: post #28
torginus wrote: post #27

Earlier quoted context omitted.

Yeah, but radix sort requires you to have an ordered integer key, not just two objects being comparable, like with most general sorting techniques.

I always ask in these threads, what sort of data do you have that cannot be divided into several integers, such that sorting by those integers according to some priority implements your comparator correctly, and also your comparator is not so expensive as to be impractical? on one occasion someone replied "sorting unicode strings in collation order" but it doesn't seem like recomputing the collation inside of each co…

Best I've been able to come up with is fractions. Though true fractions are rare (and can be converted to a sequence of integers that can be sorted lexicographically, see continued fractions).

Technically floats qualify, but not in an interesting way since you basically just need to take care of the sign bit and a few special cases.

Really most things can be sorted with radix sort, though I wouldn't want to be the one having to implement it for unicode strings (sorting text in general is one of those problems you'd preferably let other people solve for you).

Re: Sorting algorithms with CUDA

#39

Post by tverbeure »

tantalor wrote: post #35
diggan wrote: post #32

Earlier quoted context omitted.

> 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."

Re: Sorting algorithms with CUDA

#40

Post by m-schuetz »

DeathArrow wrote: post #21

I think you need to have huge arrays to worth sorting them on GPU. Copying data between RAM and GPU and taking it back will take some time.

Some render algorithms require sorting, like the currently hugely popular gaussian splats. Those sort like 5 to 20 million items per frame, in real-time.
Post reply on HN