Counting and occurrence sort for GPUs using an embedded language
Counting and occurrence sort for GPUs using an embedded language
复制标题
使用嵌入式语言对 GPU 进行计数和出现排序
DOI：
10.1145/2502323.2502325
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
M. Sheeran
中科院分区：
文献类型：
--
作者：
Josef Svenningsson;Bo Joel Svensson;M. Sheeran
本文研究了两种排序算法：计数排序和一种变体（出现排序），该算法还删除了重复元素，并检查了它们在GPU上运行的适用性。重复删除变体具有自然的功能，数据并行实现，这使得它对GPU特别感兴趣。
这些算法是在Obsidian中实现的，Obsidian是一种用于GPU编程的高级域特定语言。
测量表明，我们的实现在许多情况下优于库推力提供的排序算法。此外，出现排序比普通计数排序快2倍。我们的结论是，计数排序是一个重要的竞争者时，考虑排序算法的GPU，发生排序是非常可取的。我们还表明，黑曜石可以产生非常有竞争力的代码。
This paper investigates two sorting algorithms: counting sort and a variation, occurrence sort, which also removes duplicate elements, and examines their suitability for running on the GPU. The duplicate removing variation turns out to have a natural functional, data-parallel implementation which makes it particularly interesting for GPUs.
The algorithms are implemented in Obsidian, a high-level domain specific language for GPU programming.
Measurements show that our implementations in many cases outperform the sorting algorithm provided by the library Thrust. Furthermore, occurrence sort is another factor of two faster than ordinary counting sort. We conclude that counting sort is an important contender when considering sorting algorithms for the GPU, and that occurrence sort is highly preferable when applicable. We also show that Obsidian can produce very competitive code.