Sorting with GPUs: A Survey

by lainon • 9 years ago

148 50 9 years ago

frozenport• 9 years ago

The table at the end would benefit from a column indicating the availability of the source code.

exDM693• 9 years ago

Sorting is a fundamental problem so this is important stuff but I can't right now come up with a practical problem involving large sorting operations. Can anyone come up with a practical application for this? I have no doubt they exist.

I would think the breakeven point for using the GPU (assuming inputs and results are on the CPU) is several megabytes of millions or elements at least.

Writing this paper must have been a lot of effort. There are something like 50 different methods reviewed here. Good thing that papers like this exist.

pelario• 9 years ago

Two practical applications from top of my head:

* Do you want to build an index (for big data?), so that you can access your data fast (thing about a database). Well, the index construction is likely to do some sorting internally. * MapReduce algorithm has indeed more phases... one of it is sorting...so yes, when you are porocessing big data with map reduce, then the data is being sorted at some point.

fleitz• 9 years ago

Indexes don't really require data to be sorted, sorting is a consequence of adding data to many different types of index.

https://en.wikipedia.org/wiki/B-tree

ben-schaaf• 9 years ago

Rendering transparent models in real-time (ie. for games) requires a sorting step when they overlap. I can imagine a scene containing a couple hundred thousand transparent models that need sorting.

tomjakubowski• 9 years ago

I was very surprised that depth sorting for real time rendering was not listed among the potential applications in the abstract.

pjc50• 9 years ago

Isn't that usually done with the depth buffer?

exDM693• 9 years ago

That's obviously a good use case and doesn't even need to have that large of number of elements because the data could get consumed by the GPU, so no back-and-forth transfer necessary.

This paper was focused on comparison based sorting. Depth sorting can be done with GPU radix sort (which is super fast), because with minor modifications, floating point and integer comparison are equal for finite, not-NaN values (and games don't care about that).

skocznymroczny• 9 years ago

Are there any game engines that actually do the sorting? I thought they just render them in random order and hope for the best.

stcredzero• 9 years ago

Rendering transparent models in real-time (ie. for games) requires a sorting step when they overlap.

My game heavily uses a "find nearest n" operation on an R-Tree, then sorts by distance for AI operations.

ACow_Adonis• 9 years ago

It has potential in the field of data linking: Graph and database partitioning, merging, indexing, sorted-neighbourhood algorithms. And cases where you can't use hash-joins or comparison techniques because you're using the available ram and resources to hold something else.

Optimisation for cache-locality and branch prediction.

Any kind of repeatable scientific/datascience analysis operating across groups or cross-tabulation. Anything involving lag-like functions and relationships, time-series, relative positions (in households, neighbourhoods, countries, spatial relationships).

Perhaps i'm biased, I think i've grown up working with operations where having the data in an implicit order makes things a fair bit easier/more efficient.

Albeit, you're also right, it probably has to get up into the millions before you fundamentally care. But I do like to think I work on practical applications :P

roel_v3• 9 years ago

I have yet to see a non-trivial simulation model that doesn't need sorting at some point in its operations. But I do think you're right that sorting isn't something that would be bottleneck in today's mainstream applications of GPU's - games, compression/decompression (video, mostly) and graphics operations.

tromp• 9 years ago

Sorting also forms the bottleneck in several memory hard Proof-of-Work schemes. These differ from the general problem in two important ways:

1) the input data is generated from cryptographic hash functions, and can thus be considered random, leading to e.g. very even distribution of elements over buckets.

2) each round of sorting serves to identify groups of items that match on a subrange of their bits, and somehow transform these items.

There is a lot of cryptocurrency money to be made by developing the most optimized mining software and charging 1% or so "developer-fee" on the mining proceeds.

Ono-Sendai• 9 years ago

I think the most common practical problem for sorting large amounts of data is to enable efficient search operations later, for example binary search over sorted data.

I also agree that needing to sort large amounts of data fast is actually not that common a requirement.

EDIT: I would add that the speed of sorting on CPU is often underestimated. See my blog post about fast multithreaded radix sort on CPU here: http://www.forwardscattering.org/post/34

angrygoat• 9 years ago

Seismic exploration data needs to be sorted into various domains; for example, by offset, by receiver, or by shot. It is one of the faster operations but you can still end up CPU bound rather than I/O bound, especially if you're doing work on the fly in a GUI.

http://wiki.seg.org/wiki/CMP_sorting

barrkel• 9 years ago

I work for a startup that specializes in data matching (usually called reconciliation in banking / finance industry). Some core matching algorithms rely on comparing sorted input using sliding windows; others rely on bucketing of some kind; anything to avoid O(m*n) when comparing two lists.

The lists involved can easily run into the millions, depending on the domain.

dragontamer2• 9 years ago

I would think the breakeven point for using the GPU (assuming inputs and results are on the CPU) is several megabytes of millions or elements at least.

Well, the idea of GPU computing is to keep the data on the GPU as much as possible.

