快速破解排序：我是否正確地執行此操作？

我正在研究不同的排序算法，並嘗試考慮如何將它們移植到GPU時，如果我有這種排序的想法而沒有實際排序。這是我的內核的樣子：快速破解排序：我是否正確地執行此操作？

__global__ void noSort(int *inarr, char *outarr, int size) 
{ 
    int idx = threadIdx.x + blockIdx.x * blockDim.x; 
    if (idx < size) 
      outarr[inarr[idx]] = 1; 
}

然後在主機側，我只是打印數組索引，其中outarr[i] == 1。現在有效地，上面的代碼可以用來對整數列表進行排序，並且這可能比實際排序的算法更快。

這合法嗎？

來源

2011-07-29 Sayan

你的例子本質上是一個專門的counting sort用於具有唯一鍵（即沒有重複）的輸入。爲了使代碼正確計數，您可以用atomicAdd(inarr + idx, 1)替換賦值outarr[inarr[idx]] = 1，這樣重複的鍵就會被計數。但是，除了原子操作相當昂貴的事實之外，您仍然有問題，即該方法的複雜性與輸入中的最大值成正比。幸運的是，radix sort解決了這兩個問題。

基數排序可以被認爲是計數排序的一般化，該排序只查看輸入的B位。由於B位的整數只能取[0,2^B)範圍內的值，所以我們可以避免查看全部值。

現在，在您開始實施CUDA基數排序之前，我應該警告您已經有studied extensively和extremely fast實現可用。實際上，Thrust庫會盡可能自動應用基數排序。

來源

2011-07-30 03:09:54 wnbell

謝謝你指出一些很好的資源。由於我計劃編寫一個程序來使用多個GPU進行排序，所以有點離題了。有使用多個GPU對大量數字進行排序的實現嗎？我認爲NVidia網站的分類Networks代碼示例在單個GPU上工作。或者說，讓我這樣說...在實際世界中它可能有多大用處？ – Sayan

我不知道有任何多GPU排序代碼，但它絕對有可能構建一個。最簡單的做法是在每個設備上使用現有的（單GPU）排序並將結果合併在一起，可能使用P2P副本來加速GPU間的通信。 – wnbell

我明白你在做什麼，但我認爲它只在特殊情況下才有用。例如，如果inarr的元素具有非常大的價值呢？這就需要越來越多的元素來處理它。重複數字呢？

假設你開始使用一個內部具有唯一的小值的數組，這是一種有趣的排序方式。一般來說，在我看來，它會使用大量的內存來完成一些已經通過並行合併排序等算法處理好的內存。讀取輸出數組也是一個非常昂貴的過程（特別是如果輸入數組中有任何大數值），因爲您最終將得到一個非常稀疏的數組。

來源

2011-07-29 19:42:36

我明白你的觀點。 'outarr'必須是'MAXof（inarr）* char bytes'的最小值，這是浪費的，因爲'inarr'只能有'{3,1,42300}'。雖然我認爲追蹤重複條目的數量並不困難。正如你所說，我認爲對於合理的數據大小這種方法可能會奏效。 – Sayan

但是，如果使用鏈表而不是'outarr'，空間問題可以解決IMO。只是想想如果它可以做得更好。 – Sayan

快速破解排序：我是否正確地執行此操作？

回答

相關問題