A Novel Sorting Algorithm for Many-core Architectures Based on Adaptive Bitonic Sort
A Novel Sorting Algorithm for Many-core Architectures Based on Adaptive Bitonic Sort
复制标题
一种基于自适应双调排序的多核架构排序算法
DOI：
10.1109/ipdps.2012.30
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
N. Luttenberger
中科院分区：
文献类型：
--
作者：
H. Peters;Ole Schulz;N. Luttenberger
自适应双onic排序是一种著名的基于归并的并行排序算法。它使用一种称为bitonic树的复杂的树状数据结构来实现最佳的复杂性。因此，将自适应双元排序与其他算法一起使用通常意味着将双元树转换为数组，反之亦然。这使得自适应双onic排序在混合排序算法的上下文中不合适，在混合排序算法之间执行频繁切换。在本文中，我们提出了一种新的最优排序算法，该算法基于一种类似于自适应双onic排序的方法。我们的方法不使用bitonic树，而是使用输入数组和一些附加信息。使用这种方法，在自适应双元排序和其他算法之间切换是很容易的。我们提出了一种基于双元排序和我们的新算法的gpu混合算法的实现。这个实现被证明是文献中最快的gpu基于比较的排序算法。
Adaptive bitonic sort is a well known merge-based parallel sorting algorithm. It achieves optimal complexity using a complex tree-like data structure called a bitonic tree. Due to this, using adaptive bitonic sort together with other algorithms usually implies converting bitonic trees to arrays and vice versa. This makes adaptive bitonic sort inappropriate in the context of hybrid sorting algorithms where frequent switches between algorithms are performed. In this article we present a novel optimal sorting algorithm that is based on an approach similar to adaptive bitonic sort. Our approach does not use bitonic trees but uses the input array together with some additional information. Using this approach it is trivial to switch between adaptive bitonic sort and other algorithms. We present an implementation of a hybrid algorithm for GPUs based on bitonic sort and our novel algorithm. This implementation turns out to be the fastest comparison-based sorting algorithm for GPUs found in literature.