Abstract
We present and evaluate an implementation technique for histogram-like computations on GPUs that ensures both work-efficient asymptotic cost, support for arbitrary associative and commutative operators, and efficient use of hardwaresupported atomic operations when applicable. Based on a systematic empirical examination of the design space, we develop a technique that balances conflict rates and memory footprint. We demonstrate our technique both as a library implementation in CUDA, as well as by extending the parallel array language Futhark with a new construct for expressing generalized histograms, and by supporting this construct with several compiler optimizations. We show that our histogram implementation taken in isolation outperforms similar primitives from CUB, and that it is competitive or outperforms the hand-written code of several application benchmarks, even when the latter is specialized for a class of datasets.
Original language | English |
---|---|
Title of host publication | Proceedings of SC 2020 : International Conference for High Performance Computing, Networking, Storage and Analysis |
Publisher | IEEE |
Publication date | 2020 |
Article number | 9355244 |
ISBN (Electronic) | 9781728199986 |
DOIs | |
Publication status | Published - 2020 |
Event | 2020 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2020 - Virtual, Atlanta, United States Duration: 9 Nov 2020 → 19 Nov 2020 |
Conference
Conference | 2020 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2020 |
---|---|
Country/Territory | United States |
City | Virtual, Atlanta |
Period | 09/11/2020 → 19/11/2020 |
Sponsor | ACM's Special Interest Group on High Performance Computing (SIGHPC), Association for Computing Machinery, IEEE Computer Society, IEEE's Technical Committee on High Performance Computing (TCHPC) |
Keywords
- functional programming
- GPU
- parallelism