What I am trying to achieve is multiple k-selections (different but small datasets) running in parallel on a GPU. Basically, my aim is to select kth smallest element from an array of floats such that each work-group processes one array using CUDA and efficiently utilizes thread-level parallelism.

The number of arrays to be sorted as such run into thousands. I am not sure if I have seen such scaling done anywhere before. I have seen algorithms like the Duane Merrill Radix sort (which is actually sorting, not selection) or the randomized selection algorithm by Monroe et al. or k-selection algorithms by Alabi et al. However, ALL of them have been built for choosing the kth element from an extremely large array/vector and not multiple lists in parallel as I want.

The number of items in an array and k are pre-determined (n<10000). Could you suggest me any algorithm of k-selection of multiple short lists in parallel?

  • $\begingroup$ Sorting seems overkill... When doing things on sequential machines there are much better solutions than sorting, I would expect the same situation in parallel models? $\endgroup$ – Jeremy Jul 10 '13 at 15:19
  • $\begingroup$ parallel sorting? $\endgroup$ – vzn Jul 10 '13 at 15:53
  • $\begingroup$ Yes, and that is why I want a k-selection algorithm. Sorting is really not necessary. But, what am unsure about is about a serial k-selection algorithm which minimizes the amount of memory, has no recursion and least array swaps (if possible, none). I could then run this 'serial' algorithm in parallel. I know its too much to ask but I have these constraints for running it fast on a GPU. $\endgroup$ – Ishbir Jul 11 '13 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.