我需要計算CUDA內核中大小爲p的數組(在我的情況下,p很小,例如p = 10)的中值。我使用O(p^2)算法,因爲它的簡單性,但是以時間性能爲代價。CUDA內核中的中值選擇
是否有一個「函數」來有效地找到我可以在CUDA內核中調用的中值?
我知道我可以實現一個選擇算法,但我正在尋找一個函數和/或測試代碼。
謝謝!
我需要計算CUDA內核中大小爲p的數組(在我的情況下,p很小,例如p = 10)的中值。我使用O(p^2)算法,因爲它的簡單性,但是以時間性能爲代價。CUDA內核中的中值選擇
是否有一個「函數」來有效地找到我可以在CUDA內核中調用的中值?
我知道我可以實現一個選擇算法,但我正在尋找一個函數和/或測試代碼。
謝謝!
即使在單線程中,也可以對數組進行排序並在O(p * log(p))中選擇中間的值,這會使O(p^2)看起來過度。如果您有p個線程可供您使用,也可以按照O(log(p))的速度對陣列進行排序,儘管這可能不是小型p的最快解決方案。見上面的答案在這裏:
Which parallel sorting algorithm has the best average case performance?
如果你只是想要中位數的話,分揀是過度的。 – ArchaeaSoftware
同意。這裏有更快的排序:http://en.wikipedia.org/wiki/Selection_algorithm – Michael
下面是一些提示:
還有很多其他的優化可以做。請確保您閱讀了CUDA documents,尤其是Programming Guide和Best Practices Guide。 當你真的想要高性能的槍支時,不要忘記仔細看看CUDA分析器,比如Visual Profiler。
考慮到'p'的小值,您是否考慮過使用採用最小排序網絡的模板化函數? – njuffa
「p」的小值可能表示您應該編寫自己的代碼,如其他人已經建議的那樣。如果您想查看一些基本示例代碼,請不要忘記查看[cuda samples](http://docs.nvidia.com/cuda/cuda-samples/index.html)中的各種排序代碼,以及[CUB](http://nvlabs.github.io/cub/)。 –
嘗試實施http://en.wikipedia.org/wiki/Median_of_medians –