基于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