6
$\begingroup$

Suppose we have a function on GPU which calculates elements of array from which we need to select top K elements. The number of elements can be quite big so we can't store them in memory and our algorithm should be online. Another requirement for algorithm is its good parallelization so it could be effectively run on GPU.

Is there any classic approach for the problem? I've thought only of building heap/balanced tree with $k$ elements and inserting new elements into it if new elements is better than existing and popping smaller element. It gives O($n$ log$k$) but it fails with parallelisation because requires synchronization between GPU threads on modifying tree.

Improve this question
$\endgroup$
2
  • $\begingroup$ did you end up implementing this kind of an algorithm on a GPU? If so, I would be very interested, and even though it's not perfectly on topic, you could add a link... I need something like this myself (although being on-line is not strictly necessary) for my DBMS-related work (shameless plug). $\endgroup$
    – einpoklum
    Aug 12, 2016 at 20:08
  • $\begingroup$ Also, note that this is a very different problem when k << n and when k is some constant fraction of n. $\endgroup$
    – einpoklum
    Aug 12, 2016 at 20:18

1 Answer 1

Reset to default
3
$\begingroup$

Here is one naive solution:
Let the number of parallel processes be $m$. Then, keep a separate buffer/heap/balanced tree for each of the $m$ processes. Divide the range of input into $m$ sections. Whenever you read a number, insert it into the appropriate process' heap. This way, each process only works on its own heap/tree. When you are done with the input, and want to output the top $k$ elements, do a partial mergesort to find the overall top-k.

This will require $O(km)$ space and $O(n\log k + km\log k)$ time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Good idea but I hoped that there is a bit more complex algorithm with less overhead. $\endgroup$
    – flashnik
    Jan 2, 2013 at 15:01
  • $\begingroup$ @flashnik Yep. This is a pretty trivial algorithm. $\endgroup$
    – Paresh
    Jan 2, 2013 at 15:04
  • 1
    $\begingroup$ @flashnik If you can manage with approximate results, there could be faster methods. I have not gone through them, but you could look up some of the results by searching for "parallel selection algorithms" $\endgroup$
    – Paresh
    Jan 2, 2013 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.