Parallel Prefix Sum (Scan) with CUDA
NVIDIA
In GPU Gems 3 (12 August 2007)
@article{harris2007parallel,
title={Parallel prefix sum (scan) with CUDA},
author={Harris, M. and Sengupta, S. and Owens, J.D.},
journal={GPU Gems},
volume={3},
number={39},
pages={851–876},
year={2007},
publisher={Citeseer}
}
Parallel prefix sum, also known as parallel Scan, is a useful building block for many parallel algorithms including sorting and building data structures. In this document we introduce Scan and describe step-by-step how it can be implemented efficiently in NVIDIA CUDA. We start with a basic naive algorithm and proceed through more advanced techniques to obtain best performance. We then explain how to scan arrays of arbitrary size that cannot be processed with a single block of threads.
January 9, 2011 by hgpu
