2595

Efficient Parallel Scan Algorithms for GPUs

Shubhabrata Sengupta, Mark Harris, Michael Garland
University of California, Davis
NVIDIA Technical Report NVR-2008-003, December 2008

@techreport{sengupta2008efficient,

   title={Efficient parallel scan algorithms for GPUs},

   author={Sengupta, S. and Harris, M. and Garland, M.},

   year={2008},

   institution={Citeseer}

}

Scan and segmented scan algorithms are crucial building blocks for a great many data-parallel algorithms. Segmented scan and related primitives also provide the necessary support for the flattening transform, which allows for nested data-parallel programs to be compiled into flat data-parallel languages. In this paper, we describe the design of efficient scan and segmented scan parallel primitives in CUDA for execution on GPUs. Our algorithms are designed using a divide-and-conquer approach that builds all scan primitives on top of a set of primitive intra-warp scan routines. We demonstrate that this design methodology results in routines that are simple, highly efficient, and free of irregular access patterns that lead to memory bank conflicts. These algorithms form the basis for current and upcoming releases of the widely used CUDPP library.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: