Designing efficient sorting algorithms for manycore GPUs

By Nadathur Rajagopalan Satish, Mark J. Harris, Michael Garland. 2009 IEEE International Symposium on Parallel & Distributed Processing, 2009

729 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/2f1bffb15f7881aadd74acd25fee02bd8f186b36

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Efficient implementation of sorting on multi-core SIMD CPU architecture (2008, methodology): “Table 2 lists the best reported execution times4 (in seconds) for varying dataset sizes on various architectures( IBM Cell [7], Nvidia 8600 GTS [22], Nvidia 8800 GTX and Quadro FX 5600 [ 19 ], Intel 2-core Xeon with Quicksort [7], and IBM PowerPC 970MP [11]).”
Design and implementation of a parallel priority queue on many-core architectures (2012, background): “The most efficient sorting routine on GPGPUs so far is the radix sort implementation [27], which is the starting point of our sorting implementation.”
The Scalable Heterogeneous Computing (SHOC) benchmark suite (2010, background): “• Sort Measures device performance for a very fast radix sort algorithm [10] which sorts key-value pairs of single precision ﬂoating point data.”
Computational Physics on Graphics Processing Units (2012, background): “Performance can be further improved by sorting particles depending on the index of the voxel they belong, making neighbouring particles in space, to a degree, close in memory, thus increasing coalescence and cache hit rate on GPU systems; such a task can be done with radix count sort [15,16,17] in O”
State-of-the-art in heterogeneous computing (2010, background): “Sorting Bitonic sort (GPU) [135]; Hybrid radix-bitonic, out-of-core (GPU) [136]; Radix (GPU) [137]; AA-sort (CBEA) [138].”
Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU (2010, methodology): “On GPUs, where SIMD us e is important, the algorithm is rewritten using a 1-bit sort p rimitive, called split [39].”
A Comprehensive Performance Comparison of CUDA and OpenCL (2011, methodology): “The benchmark uses the four-step radix sort in each pass proposed in papers [28] [29].”
Randomized selection on the GPU (2011, methodology): “We used CUDPP [CUDA 2010; Satish et al 2009] for the small internal sorts, random selections and one of the prefix-sums.”