欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

GPU编程sort实现原理

冒泡排序

对于有n个元素的待排序数组,去n/2个计算单元,最多执行step为n,对于任何一个线程i,交替和自己的左边和右边元素比大小,大小逆序就更换元素的值。这个方式step复杂度为 \(O(n)\) ,work复杂度为 \(O(n^2)\)

归并排序

实际的归并排序中,并不会从一开始一个元素就调用归并算法,归并排序分为三个阶段:

  1. 短队列归并
  2. 中等队列归并
  3. 长队列归并

中等队列归并

而是调用别的效率更高的算法。等元素达到一定规模,再进行归并。归并的方式还是按照以前的套路,并行计算出来地址,相互没有影响,从而提高效率。具体计算地址的时候公式为:

\(pos = self_{pos} + offset_{pos}\)

其中 \(offset_{pos}\) 表示的是当前位置的数值在另外一个队列中是第几大的,通过二分查找可以做到log(n)的时间复杂度求得。

长队列归并

这是一个将大问题分解为小问题的典型的例子;具体为,两个个队列每隔256个元素抽出来一个元素,将两类元素排序,得到分割点。然后再进行分段分别排序即可。

Sorting Network

这是一个很有意思的方法,就是只是用「swap」操作达到排序的目的。Sorting Network具体介绍「戳我」。

不同的排序算法使用Sorting Network表示,如下图:

QQ20170205-0

Bitonic sorter(双调排序)

Bitonic sorter可看做是Sorting Network的一个实现,具体介绍「戳我」。Bitonic sorter的方式时间复杂度是 \(n log(n)^2\) ,次复杂度对数据分布不敏感.这个方法关键的地方就是在合并的时候两个有序列表如何利用GPU加速处理,其实就是将两个长度为m有序列表合并为一个列表,并保证合并后的列表前m个小于(大于)后m。个具体算法如下图:

843px-BitonicSort1.svg

Radix Sort

时间复杂度为 \(O(kn)\) ,借助compact操作,可以很方便的实现这个算法。算法过程如下图:

img1570

图片来源:Counting Sort and Radix Sort

Quick Sort

思路比较简单,就是选择一个元素对原始数据进行分段,分段之后对每一分段进行递归调用。

资料

https://en.wikipedia.org/wiki/Sorting_network

https://en.wikipedia.org/wiki/Bitonic_sorter

未经允许不得转载:大数据算法 » GPU编程sort实现原理

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站