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

摘 要：本文介紹了基于CUDA的奇偶排序并行算法，并給出GPU代碼，分析了用CPU與GPU代碼實(shí)現(xiàn)的優(yōu)缺點(diǎn)，可以讓我們對(duì)并行計(jì)算技術(shù)有更深刻的學(xué)習(xí)和了解。

關(guān)鍵詞：CUDA；奇偶排序；GPU；并行計(jì)算

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

1 引言

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

2 相關(guān)概念

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

CUDA是NVIDIA公司最新推出的產(chǎn)品，通過CUDA平臺(tái)可以充分利用并行計(jì)算的優(yōu)勢(shì)來處理計(jì)算問題[2]。CUDA的GPU端語(yǔ)言采用C，所以對(duì)于開發(fā)者來說，使用起來更加簡(jiǎn)單。CUDA可廣泛的應(yīng)用在圖形學(xué)、生物、科學(xué)計(jì)算、地質(zhì)、物理模擬等需要大規(guī)模并行計(jì)算的領(lǐng)域。

3 奇偶排序

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

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

4 代碼實(shí)現(xiàn)

CPU版的奇偶排序代碼非常簡(jiǎn)單，我們?cè)诖瞬辉诮o出，奇偶排序算法的GPU實(shí)現(xiàn)，代碼如下：

5 總結(jié)

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

參考文獻(xiàn)：

[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]陳國(guó)良.并行計(jì)算：結(jié)構(gòu)、算法、編程[B].北京：高等教育出版社，2003.

作者簡(jiǎn)介：李幸剛（1992—），河南平頂山人，軟件工程專業(yè)。endprint