Scan Primitives for GPU Computing

Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D.

Scan Primitives for GPU Computing

Files

097-106.pdf (724.11 KB)

Date

2007

Authors

Sengupta, Shubhabrata
Harris, Mark
Zhang, Yao
Owens, John D.

Publisher

The Eurographics Association

Abstract

The scan primitives are powerful, general-purpose data-parallel primitives that are building blocks for a broad range of applications. We describe GPU implementations of these primitives, specifically an efficient formulation and implementation of segmented scan, on NVIDIA GPUs using the CUDA API. Using the scan primitives, we show novel GPU implementations of quicksort and sparse matrix-vector multiply, and analyze the performance of the scan primitives, several sort algorithms that use the scan primitives, and a graphical shallow-water fluid simulation using the scan framework for a tridiagonal matrix solver.

        @inproceedings{:10.2312/EGGH/EGGH07/097-106
,
booktitle = {SIGGRAPH/Eurographics Workshop on Graphics Hardware
},
editor = {Mark Segal and Timo Aila
},
title = {{Scan Primitives for GPU Computing
}},
author = {Sengupta, Shubhabrata and 
Harris, Mark and 
Zhang, Yao and 
Owens, John D.
},
year = {2007
},
publisher = {The Eurographics Association
},
ISSN = {1727-3471
},
ISBN = {978-3-905673-47-0
},
DOI = {/10.2312/EGGH/EGGH07/097-106
}
}