# Sort on GPU Need some help to use sorts... **URL:** \ **Category:** CUDA Programming and Performance\ **Created:** [April 24, 2008, 7:35pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486 "2008-04-24T19:35:15Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![D1mmu](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@D1mmu](https://forums.developer.nvidia.com/u/D1mmu)\ **Post date:** [April 24, 2008, 7:35pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/1 "2008-04-24T19:35:15Z")
Hi, I’m a student from University of Liège. I’m trying to use CUDA to speed up the “decision tree” algorithm (the current version is only sequential). This algorithm is mostly used in a lot of bio-informatic applications. At the moment, I’m trying to find a sort algorithm on GPU that would be faster than a “Quicksort on CPU”. In memory, I have to sort a very large float vector. I have seen some interessant algorithm, like : - bitonic sort - abi sort - radix sort - tera sort I read in the forum that the “radix sort” given with the SDK is very efficient (in the project named “particles”). But I don’t understand how to use it… ```auto //////////////////////////////////////////////////////////////////////////////// //! Perform a radix sort //! Sorting performed in place on passed arrays. //! //! @param pData0       input and output array - data will be sorted //! @param pData1       additional array to allow ping pong computation //! @param elements     number of elements to sort //////////////////////////////////////////////////////////////////////////////// void RadixSort(KeyValuePair *pData0, KeyValuePair *pData1, uint elements, uint bits); ``` If I have a float Vector “float\* vector”, how can I send to RadixSort() a “KeyValuePair \*pData0” ? Would you know any better algorithms to sort large float vectors ? The bitonic sort seems to be working fine with a little vector (and with size%2 == 0) but if I really want to use it, I need to find an example of CUDA implementation of the ABisort… Would you know where I could find it ? Thank you for your help, and keep in mind that i’m a newbie :P! ---
**Author:** ![DenisR](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@DenisR](https://forums.developer.nvidia.com/u/DenisR)\ **Post date:** [April 25, 2008, 4:47am UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/2 "2008-04-25T04:47:04Z")
What I understood is that the radixsort is sorting a data (key) based on a value (value) So for you you have no key, just a value. I am not sure if it is easy to adjust the radix-sort algorithm to get rid of the data. ---
**Author:** ![D1mmu](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@D1mmu](https://forums.developer.nvidia.com/u/D1mmu)\ **Post date:** [April 25, 2008, 10:22am UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/3 "2008-04-25T10:22:56Z")
> [@](#): > > What I understood is that the radixsort is sorting a data (key) based on a value (value) > > So for you you have no key, just a value. I am not sure if it is easy to adjust the radix-sort algorithm to get rid of the data. > > [snapback]368118[/snapback] Thank you for your useful informations DenisR :)! I don’t understand how the keys are used by the radix sort… I could set a unique key to each float by given the position of each float in the vector. But I’ve not been surprised to see this solution not working… How could I set these keys to try the efficiency of this algorithm in my application? If radix sort is not efficient (or not usable), I have to reimplement the Bitonic sort to make it compatible for vector size != 2^n and next implement the (complex) ABisort to use bitonic sort with more than 512 elements. Ok, let’s work D1mmu! [External Media](http://hqnveipbwb20/public/style_emoticons/<#EMO_DIR#>/fear.gif "Media hosted on another site. Click to open in a new tab.") My last question is : would you know any “easy to use” CUDA sorts function compatible with a large number of element? ---
**Author:** ![DenisR](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@DenisR](https://forums.developer.nvidia.com/u/DenisR)\ **Post date:** [April 25, 2008, 10:32am UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/4 "2008-04-25T10:32:39Z")
CUDPP is a library with scan, reduction and I believe sorting primitives. [url=“[http://forums.nvidia.com/index.php?showtopic=65314](http://forums.nvidia.com/index.php?showtopic=65314)”][The Official NVIDIA Forums | NVIDIA](http://forums.nvidia.com/index.php?showtopic=65314%5B/url%5D) ---
**Author:** ![D1mmu](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@D1mmu](https://forums.developer.nvidia.com/u/D1mmu)\ **Post date:** [April 25, 2008, 10:49am UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/5 "2008-04-25T10:49:13Z")
Thank you! So I’m going to learn how to use this library! I will post here my solution if it works fine. ---
**Author:** ![Mu-Chi\_Sung](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Mu-Chi\_Sung](https://forums.developer.nvidia.com/u/Mu-Chi_Sung)\ **Post date:** [April 26, 2008, 5:49pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/6 "2008-04-26T17:49:21Z")
> [@](#): > > Thank you! So I’m going to learn how to use this library! I will post here my solution if it works fine. > > [snapback]368208[/snapback] The CUDPP lastest 1.0 alpha realse does not support key-value pair sorting, unless you read the kernel and hack it in your way. But an interesting point is that: When I tried to compare the performance of the original radix sort in particle example with the new CUDPP sort primitive, I thought CUDPP should perform better than radix sort in SDK example because it’s a newer implementation and it only reads the key while the radix sort example reads both key and value…,but finally I found that CUDPP is actually _slower_ than the old version. The performance of sort primitive in CUDPP seems to be slower than previous version…Well, maybe the reason is…it’s the “alpha version”… \/crying.gif’ class=‘bbc\_emoticon’ alt=‘:’(’ /\> ---
**Author:** ![Linh\_Ha](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Linh\_Ha](https://forums.developer.nvidia.com/u/Linh_Ha)\ **Post date:** [April 26, 2008, 7:29pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/7 "2008-04-26T19:29:16Z")
> [@](#): > > When I tried to compare the performance of the original radix sort in particle example with the new CUDPP sort primitive, I thought CUDPP should perform better than radix sort in SDK example because it’s a newer implementation and it only reads the key while the radix sort example reads both key and value…,but finally I found that CUDPP is actually _slower_ than the old version. The performance of sort primitive in CUDPP seems to be slower than previous version… > > [snapback]368833[/snapback] Any one can sheet a light on why it is slower. CUDPP is highly optimized with CUDA prefix sum version, so why it is slower, this does not make sense to me ---
**Author:** ![D1mmu](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@D1mmu](https://forums.developer.nvidia.com/u/D1mmu)\ **Post date:** [April 29, 2008, 11:29am UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/8 "2008-04-29T11:29:31Z")
> [@](#): > > The CUDPP lastest 1.0 alpha realse does not support key-value pair sorting, unless you read the kernel and hack it in your way. But an interesting point is that: > > When I tried to compare the performance of the original radix sort in particle example with the new CUDPP sort primitive, I thought CUDPP should perform better than radix sort in SDK example because it’s a newer implementation and it only reads the key while the radix sort example reads both key and value…,but finally I found that CUDPP is actually _slower_ than the old version. The performance of sort primitive in CUDPP seems to be slower than previous version…Well, maybe the reason is…it’s the “alpha version”… \/crying.gif’ class=‘bbc\_emoticon’ alt=‘:’(’ /\> > > [snapback]368833[/snapback] I tryied CUDPP and its sort function. It seems to be working fine for positive int and floats. The program totally crashes when I put negative values… In the documentation, I read : > [@](#): > > Currently, this only sorts unsigned ints (positive floats ought to work as well but are untested). > > Todo: > > Provide more flexible sorts. But does someone now if there is a way to use it with unsigned values? ---
**Author:** ![DenisR](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@DenisR](https://forums.developer.nvidia.com/u/DenisR)\ **Post date:** [April 29, 2008, 1:07pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/9 "2008-04-29T13:07:20Z")
option 1 : take the code and make it work with negative values option 2 : search for the minimum element of the array (reduction),substract that from the entire array, perform the sort, add the minimum element to the entire array. ---
**Author:** ![D1mmu](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@D1mmu](https://forums.developer.nvidia.com/u/D1mmu)\ **Post date:** [April 29, 2008, 1:34pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/10 "2008-04-29T13:34:38Z")
> [@](#): > > option 1 : take the code and make it work with negative values > > option 2 : search for the minimum element of the array (reduction),substract that from the entire array, perform the sort, add the minimum element to the entire array. > > [snapback]370214[/snapback] At the moment, I’m testing my implementation with “the option 2”, but my DB is large… I have to do some test… For information, I did a little benchmark beetwen the Qsort in CPU and RadixSort (from CUDPP) in GPU, I get the following results ( element[i] = (float) rand()%nbElements; ): (CPU : E6750 and GeForce 8800 gts 640) For 10000 elements → CPU : 3 ms and GPU : 0 ms For 100000 elements → CPU : 41 ms and GPU : 3 m For 1000000 elements → CPU : 391 ms and GPU : 36 ms For 10000000 elements → CPU : 4166 ms and GPU : 454 ms ---
**Author:** ![Ku-Sai\_Sung](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Ku-Sai\_Sung](https://forums.developer.nvidia.com/u/Ku-Sai_Sung)\ **Post date:** [April 29, 2008, 4:28pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/11 "2008-04-29T16:28:10Z")
The best CUDA parallel sort algorithm I know is the one implemented by Alan Kaatz. It performs sort in a set of 16000000 elements (16 million elements) in just 311.35 (ms). This is the link for his code: [url=“[Course Websites | The Grainger College of Engineering | UIUC](http://courses.ece.uiuc.edu/ece498/al1/mps/MP5-TopWinners/kaatz/MP5-parallel_sort.zip)”][http://courses.ece.uiuc.edu/ece498/al1/mps...rallel\_sort.zip[/url]](http://courses.ece.uiuc.edu/ece498/al1/mps...rallel_sort.zip%5B/url%5D) Maybe you should ask for his permission if you want to use it. For 1 million elements, it took about 30 ms. (tested by me) Good luck! :) ---
**Author:** ![D1mmu](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@D1mmu](https://forums.developer.nvidia.com/u/D1mmu)\ **Post date:** [April 30, 2008, 6:36pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/12 "2008-04-30T18:36:10Z")
> [@](#): > > The best CUDA parallel sort algorithm I know is the one implemented by Alan Kaatz. > > It performs sort in a set of 16000000 elements (16 million elements) in just 311.35 (ms). > > This is the link for his code: > > http://courses.ece.uiuc.edu/ece498/al1/mps…rallel\_sort.zip > > Maybe you should ask for his permission if you want to use it. > > For 1 million elements, it took about 30 ms. (tested by me) > > Good luck! :) > > [snapback]370273[/snapback] Thank you ! I tried this sort and it is very fast, but in ma case, I have to sort my matrix by attributes… I have the following float matrix (in fact, it’s juste a large malloc) : Record 1 : Att11 Att12 Att13 … Y1 (Y is the conclusion about the other attributes of the record) Record 2 : Att21 Att22 Att23 … Y2 Record 3 : Att31 Att32 Att33 … Y3 ``` ... ``` In my algorithm, I have to sort each records by a defined Attribute. So I first tryed to transpose my matrix, to have one attribute by line. And then I would use the efficient function you showed me to sort only line by line… Att1 : Rec11 Rec12 … Rec1n Att2 : Rec21 Rec22 … Rec2n Att3 : … … Y : Y1 Y2 … Yn But I forgot that I can’t tranpose my matrix… because after a sort, my Y values would not be with her concerned Rec… My solution would be to have a sort function as portable as qsort(), in wich I could give the size of my record (sizeof(float) \* nb\_attributes) and a function where I could define the specifics comparisons to do… So I don’t see any other solutions… I must try to implement the ABIsort for my use case. :unsure: Thank you for your help ! ---
**Author:** ![D1mmu](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@D1mmu](https://forums.developer.nvidia.com/u/D1mmu)\ **Post date:** [May 1, 2008, 5:28pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/13 "2008-05-01T17:28:06Z")
I’m trying to implement my own sort (king of bitonic sort). At the moment, I have (512 elem) sub-matrixes sorted and I would like to merge them, would you know a parrallel merge function that takes two matrixes and fills a third one? Ma : [1 2 4 5] Mb : [2 5 6 7] Mresult : [1 2 2 4 5 5 6 7] ---
**Author:** ![humorstar](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@humorstar](https://forums.developer.nvidia.com/u/humorstar)\ **Post date:** [June 1, 2008, 8:30pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/14 "2008-06-01T20:30:00Z")
Dear all, I am trying to do radixsort with the following KeyValuePair: typedef struct KeyValuePair { float key; float value; } or more precisely: typedef struct KeyValuePair { float key; int value; } or even more complex: typedef struct KeyValuePair { float key; int \*value; } I looked at the options as suggested in this thread of post: 1. radixsort in the ‘particles’ example’s KeyValuePair is: typedef struct KeyValuePair { uint key; uint value; } radixsort is only for integers. I guess it won’t work with my case. Is there any other ways? I don’t quite understand how radixsort works in this example. Why does it look so complex? Why does the element needs to round up to multiples of 3072? 1. cudpp has a RADIXSORT. But it does not look like it supports KeyValuePair sorting. It will sort an array with a value. I only need to sort less than 10000 such elements. Will it be worthy to use GPU for this task? Thank you, ---
**Author:** ![Linh\_Ha](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Linh\_Ha](https://forums.developer.nvidia.com/u/Linh_Ha)\ **Post date:** [June 2, 2008, 2:49am UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/15 "2008-06-02T02:49:46Z")
> [@](#): > > radixsort is only for integers. I guess it won’t work with my case. Is there any other ways? radix can be used for arbitrary key length. You should understand the mechanism CPU radix first before making your own GPU version, it is not too hard to make the change, but it is hard to make it fast. Good luck > [@](#): > > I don’t quite understand how radixsort works in this example. Why does it look so complex? Why does the element needs to round up to multiples of 3072? There’s explanation inside the source code. There’s also related chapter in GPU Gems III > [@](#): > > I only need to sort less than 10000 such elements. Will it be worthy to use GPU for this task? > > [snapback]386897[/snapback] In that case the CPU sort will be tens time faster than GPUs. Normally, GPU sort is only faster with more than 1M records ---
**Author:** ![PINS](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@PINS](https://forums.developer.nvidia.com/u/PINS)\ **Post date:** [June 19, 2008, 10:23pm UTC](https://forums.developer.nvidia.com/t/sort-on-gpu-need-some-help-to-use-sorts/3486/16 "2008-06-19T22:23:40Z")
Hey everyone, I’ve been trying to use the sort algorithm from the particles example inside my own project. After some modifications to work with positive floating point data, I’m not getting good performance results. To give you an idea, here are some numbers: number of keyvalue pairs \_\_\_\_ time (ms) 10.000 \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ 1.65 100.000 \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ 6.94 1.000.000 \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ 95.20 As far as I’ve checked, the results are correctly sorted. Anyone can tell me if I just messed up the original code? Or is this the performance I should expect anyway? Btw, I’m testing on a 9800GX2, but i get similar results on a 8800GTX.