Bontes, Johan and Gain, James (2024) Redzone stream compaction: removing k items from a list in parallel O(k) time, ACM Trans. Parallel Comput., Association for Computing Machinery.
![[thumbnail of redzone.pdf]](https://pubs.cs.uct.ac.za/style/images/fileicons/text.png) |
Text
redzone.pdf - Accepted Version Download (373kB) |
Abstract
Stream compaction, the parallel removal of selected items from a list, is a fundamental building block in parallel algorithms. It is extensively used, both in computer graphics, for shading, collision detection, and ray tracing, as well as in general computing, such as for tree traversal and database selection. In this paper we present Redzone stream compaction, the first parallel stream compaction algorithm to remove k items from a list with n ≥ k elements in O(k) rather than O(n) time. Based on our benchmark experiments on both GPU and CPU, if k is proportionally small (k ≪ n) Redzone outperforms existing parallel stream compaction by orders of magnitude, while if k is close to n it underperforms by a constant factor. Redzone removes items in-place and needs only O(1) auxiliary space. However, unlike current O(n) algorithms, it is unstable (i.e., the order of elements is not preserved) and it needs a list of the items to be removed.
| Item Type: | Journal article (online only) |
|---|---|
| Additional Information: | Just Accepted. Online: https://doi.org/10.1145/367578 |
| Uncontrolled Keywords: | Stream compaction, list removal |
| Subjects: | Computing methodologies > Concurrent computing methodologies |
| Date Deposited: | 14 Aug 2024 07:14 |
| Last Modified: | 14 Aug 2024 07:14 |
| URI: | https://pubs.cs.uct.ac.za/id/eprint/1692 |
Actions (login required)
 |
View Item |