Bitonic Sorting Network vs Thrust :: sort_by_key

Question

我實現了一個使用排序的算法。我嘗試了大約0.4s的Thrust :: sort_by_key來對10^7元素的數組進行排序。

我認爲雙向排序網絡應該比Thrust :: sort_by_key快。然而，雙音排序需要大約2.5s來對上述相同的陣列進行排序。我使用了SDK提供的雙向排序網絡。我只是稍微修改了原始的雙音排序。

你能告訴我爲什麼嗎？或給我一些建議？

謝謝，

奕

八月，15，2011

Answer 1

簡短的回答是由CUDA SDK提供的雙調排序例子主要意在教學。它不像Thrust的排序實現那樣優化，它基於Merrill提供的非常高效的基數排序。

這兩種算法的asymptotic performance也不同。雙音排序網絡具有O(n lg^2 n)的複雜性，而Thrust採用的基數排序具有更復雜的O(#bits n)，其中#bits表示表示輸入數據所需的比特數。換句話說，基數排序需要的漸進式全局內存讀取和寫入比雙向排序要少。

您可能會發現，對於較小的工作負載，雙音排序性能會更好。