Scan primitives for GPU computing

By Shubhabrata Sengupta, Mark J. Harris, Yao Zhang, John Douglas Owens. GH '07, 2007

652 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/ec88941835c88a2956fc84c9e7cfd6dedf1b36f6

How researchers see this paper

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

Citations in the corpus

Implementing sparse matrix-vector multiplication on throughput-oriented processors (2009, methodology): “[20], provided in the CUDPP [9] library, and which we have previously used ourselves [10].”
GPU-accelerated preconditioned iterative linear solvers (2013, methodology): “Existing implementations of the GPU Sparse matrix-vector product (SpMV) include CUDPP (CUDA Data Parallel Primitives) library [24], NVIDIA CUSPARSE library [5] and the IBM SpMV library [4].”
A performance study of general-purpose applications on graphics processors using CUDA (2008, background): “One key example is a set of scan primitives developed by Sengupta et al. [25].”
Fast GPU-based locality sensitive hashing for k-nearest neighbor computation (2011, background): “Radix sort Radix sort [37] rearranges an array in ascending order in linear time.”
Position-Based Simulation Methods in Computer Graphics (2015, methodology): “Since the array contains the paths one after another, a segmented preﬁx sum [SHZO07] can be used to determine the preﬁx sums of all paths at once.”
Efficient Large-Scale Approximate Nearest Neighbor Search on the GPU (2016, methodology): “The pointer array is assembled by first computing a histogram of vectors over all bins and then computing the prefix sum [17].”
CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication (2015, methodology): “Therefore, the more complex segmented sum operation in [5, 9, 28, 15] can be converted to a faster preﬁx-sum scan operation (line 5) and a few arithmetic operations (lines 6–8). inclusive prefix sum scan ( *in ) 6: for i = 0 to length − 1 in parallel do 7: end for 9: free ( *tmp ) 10: end function…”
Efficient implementation of sorting on multi-core SIMD CPU architecture (2008, methodology): “Recently added GPU capabilities like scattered writes, ﬂexible comparisons and atomic operations on memory have enabled methods combining radixsort and mergesort to achieve faster performances on modern GPUs [19, 21, 22].”
Designing efficient sorting algorithms for manycore GPUs (2009, background): “Our radix sort is roughly twice as fast as the CUDPP radix sort [22].”
Relational joins on graphics processors (2008, methodology): “[33] implemented the segmented scan using the scatter.”
Accelerating Compute-Intensive Applications with GPUs and FPGAs (2008, background): “Domain specific parallel libraries, such as a recent scan primitives implementation [18] can be used as building blocks to ease parallel programming on the GPU.”
Relational query coprocessing on graphics processors (2009, methodology): “CUDPP: CUDA data parallel primitives library.”
Model-driven autotuning of sparse matrix-vector multiply on GPUs (2010, methodology): “For instance, our best BELLPACK implementation achieves up to 29.0 G.op/s in single-precision and 15.7 G.op/s in doubleprecision on the NVIDIA T10P multiprocessor (C1060), enhancing prior state-of-the-art unblocked implementations (Bell and Garland, 2009) by up to 1.8× and 1.5× for single-and…”
State-of-the-art in heterogeneous computing (2010, methodology): “Up and down sweep (GPU) [67,156]; Linked lists (CBEA) [19]; Histogram pyramids (GPU) [50,186]”
The Scalable Heterogeneous Computing (SHOC) benchmark suite (2010, methodology): “Level One benchmarks measure basic parallel algorithms, such as the Fast Fourier Transform (FFT) or the parallel pre-ﬁx sum (a.k.a. scan)[11].”
Rodinia: A benchmark suite for heterogeneous computing (2009, methodology): “Reductions, however, must be implemented manually in CUDA (although CUDA libraries [30] make the reduction easier), while in OpenMP this is handled by the compiler (e.g., in Back Propagation and SRAD ).”