<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-07-10T15:19:57.017Z
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?
J.y B.y
CC BY-SA 3.0
2013-07-10T15:53:51.830Z
parallel sorting?
vzn
CC BY-SA 3.0
2013-07-11T11:05:44.633Z
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.
Ishbir
<dc.parallel-comp>
Multiple k-selection using GPU
Ishbir
# Multiple k-selection using GPU

(Asked by: username_0 on 2013-07-10)

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?

**Tags:** dc.parallel-comp
> **Comments:**
> **username_1**: 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?  
> **username_2**: parallel sorting?  
> **username_0**: 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.  

---

## 0 answers

