Counting and Occurrence Sort for GPUs using an Embedded Language

Josef Svenningsson, Bo Joel Svensson, Mary Sheeran
Dept, of Computer Science and Engineering, Chalmers University of Technology
FHPC, 2013


   title={Counting and Occurrence Sort for GPUs using an Embedded Language},

   author={Svenningsson, Josef and Svensson, Bo Joel and Sheeran, Mary},



Download Download (PDF)   View View   Source Source   Source codes Source codes




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, dataparallel 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: