如何使用CUDA從M個元素中獲取N個最大元素，其中N << M？

我只是想知道是否有越來越Ñ最大元件出M個元件，其中N是小於M小得多的任何有效的方式（例如，N = 10，M = 1000）使用GPU。如何使用CUDA從M個元素中獲取N個最大元素，其中N << M？

的問題是 - 由於大尺寸的輸入數據，我真的不希望將數據從GPU轉移到CPU，然後拿回來。然而，由於線程分歧以及我們不關心的排序元素浪費的時間（在上述情況下，DC元素爲11〜1000），精確排序似乎並不成功。

我猜一些最大堆是這些問題的典型解決方案。 – halfelf

@halfelf：我不會推薦在CUDA上做最大的二進制堆，如果這就是你所指的？除非你在並行機器上有更具體的方式來做這件事？ – CygnusX1

你舉一個例子N = 10，M = 1000，但你談論的是大量的輸入數據。你對N和M有什麼現實價值？根據N我建議要麼適應減少算法或適應排序算法。即使對於小M，如果它是更大的CUDA算法的一部分，也可以在設備上執行。 – CygnusX1

如果N是足夠小的N個最大的值可以保存在共享內存，這將允許快速實現，只有通過你的全局內存M個元素的數組讀取一次，然後立即寫出這N個最大值。如果N也不超過每個塊的最大線程數，則實現變得更簡單。

相反串行編程，我不會用堆（或其它更復雜的數據結構），但只是一個排序後的數組。 SM上有很多並行硬件，當遍歷一個堆時將不會使用它。整個線程塊可用於移動共享內存陣列中小於新傳入值的元素。

如果N < = 32，則使用warp shuffle functions可以使用整潔的解決方案來保持寄存器中N個最大數字的排序列表。

2016-08-11 10:13:37 tera

您能否詳細說明採用哪種算法？根據你的描述，你提到在第一段中共享內存中保留N個最大值，並使用寄存器來保留第三段中的N個最大值。您帖子中的第二段建議不要使用堆數據結構。我的問題是你用什麼算法從M個元素中獲取N個最重要的元素。謝謝 – LongY

回答