Concurrent Binary Trees (with application to longest edge bisection)
| dc.contributor.author | Dupuy, Jonathan | en_US |
| dc.contributor.editor | Yuksel, Cem and Membarth, Richard and Zordan, Victor | en_US |
| dc.date.accessioned | 2020-10-30T18:18:29Z | |
| dc.date.available | 2020-10-30T18:18:29Z | |
| dc.date.issued | 2020 | |
| dc.description.abstract | We introduce the concurrent binary tree (CBT), a novel concurrent representation to build and update arbitrary binary trees in parallel. Fundamentally, our representation consists of a binary heap, i.e., a 1D array, that explicitly stores the sum-reduction tree of a bitfield. In this bitfield, each one-valued bit represents a leaf node of the binary tree encoded by the CBT, which we locate algorithmically using a binary-search over the sum-reduction. We show that this construction allows to dispatch down to one thread per leaf node and that, in turn, these threads can safely split and/or remove nodes concurrently via simple bitwise operations over the bitfield. The practical benefit of CBTs lies in their ability to accelerate binary-tree-based algorithms with parallel processors. To support this claim, we leverage our representation to accelerate a longest-edgebisection- based algorithm that computes and renders adaptive geometry for large-scale terrains entirely on the GPU. For this specific algorithm, the CBT accelerates processing speed linearly with the number of processors. | en_US |
| dc.description.number | 2 | |
| dc.description.sectionheaders | Hardware Architectures and Space Partitioning | |
| dc.description.seriesinformation | Proceedings of the ACM on Computer Graphics and Interactive Techniques | |
| dc.description.volume | 3 | |
| dc.identifier.doi | 10.1145/3406186 | |
| dc.identifier.issn | 2577-6193 | |
| dc.identifier.uri | https://doi.org/10.1145/3406186 | |
| dc.identifier.uri | https://diglib.eg.org:443/handle/10.1145/3406186 | |
| dc.publisher | ACM | en_US |
| dc.subject | Computing methodologies | |
| dc.subject | Massively parallel algorithms | |
| dc.subject | Rendering. | |
| dc.subject | binary tree | |
| dc.subject | concurrent | |
| dc.subject | parallel | |
| dc.subject | binary heap | |
| dc.subject | longest edge bisection | |
| dc.subject | GPU | |
| dc.subject | real | |
| dc.subject | time | |
| dc.title | Concurrent Binary Trees (with application to longest edge bisection) | en_US |