基于CUDA的奇偶排序并行算法

摘 要：本文介紹了基于CUDA的奇偶排序并行算法，并給出GPU代碼，分析了用CPU與GPU代碼實現的優缺點，可以讓我們對并行計算技術有更深刻的學習和了解。

關鍵詞：CUDA；奇偶排序；GPU；并行計算

DOI：10.16640/j.cnki.37-1222/t.2015.23.238

1 引言

排序是指將一個無序的元素序列，通過一定的方式排列成以關鍵字有序的序列。目前排序算法有很多，有的能夠在GPU上實現，比如樣本排序，有的則不能很好的在GPU上實現，比如堆排序。奇偶排序就是一種非常適合在GPU上實現的排序方法。它是由冒泡算法改進而來，奇偶排序分為奇下標排序和偶下標排序，在一每輪排序過程中，各元素的操作與其他元素是互不影響的。

2 相關概念

并行計算（Parallel Computing），是同時使用多種計算資源進行計算問題的方法，能夠有效提高計算效率和計算機的處理能力。并行計算分為時間上的并行和空間上的并行兩種。時間上的并行類似于生產流水線，在同一時間啟動多個操作從而提高計算速度。空間上的并行則是指利用多個處理器同時進行計算[1]。

CUDA是NVIDIA公司最新推出的產品，通過CUDA平臺可以充分利用并行計算的優勢來處理計算問題[2]。CUDA的GPU端語言采用C，所以對于開發者來說，使用起來更加簡單。CUDA可廣泛的應用在圖形學、生物、科學計算、地質、物理模擬等需要大規模并行計算的領域。

3 奇偶排序

我們都知道冒泡排序是首先選擇數組中第一個索引中的元素，然后將該元素與它后面得元素進行逐一比較，如果它比后面的元素小，則兩個元素進行交換，否則不再進行比較。以此類推，選擇數組中各元素分別與后面元素進行比較，最終得到一個從大到小的有序序列。

奇偶排序在冒泡算法的基礎上加以改進，每次在數組中進行兩趟掃描。第一趟掃描選擇所有的奇數項對a[i]和a[i+1]，（i=1， 3， 5……）。如果a[i]大于a[i+1]，則兩個元素位置交換。第二趟對所有的偶數項進行掃描，此時（i=2， 4，6……）。重復以上操作直到數組全部有序。奇偶排序和冒泡排序的時間復雜度都是O（N^2）[3]。

4 代碼實現

CPU版的奇偶排序代碼非常簡單，我們在此不在給出，奇偶排序算法的GPU實現，代碼如下：

5 總結

通過上面GPU代碼我們可以看到，處理那些幾乎有序的數組，奇偶排序十分實用。當數組中元素是倒敘排列時是最壞情況。由于基于CUDA的GPU代碼需要先將數據拷貝到設備上進行計算，然后再拷貝回主機輸出，當數組中數據比較少時，會比CPU代碼消耗更多的時間，但是，當數據量比較大時，在多線程的并行計算方式會大大提高運算效率。

參考文獻：

[1] Adams J et al， The Fortran 90 Handbook.McGraw-Hill，1992.

[2]Allan S J， Oldehoeft R . HEP SISAL： Parallel Functional Programming. Kowalik（Ed）. Parallel MIMD Computation： HEP Supercomputers and Applications. MIT Press，1985.

[3]陳國良.并行計算：結構、算法、編程[B].北京：高等教育出版社，2003.

作者簡介：李幸剛（1992—），河南平頂山人，軟件工程專業。endprint