World's fastest radix sort? 1B 32bit keys a second using a stock GTX 480 | Hacker News Reader

World's fastest radix sort? 1B 32bit keys a second using a stock GTX 480

code.google.com

74 pointsjunkbit31 comments

GPUs are scary fast if you have the 'right' problem.

That's why the sorting implementation is important. Unlike most CUDA programs which heavily relied on locality of data, sorting problem relies on the support of the global knowledge about key distribution. Even division-and-conquer methods such as qsort require a full scan over the dataset, which on CUDA architecture is painful. Duane's research concentrates on how to apply GPGPU architecture to a set of more general problems which traditionally relies on global access of data (thus, shared memory system).

Disclaimer: I didn't follow his work closely, so my interpretation may be misleading.

What I keep seeing is that the Fermi video game cards (GTX480) is faster than the scientific computing minded (Tesla C20) cards. According to those graphs, the difference isn't trivial either, which is kinda surprising.

There is a lot of misinformation in replies to this post. The Tesla cards do NOT have 4x more DP performance (the whole Fermi generation, which includes Tesla and gaming cards, have 4x the DP perf of the previous GT200 generation). Tesla cards NOT have higher accuracy. The differences between buying a Tesla card and a gaming card are: - Tesla cards have ECC memory, video cards do not. - When you buy a Tesla card, Nvidia supposedly gives you very good tech support (I've heard you can call their engineers directly) - Tesla cards have more GDDR memory: 3GB for the C2050, 6GB for the C2070, compared to 1.5GB for the highest end gaming card GTX480.

Some people are willing to pay a premium for the above 3 advantages, that's why Nvidia can sell Tesla cards at such a high price. IMO, the first advantage is overrated: Nvidia's ECC implementation (secdec) is unable to detect many multi-bit errors. Gaming cards offer at 10x better perf/price ratio, so it makes it hard to ignore them.

We had NVIDIA folks coming to our game studio, and they've said almost the same but for another set of applications - Basically if you want full support for Autodesk or Adobe products (3DS Max, Maya, MotionBuilder, Photoshop) then you should get Quadra card.

The Quadra has ECC, it's produced by NVIDIA itself (not 3rd party), and they have developed extensive driver support where each application that you run (Windows) would have specific settings that give you the best performace, quality or stability.

There are tons of other manifacturers that produce NVIDIA cards, but they don't put ECC memory, boost the GPU frequency until they almost don't burn, etc.

Also some specific features exist only for Quadra, that are not important for games - for example quick antialiased lines (just a simple example, there is more).

So what MRB is saying is right. At the surface it looks Quadra/Tesla are worse, but their stability is much better, and customer support is guaranteed.

NVIDIA can't simply support HW not built by them in large. It's not possible for them to know every kind of card there is.

For this integer program the difference is not due to accuracy, DP, or memory models. The GTX480 has 480 "cores" at 1.4 GHz while the C2050 has 448 "cores" at 1.15 GHz. I can't explain why Nvidia's more expensive card has lower performance other than they can get away with it.

In the case of the Fermi-class cards, you're paying for more memory (3 or 6GB vs 1 or 2), stability, tweaked drivers, and (possibly most importantly) error correction. It's really the same argument as for workstation graphics cards - consumer class cards are designed to sacrifice floating-point accuracy for maximum speed, and in some cases, this is unacceptable.

That said the 20- series is really freaking expensive. When I got my C1060's, they were ~$1500/per retail; I think the C2070's are nearly twice that.

It seems like Nvidia would have less of an image problem if the Teslas were the same performance and have more RAM and have ECC. (Also, the value of ECC is diminished if a Tesla is over 3x the price of a GeForce, because then you can run three times and vote.)

> It seems like Nvidia would have less of an image problem if the Teslas were the same performance and have more RAM and have ECC.

That might be hard when going for reliability. It's a bit like overclocking your CPU, you can do it, but it's outside of the warranty. In this case the overclockers are the third party board manufacturers that are trying to get an advantage over their competitors that they can paste on the box so that in the store when comparing two boxes the customer will pick theirs.

> (Also, the value of ECC is diminished if a Tesla is over 3x the price of a GeForce, because then you can run three times and vote.)

That's not really true. The majority of the situations where the Tesla boards are used you'll find multiple boards in one box already. The limiting factor here is how many boards you can pack in to a system, more = better. So if you'd use the 'voting' principle you'd be wasting tons of power, rackspace and host computers in order to offset the price of the ECC, not just the two extra cards.

In this case the overclockers are the third party board manufacturers that are trying to get an advantage over their competitors

I don't think so; most GeForce cards appear to use stock clocks and Nvidia reference PCBs and coolers.

The same happened when the 200 series came out, also the memory model is subtly different.

I expect we'll see the exact same thing happen as what happened with the 200 series, the first cards will be looked at as the crummy old ones as soon as the next batch hits the streets. You can pretty much expect the following:

a 1.4 GHz part

maybe a 1.8 or 2.0 GHz part

a dual chip card featuring 896 cores at the same power consumption level as the current 480GTX

I may be mistaken, it's my understanding that the video game cards are designed to be faster at the expense of accuracy, whereas the scientific computing cards are designed to have better accuracy at the expense of speed.

Are the game cards not following IEEE floating point spec? I really should ask this on the nvidia cuda forums to get a really good answer.

Edit: Wikipedia says that the Tesla cards have 4X higher double precision performance than the game cards, so that could be the explanation.

That's one part of it, the other part is that subtle changes to the memory model will take a while to be taken advantage of, most code is now optimized for the 200 series chips (of which the 480 mentioned here has two).

As with lots of GPU-accelerated benchmarks unfortunately, they ignore the time to transfer the 1B keys from main memory to the GPU and back.

That's not entirely fair. If you benchmark a sorting algorithm you normally don't measure the time it takes to bring the records in from the disk either.

Of course there is overhead, that's obvious, there would be overhead in any co-processor driven situation, but that overhead depends to a large extent on the host machine and the bus used to connect, so it would be reducing the value of the benchmark to include those figures in the timing.

Also, there are plenty of applications where the input to the radix sort would come from other kernels and/or where the output would go to other kernels.

In those cases there is no overhead.

Can you, jacquesm, or some other knowledgeable sort give an example of a situation which could call for this level of sorting?

Sorting a billion of anything in 1s seems likely to kick against other problems.

Just curious (I'm not asking why you'd want to, but you can tell me that too if you like).

There's a handful of ML algorithms where sorting is a bottleneck, or where the algorithm could have some complex data-structures ripped out if sorting were an order of magnitude faster. They're often hard to implement entirely on the GPU, though, so you'd have to be careful with the transfer to/from the GPU if you were using it solely for the sorting.

Particle simulations would be one example.

The problem is not only time from disk, it's time from memory.

Outside of a benchmark- that's latency you can hide though, right? Without reference to the specifics of this situation, which I don't claim to know much about, the co-processor can be sorting one dataset in it's local memory while the CPU is transferring data into another local buffer (or even, the co-processor can initiate the transfer itself using DMA).

Only to a limited extent. Assuming this is a regular-ish implementation of radix sort, you could start doing the first bucketing while data is being copied in. Likewise, you can copy out the sections which already have been fully sorted. But I would be surprised if you saw more than 10-15% percent speedup over naive copy execute copy.

Your observation is likely correct, but I was talking about sorting two or more independent sets, not partitioning the sort of one set; assuming that a "proper" (non benchmark) application will have several workloads waiting to be processed at a given time, so the GPU can be working on one while the data for the next is being transferred (so hiding the latency for the transfer for all but the first set).

[edit] I don't know how practical that is on real world hardware; a billion keys is obviously a lot of data to transfer.

A lot of applications generate their own data. The pure "on disk" piece might be a fraction of the total.

e.g., consider z-sorting vertices for a million-polygon model as it rotates (that's useful for some kinds of transparency.) Bandwidth to main memory is a small piece of the total.

That assumes that the data the should be sorted wasn't created on the GPU right?

It does seem like a nice tool for that case. I think a lot of people, though, especially reading the discussion at places like reddit, are expecting that this means you can now just replace your sort() call with a drop-in replacement gpu_sort(), getting a 4x speedup in the process, which is not likely to be true.

I have often wondered if you couldn't put the needed database indexes and other associated data onto a GPU , and have the GPU handle the optimization for the query, run the query, and then just return to the database server which blocks to go to to get the data; the indexes could be synced to disk of course but they would be run from the GPU.

There's a paper by some people who got MySQL to sort using the GPU, and got great speedup. That was quite old and I can't find it now.

However, a more recent paper is Accelerating SQL Database Operations on a GPU with CUDA: http://www.cs.virginia.edu/~skadron/Papers/bakkum_sqlite_gpg...

The references in that paper are pretty interesting, too.

That looks pretty cool, and the best performance seems to come from aggregating and doing floating point math.

SQLite is designed for embedding into cell phones and web browsers and other tiny devices, so I'd expect that there's quite a bit of room for optimizing the floating point math on server-grade hardware.

Radix sort is my favorite sort algorithm. Here, I made a little Radix sort video with sound: http://rasterburn.org/~sgt/stuff3/radixsort.avi

There's an ongoing thread in the CUDA forums about it: http://forums.nvidia.com/index.php?showtopic=175238

Reply on news.ycombinator.com