Count Sort for GPU Computing
Count Sort for GPU Computing
复制标题
用于 GPU 计算的计数排序
DOI：
10.1109/icpads.2009.30
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Zongmin Ma
中科院分区：
文献类型：
--
作者：
Weidong Sun;Zongmin Ma
计数排序是一种简单、稳定、高效、运行时间线性的排序算法，是许多应用程序的基本组成部分。本文描述了在商用多处理器GPU上使用NVIDIA公司的计算统一设备架构（CUDA）平台实现计数排序算法的数据并行实现的设计问题。完全并行版本在CPU上的运行速度比任何串行实现都要快得多，但由于大规模线程并行模型的限制而失去了稳定性。但是线程级并行实现仍然为许多应用程序提供了有效的并行排序原语，这些应用程序不需要稳定的排序，或者可以适应不稳定的子例程。
Counting sort is a simple, stable and efficient sort algorithm with linear running time, which is a fundamental building block for many applications. This paper depicts the design issues of a data parallel implementation of the count sort algorithm on a commodity multiprocessor GPU using the Compute Unified Device Architecture (CUDA) platform, both from NVIDIA Corporation. The full parallel version runs much faster than any serial implementation on CPU with the loss of stability due to the limitation of the massive threads parallel model. But the thread-level parallel implementation still provides an efficient parallel sort primitive for many applications, which do not require stable sort or can be adapted for unstable subroutines.