Abstract
在計算機科學的研究領域，排序法是一直不斷被拿出來討論的問題之一；由於排序法的基礎性和重要性，使得它現在也廣泛被移植到新興的多核心圖形處理器(GPUs)上。在CUDPP函式庫裡的 GPU radix sort 是一種非比較式的(non-comparison-based)排序法，它是目前在GPU上最快的排序法；而 GPU sample sort 是GPU上最快的比較式(comparison-based)排序。這兩個排序法，分別是兩種不同排序分類裡的領先技術(state of the art)；不過它們都需要使用到額外的空間來重組資料，或是使用不可分割運算(atomic operation)來加速。GPU通常被用來處理非常大量的資料，因此，記憶空間的運用顯得特別重要；另外，排序法在沒有不可分割運算(atomic operation)支援的GPU上執行，可能導致效能下降，或甚至無法正常執行。在這個論文裡，我們提出一個在 NVIDIA GPU 上實現shell排序的方法。這個方法不用額外的記憶空間，也不需要不可分割運算的支援。我們的實驗結果也顯示，GPU shellsort 平均上有 GPU quicksort 的兩倍快，與將近快過三倍 Thrust mergesort 。在小於三千兩百萬筆資料時，效能大概和目前比較式排序的中最快的 GPU sample sort 相當。我們所提出在GPU上的 shell 排序法 ，在各種資料分佈上的表現也都非常穩健，沒有一種標準測試用的資料分佈會使這個方法的效能變的非常差。基本上這個方法也適用其它的多核心平台。