在第五讲中我们学习了GPU三个重要的基础并行算法： Reduce, Scan 和 Histogram，分析了 其作用与串并行实现方法。 在第六讲中，本文以冒泡排序 Bubble Sort、归并排序 Merge Sort 和排序网络中的双调排序 Bitonic Sort 为例， 讲解如何从数据结构课上学的串行并行排序方法转换到并行排序，并附GPU实现代码。
在并行方法中，我们将考虑到并行方法需要注意的特点进行设计，希望大家在读完本文后对GPU上并行算法的设计有一些粗浅的认识。需注意的特点如下： 1. 充分发挥硬件能力（尽量不要有空闲且一直处于等待状态的SM） 2. 限制branch divergence（见CUDA系列学习（二）） 3. 尽量保证内存集中访问（即防止不命中）
( 而我们在数据结构课上学习的sort算法往往不注意这几点。)
CUDA系列学习目录：
CUDA系列学习（一）An Introduction to GPU and CUDA
CUDA系列学习（二）CUDA memory & variables – different memory and variable types
CUDA系列学习（三）GPU设计与结构QA & coding练习
CUDA系列学习（四）Parallel Task类型 与 Memory Allocation
CUDA系列学习（五）GPU基础算法: Reduce, Scan, Histogram
I. Bubble Sort
冒泡排序，相信大家再熟悉不过了。经典冒泡排序通过n轮有序冒泡(n为待排序的数组长度)得到有序序列， 其时间复杂度O(1), 空间复杂度O(n^2)。
那么如何将冒泡排序算法改成并行算法呢？ 这里就需要解除一些依赖关系， 比如是否能解除n轮冒泡间的串行依赖 & 是否能解除每一轮冒泡内部的串行依赖， 使得同样的n^2次冒泡操作可以通过并行， 降低step complexity。 1996年， J Kornerup针对这些问题提出了odd-even sort算法，并在论文中证明了其排序正确性。
I.1 从Bubble Sort到Odd-even Sort
先来看一下odd-even sort的排序方法:
图1.1
上图为odd-even sort的基本方法。 奇数步中， array中奇数项array[i]与右边的item(array[i + 1])比较； 偶数步中， array中奇数项array[i]与左边的item(array[i – 1]) 比较；
这样，同一个step中的各个相邻比较就可以并行化了。
PS： 对于array中有偶数个元素的数组也是一样：
图1.2
I.2 Odd-even Sort复杂度
在odd-even sort的算法下， 原本O(n^2)的总比较次数不变，但是由于并行，时间复杂度降到O(n), 即
step complexity = O(n) work complexity = O(n^2)
code详见 < Bubble sort and its variants >
II. Merge Sort
看过odd-even sort后，我们来看如何将归并排序并行化。数据结构课上我们都学过经典归并排序： 基于divide & conquer 思想， 每次将一个array分拆成两部分， 分别排序后合并两个有序序列。 可以通过 T(n)=2T(n/2)+n 得到， 其complexity = O(nlogn)。 和I.1节类似， 我们看看merge sort中的哪些步是可以并行的。
这里可以将基于merge sort的大规模数据排序分为三部分。 经过divide步之后， 数据分布如图所示：
图2.1
最下端的为 大量-短序列 的合并； 中间一块为中等数量-中等长度序列 的合并； 最上端的为少量-长序列 的合并；
我们分这三部分进行并行化。 之后大家会明白为啥要这么分~
II.1 Step 1: Huge number of small tasks
这一部分，每一部分序列合并的代价很小， 而有众多这样的任务。 所以我们采取给每个merge一个thread去执行， thread 内部就用串行merge的方法。
II.2 Step 2: Mid number of mid task
在这一阶段， 有中等数量的task， 每个task的工作量也有一定增长。 所以我们采取给每个merge一个SM去执行， 每个block上运行的多个thread并行merge的方法。 和step1中的主要区别就是block内部merge从串行改成了并行。 那么怎样去做呢？
如下图所示，假如现在有两个长为4个元素的array， 想对其进行排序， 将merge排序结果index 0 – 7 写入数据下方方块。
图2.2
做法： 对于array中的每个数字， 看两个位置： 1. 自己所在序列的位置： 看它前面有几个元素 2. 另一个序列的位置： 另一个序列中有多少个元素比它小（采用二分搜索）
这样做来， 第一步O(1)可得到， 第二步二分查找O（logn）可得到； 整个merge过程用shared memory存结果。
II.3 Step 3: Small number of huge task
第三个环节中，也就是merge的顶端（最后一部分），每个merge任务的元素很多， 但是merge任务数很少。 这种情况下， 如果采用Step2的方法， 最坏的情况就是只有一个很大的task在跑， 此时只有1个SM在忙， 其他空闲SM却没法利用， 所以这里我们尝试将一个任务分给多个SM执行。
方法： 如图2.3所示， 将每个序列以256个元素为单位分段， 得到两个待merge序列In1和In2。然后，对这些端节点排序，如EABFCGDH。 如step2中的方法， 我们计算每个段节点在另一个短序列（长256）中的位置， 然后只对中间那些不确定的部分进行merge排序， 每个merge分配一个SM。
如E~A的部分， 1. 计算出E在In1中的位置posE1, A在In2中的位置posA2 2. merge In1中 posE1~A 和 In2中 E~posA2的元素
图2.3
II.4 Merge sort in GPU
以上面step 1的merge sort为例，， 其gpu代码中kernel函数如下：
其中temp为排好序的序列， 每次排序两个大小为sortedsize的block，为temp赋值2 * sortedsize个元素。
宁愿停歇在你门前的那棵树上，看着你，守护你。
