CUDA内核中的中值选择 [英] Median selection in CUDA kernel

查看:176
本文介绍了CUDA内核中的中值选择的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我需要计算CUDA内核中大小为p的数组的中值(在我的例子中,p很小,例如p = 10)。我使用O(p ^ 2)算法的简单性,但是以时间性能为代价。

I need to compute the median of an array of size p inside a CUDA kernel (in my case, p is small e.g. p = 10). I am using an O(p^2) algorithm for its simplicity, but at the cost of time performance.

有一个函数我可以调用一个CUDA内核?

Is there a "function" to find the median efficiently that I can call inside a CUDA kernel?

我知道我可以实现一个选择算法,但我正在寻找一个函数和/或测试代码。

I know I could implement a selection algorithm, but I'm looking for a function and/or tested code.

谢谢!

推荐答案

即使在单线程中,也可以对数组进行排序, p * log(p)),这使得O(p ^ 2)看起来过多。如果你有你的p线程,也可以像O(log(p))一样快的排序数组,虽然这可能不是小p的最快的解决方案。请参阅上面的解答:

Even in a single thread one can sort the array and pick the value in the middle in O(p*log(p)), which makes O(p^2) look excessive. If you have p threads at your disposal it's also possible to sort the array as fast as O(log(p)), although that may not be the fastest solution for small p. See the top answer here:

哪种并行排序算法具有最佳的平均案例性能?

这篇关于CUDA内核中的中值选择的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