Concurrent Binary Trees (with application to longest edge bisection)
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.
Description
@inproceedings{10.1145:3406186,
booktitle = {Proceedings of the ACM on Computer Graphics and Interactive Techniques},
editor = {Yuksel, Cem and Membarth, Richard and Zordan, Victor},
title = {{Concurrent Binary Trees (with application to longest edge bisection)}},
author = {Dupuy, Jonathan},
year = {2020},
publisher = {ACM},
ISSN = {2577-6193},
ISBN = {},
DOI = {10.1145/3406186}
}