The CPU <---> GPU link is at best, 16x PCIe. Which is fast, but not anywhere close to the speed of HBM, GDDR5 or DDR4 RAM. (Exception: AMD's A10 operators, which have a GPU / CPU which shares on-chip cache memory. As well as the "Crystalwell" Intel chips IIRC. But these are rare chips that I doubt most people use)

So if you happen to be running a major algorithm on the GPU, you'll probably want to sort it as well, before bringing it back to the CPU. Under no circumstances should you be introducing a PCIe delay for a simple operation like sorting.

taeric• 9 years ago

Sorting has long been known as something that can be bound with more comparison units. Batcher's sort, as an example, is far from a new algorithm. So, to that end, being able to sort a collection in lgN time is quite appealing.

What I take this paper as doing, is seeing how close we are to being able to take it for granted that you can sort large collections in lgN time, instead of NlgN time. My guess is we are a ways from there, but probably not as far as I think.

lacksconfidence• 9 years ago

XGBoost recently added GPU support for training. As far as I'm aware one of the reasons the speedup is relatively small (vs say deep learning on CPU vs GPU) is that it spends a significant amount of time sorting which is not particularly fast on the GPU.

oelmekki2• 9 years ago

Cool to see research in that field, I realized this year that for gaming GPU and VRAM were actually more important than CPU and RAM, it probably tells something about underusage of GPU in general computing.

There's one big blocker as far as I can tell, though: portability. When it comes to gaming, neural networks, cryptomining, etc, I always see "only nvidia cards supported", or "work best on amd". If we were to use GPU in just any kind of application, we would need to have hardware abstraction library which support any kind of GPU, including intel chips.

Is such effort already being worked on, at any stage of completion?

idle_zealot• 9 years ago

Something like https://en.wikipedia.org/wiki/OpenCL ?

oelmekki2• 9 years ago

Awesome, thanks. I've seen the name mentioned several times, but I didn't know what was behind.

It seems (unsurprisingly for an hardware abstraction) that performance is a problem, but at least it's a problem that is being worked on. Maybe at some point we will stop to think "we can't implement that, that's way too massive to perform properly" and start thinking "this is a job for the GPU" :) At the very least, databases come to mind, with their sorting/filtering of massive data.

richdougherty• 9 years ago

Interesting article about OpenCL and Vulkan... https://www.pcper.com/reviews/Graphics-Cards/Follow-Neil-Tre...

VHRanger• 9 years ago

OpenACC

falcolas• 9 years ago

for gaming GPU and VRAM were actually more important than CPU and RAM

It's probably just the games I play, but these days I'm rarely GPU bound, just CPU bound. It would be great to see some frameworks make GPU accelerated physics (with automatic CPU fallback) easier for smaller game development companies to take advantage of.

For example: Factorio and Space Engineers are primarily CPU bound due to the tracking of millions of objects (Factorio) & physics (Space Engineers).

meschi• 9 years ago

Nvidia PhysX?

overcast• 9 years ago

It must be the games you're playing, large scale strategy? Everything in my gaming rig is from 2008(LGA1366). The only thing I've upgraded since then is video cards. I ran an I7 920 Nehalem chip up until last year, when I "upgraded" to a Xeon X5675 from ebay as a drop in cpu replacement. Runs everything I throw at it completely maxed out at 2560x1600 resolution vsynced to the monitor refresh rate of 60hz.

Eridrus• 9 years ago

AMD is taking a stab at this with ROCm/HIP/HCC to try and get a slice of the machine learning market: https://rocm.github.io/languages.html

I wish them all the best, but I haven't seen much adoption yet. It's not particularly clear that this is the right path yet because folks are building special-purpose neural net accelerators, and those may not have the same programming model and may make this whole HIP thing irrelevant for ML.

I'm also not totally convinced software developers are ready to take advantage of something like this; developers are barely taking advantage of multiple CPU cores, let alone the more limited GPGPU environment.

141133• 9 years ago

The problem isn't that a particular library is AMD or NVIDIA only in terms of computation, but NVIDIA or AMD only in terms of performance. GPU implementations are usually optimised for a specific architecture, which is then the "supported" architecture.

On occasion, such implementations do use vendor specific tools (such as CUDA), but there are a plethora of tools such as OpenCL, SyCL etc that provide portability - but not always performance portability, meaning that they will still be tuned to a specific architecture.

For performance portability, the LIFT project (http://www.lift-project.org/) provides a partial solution. Our approach relies on a high level model of computation (think or something like a functional, or pattern based programming language) coupled with a rewrite-based compiler that explores the space of OpenCL programs with which to implement a computation.

That lets us "optimise" a given implementation to a specific architecture, entirely automatically, in a way that many other low level approaches simply aren't able to, as they contain too many implementation (rather than computation) details.

marmaduke2• 9 years ago

Looks interesting conceptually but it would be good to refute the "sufficiently clever compiler" in anticipation. My beef with this sort of thing or Furthark or OpenACC is that they don't seem to understand complex data layouts required for real problems.

gnarbarian2• 9 years ago

I'm using GPU.js for a nbody gravity simulation in three.js. So far I'm liking GPU.js but it has it's limitations. only being able to return a single float from any function causes a lot of redundancy. For example, in order to get the 3d acceleration vector for one body I have to call the function once for each dimension, recomputing all of the temporary variables each pass. Then I have to make another pass for collision detection so it ends up being about 4n^2 vs just n^2

nonetheless it's still about an order of magnitude faster than the pure CPU implementation I have.

In the future they plan to add webGL 2.0 and OpenCL support which should improve the flexibility of the library.

http://thedagda.co:9000/?stars=true&bodyCount=1000

you can toggle CPU nbody computation with:

?CPU=true in the url. remove it for GPU computation.

you can toggle the number of planets with the bodyCount variable. default is 1000

if you have a beefy computer try bodyCount=4000

gamepad=true works if you have a xbox controller hooked up.

on gitHub:

https://github.com/ubernaut/spaceSim

Zelizz• 9 years ago

Why not calculate the unchanging intermediate results in separate functions so that you can pass them as arguments to the final function?

gnarbarian2• 9 years ago

Easier said than done. I can't get superkernels to work at all. I've tried.

leecarraher• 9 years ago

Sorting seems like a memory hard problem where the computationally optimal, merge sort solution, is heavily branched, two things gpus have never been terribly good at. Furthermore, the synchronized program counter per block of threads, presents a considerable road block to getting optimal thread occupancy specifically in the cuda architecture.

Sorting with GPUs: A Survey

Related Stories