NEW ALGORITHMS FOR GPU STREAM COMPACTION - A Comparative Study
Pedro Miguel Moreira, Luís Paulo Reis, A. Augusto de Sousa
2009
Abstract
With the advent of GPU programmability, many applications have transferred computational intensive tasks into it. Some of them compute intermediate data comprised by a mixture of relevant and irrelevant elements in respect to further processing tasks. Hence, the ability to discard irrelevant data and preserve the relevant portion is a desired feature, with benefits on further computational effort, memory and communication bandwidth. Parallel stream compaction is an operation that, given a discriminator, is able to output the valid elements discarding the rest. In this paper we contribute two original algorithms for parallel stream compaction on the GPU. We tested and compared our proposals with state-of-art algorithms against different data-sets. Results demonstrate that our proposals can outperform prior algorithms. Result analysis also demonstrate that there is not a best algorithm for all data distributions and that such optimal setting is difficult to be achieved without prior knowledge of the data characteristics.
DownloadPaper Citation
in Harvard Style
Moreira P., Reis L. and de Sousa A. (2009). NEW ALGORITHMS FOR GPU STREAM COMPACTION - A Comparative Study . In Proceedings of the Fourth International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2009) ISBN 978-989-8111-67-8, pages 119-128. DOI: 10.5220/0001783601190128
in Bibtex Style
@conference{grapp09,
author={Pedro Miguel Moreira and Luís Paulo Reis and A. Augusto de Sousa},
title={NEW ALGORITHMS FOR GPU STREAM COMPACTION - A Comparative Study},
booktitle={Proceedings of the Fourth International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2009)},
year={2009},
pages={119-128},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001783601190128},
isbn={978-989-8111-67-8},
}
in EndNote Style
TY - CONF
JO - Proceedings of the Fourth International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2009)
TI - NEW ALGORITHMS FOR GPU STREAM COMPACTION - A Comparative Study
SN - 978-989-8111-67-8
AU - Moreira P.
AU - Reis L.
AU - de Sousa A.
PY - 2009
SP - 119
EP - 128
DO - 10.5220/0001783601190128