10 ms·

Sorting with GPUs: A Survey

148 points by lainon 9y ago

frozenport 9y ago
The table at the end would benefit from a column indicating the availability of the source code.
exDM69 9y 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 9y 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 9y 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 https://en.wikipedia.org/wiki/B-tree
- ben-schaaf 9y 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 9y ago
    I was very surprised that depth sorting for real time rendering was not listed among the potential applications in the abstract.
  - pjc50 9y ago
    Isn't that usually done with the depth buffer?
    - heavenlyblue 9y ago
      Depth buffer has an issue of scales: one thing is 1 meter away and another one is 1 million meters away with another several thousand billion meters away. That makes it practically unusable for global positioning (especially for things that are both far away, but another one is just a little bit further). On the other hand sorting doesn't need to have a global axis - in the perfect case it just needs to compare two elements against each other.
    - exDM69 9y ago
      For non-transparent models, to a degree it gets done by the depth buffer. For transparent models, depth buffer is not helpful. But even when using the depth buffer, drawing in front-to-back order will drastically improve performance as fragment shaders don't have to run for occluded fragments that get depth culled.
    - panic 9y ago
      Depth buffers only work well for opaque objects, which cover each other completely. With partial coverage or blending, multiple objects could end up contributing to a pixel in an order-dependent way (e.g., if you're viewing an anti-aliased leaf edge under the surface of water through a window). The depth buffer, which only stores a single depth, doesn't solve this problem directly -- you can use it to render each transparent layer one-by-one ("depth peeling"), but this can be slow.
  - exDM69 9y 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).
- ACow_Adonis 9y 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_v 9y 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 9y 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 9y 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 http://www.forwardscattering.org/post/34
- angrygoat 9y 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 http://wiki.seg.org/wiki/CMP_sorting
- barrkel 9y 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.
- dragontamer 9y 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.
  - deleted 9y ago
    [deleted]
- taeric 9y 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 9y 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.
oelmekki 9y 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 9y ago
  Something like https://en.wikipedia.org/wiki/OpenCL https://en.wikipedia.org/wiki/OpenCL ?
  - oelmekki 9y 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.
    - autopoiesis 9y ago
      Also there's work towards a pure C++ abstraction layer for programming these accelerators, called SYCL [0]. It lets you define your compute kernels using normal C++ lambdas or functions, and then automatically infers the data dependencies to do the kernel execution. In particular, it provides an implementation of the C++ "Parallel STL" [1] (some intro slides at [2]), which in turn provides "execution policies" for various standard library functions, such as sorting. The aim is precisely the kind of thing you're talking about! [0] I found a nice intro at https://blog.tartanllama.xyz/sycl/ https://blog.tartanllama.xyz/sycl/ [1] http://en.cppreference.com/w/cpp/experimental/parallelism http://en.cppreference.com/w/cpp/experimental/parallelism [2] https://www.khronos.org/assets/uploads/developers/library/2016-supercomputing/SYCL_ParallelSTL-Ruyman-Reyes_Nov16.pdf https://www.khronos.org/assets/uploads/developers/library/20...
sudhasiri 9y ago
Industrial Graphics Cards and GPGPU Solutions | Industrial Graphics Cards https://www.plantautomation-technology.com/categories/networks-industrial-communication-software/aetina-corporation https://www.plantautomation-technology.com/categories/networ...
gnarbarian 9y 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 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 https://github.com/ubernaut/spaceSim
- Zelizz 9y ago
  Why not calculate the unchanging intermediate results in separate functions so that you can pass them as arguments to the final function?
  - gnarbarian 9y ago
    Easier said than done. I can't get superkernels to work at all. I've tried.
leecarraher 9y 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.

148 points by lainon 9y ago

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

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 9y 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 9y 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 https://en.wikipedia.org/wiki/B-tree
ben-schaaf 9y 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 9y ago
  I was very surprised that depth sorting for real time rendering was not listed among the potential applications in the abstract.
- pjc50 9y ago
  Isn't that usually done with the depth buffer?
  - heavenlyblue 9y ago
    Depth buffer has an issue of scales: one thing is 1 meter away and another one is 1 million meters away with another several thousand billion meters away. That makes it practically unusable for global positioning (especially for things that are both far away, but another one is just a little bit further). On the other hand sorting doesn't need to have a global axis - in the perfect case it just needs to compare two elements against each other.
  - exDM69 9y ago
    For non-transparent models, to a degree it gets done by the depth buffer. For transparent models, depth buffer is not helpful. But even when using the depth buffer, drawing in front-to-back order will drastically improve performance as fragment shaders don't have to run for occluded fragments that get depth culled.
  - panic 9y ago
    Depth buffers only work well for opaque objects, which cover each other completely. With partial coverage or blending, multiple objects could end up contributing to a pixel in an order-dependent way (e.g., if you're viewing an anti-aliased leaf edge under the surface of water through a window). The depth buffer, which only stores a single depth, doesn't solve this problem directly -- you can use it to render each transparent layer one-by-one ("depth peeling"), but this can be slow.
- exDM69 9y 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).
ACow_Adonis 9y 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_v 9y 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 9y 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 9y 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 http://www.forwardscattering.org/post/34
angrygoat 9y 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 http://wiki.seg.org/wiki/CMP_sorting
barrkel 9y 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.
dragontamer 9y 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.
- deleted 9y ago
  [deleted]
taeric 9y 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 9y 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.

oelmekki 9y 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 9y ago
Something like https://en.wikipedia.org/wiki/OpenCL https://en.wikipedia.org/wiki/OpenCL ?
- oelmekki 9y 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.
  - autopoiesis 9y ago
    Also there's work towards a pure C++ abstraction layer for programming these accelerators, called SYCL [0]. It lets you define your compute kernels using normal C++ lambdas or functions, and then automatically infers the data dependencies to do the kernel execution. In particular, it provides an implementation of the C++ "Parallel STL" [1] (some intro slides at [2]), which in turn provides "execution policies" for various standard library functions, such as sorting. The aim is precisely the kind of thing you're talking about! [0] I found a nice intro at https://blog.tartanllama.xyz/sycl/ https://blog.tartanllama.xyz/sycl/ [1] http://en.cppreference.com/w/cpp/experimental/parallelism http://en.cppreference.com/w/cpp/experimental/parallelism [2] https://www.khronos.org/assets/uploads/developers/library/2016-supercomputing/SYCL_ParallelSTL-Ruyman-Reyes_Nov16.pdf https://www.khronos.org/assets/uploads/developers/library/20...

sudhasiri 9y ago

Industrial Graphics Cards and GPGPU Solutions | Industrial Graphics Cards https://www.plantautomation-technology.com/categories/networks-industrial-communication-software/aetina-corporation https://www.plantautomation-technology.com/categories/networ...

gnarbarian 9y 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 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 https://github.com/ubernaut/spaceSim

Zelizz 9y ago
Why not calculate the unchanging intermediate results in separate functions so that you can pass them as arguments to the final function?
- gnarbarian 9y ago
  Easier said than done. I can't get superkernels to work at all. I've tried.

leecarraher 9y 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.