CUDA內核中的中值選擇

我需要計算CUDA內核中大小爲p的數組（在我的情況下，p很小，例如p = 10）的中值。我使用O（p^2）算法，因爲它的簡單性，但是以時間性能爲代價。CUDA內核中的中值選擇

是否有一個「函數」來有效地找到我可以在CUDA內核中調用的中值？

我知道我可以實現一個選擇算法，但我正在尋找一個函數和/或測試代碼。

謝謝！

2013-08-30 rodms

考慮到'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 –

即使在單線程中，也可以對數組進行排序並在O（p * log（p））中選擇中間的值，這會使O（p^2）看起來過度。如果您有p個線程可供您使用，也可以按照O（log（p））的速度對陣列進行排序，儘管這可能不是小型p的最快解決方案。見上面的答案在這裏：

Which parallel sorting algorithm has the best average case performance?

來源

2013-08-30 18:45:03 Michael

如果你只是想要中位數的話，分揀是過度的。 – ArchaeaSoftware

同意。這裏有更快的排序：http://en.wikipedia.org/wiki/Selection_algorithm – Michael

下面是一些提示：

使用更好的選擇算法：QuickSelect是快速排序的選擇的一個速度更快的版本數組中的第k個元素。對於編譯時常量掩碼大小，由於高TLP和O（log^2 n）關鍵路徑，sorting networks甚至更快。如果您只有8位值，則可以使用基於直方圖的方法。 This paper描述了一個實現，每個像素需要不變的時間，而不受掩碼大小的影響，這對於非常大的掩碼大小而言非常快速。您可以通過使用最小啓動策略（只需運行儘可能多的線程以保持所有SM處於最大容量），平鋪圖像，並讓同一塊的線程在每個內核直方圖上協作來並行化它。

Sort in registers.對於較小的遮罩尺寸，您可以將整個陣列保留在寄存器中，使用sorting network的中值選擇更快。對於較大的面罩尺寸，您可以使用shared memory。

首先將塊使用的所有像素複製到shared memory，然後複製到也位於共享內存中的線程局部緩衝區。

如果您只有幾個需要非常快的屏蔽（例如3x3和5x5），use templates才能使它們編譯時間常量。這可以加速很多事情，因爲編譯器可以展開循環並重新排序更多指令，可能會改進負載配料和其他好吃的東西，從而導致大幅度的加速。

確保您的閱讀是coalesced and aligned。

還有很多其他的優化可以做。請確保您閱讀了CUDA documents，尤其是Programming Guide和Best Practices Guide。當你真的想要高性能的槍支時，不要忘記仔細看看CUDA分析器，比如Visual Profiler。

來源

2013-10-29 04:48:41 Domi

CUDA內核中的中值選擇

回答

相關問題