Joinable Parallel Balanced Binary Trees
Joinable Parallel Balanced Binary Trees
复制标题
可连接的并行平衡二叉树
DOI：
10.1145/3512769
复制
发表时间：
2022
影响因子：
1.6
通讯作者：
Sun, Yihan
中科院分区：
文献类型：
--
作者：
Blelloch, Guy;Ferizovic, Daniel;Sun, Yihan
在本文中，我们将展示如何使用单个函数join简单而高效地实现并行平衡二叉搜索树（bst）。基于onjoin，我们的方法适用于多个平衡树数据结构，以及有序集合和映射的各种函数。我们将我们的技术描述为一种算法框架，称为基于连接的算法。我们展示了joinfunction完全捕获了各种树算法重新平衡树所需的东西，只要平衡方案满足某些属性，我们将其称为joinabletrees。我们讨论了四种可连接的平衡方案：AVL树、红黑树、权重平衡树和树堆。我们提出了多种适用于可接合树的树算法，包括插入、删除、并、交、差、分割、范围、过滤等，其中大多数算法也是并行的。这些算法是通用的跨平衡方案。在比较模型中，许多算法都是最优的，我们提供了一个一般的证明来证明可接合树的工作效率。这些算法都是高度并行的，都具有多对数跨度（并行依赖）。具体来说，集合-集合操作（并、交和差）对于输入集大小和具有多对数跨度。我们在四种平衡方案上实现并测试了我们的算法。一般来说，所有四种方案的性能都非常相似，但权重平衡树的性能略优于其他方案。它们具有相同的加速特性，在72个内核（144个超线程）上获得大约73个加速。实验结果还表明，我们的实现优于现有的并行实现，在不同的输入大小上，我们的顺序版本比c++标准模板库（STL）中的顺序合并算法达到了接近或更好的性能。
In this article, we show how a single function,join, can be used to implement parallelbalanced binary search trees(BSTs) simply and efficiently. Based onjoin, our approach applies to multiple balanced tree data structures, and a variety of functions for ordered sets and maps. We describe our technique as an algorithmic framework calledjoin-based algorithms. We show that thejoinfunction fully captures what is needed for rebalancing trees for a variety of tree algorithms, as long as the balancing scheme satisfies certain properties, which we refer to asjoinabletrees. We discuss four balancing schemes that are joinable: AVL trees, red-black trees, weight-balanced trees, and treaps. We present a variety of tree algorithms that apply to joinable trees, includinginsert,delete,union,intersection,difference,split,range,filter, and so on, most of them also parallel. These algorithms are generic across balancing schemes. Many algorithms are optimal in the comparison model, and we provide a general proof to show the efficiency in work for joinable trees. The algorithms are highly parallel, all with polylogarithmic span (parallel dependence). Specifically, the set-set operationsunion,intersection, anddifferencehave workand polylogarithmic span for input set sizesand.We implemented and tested our algorithms on the four balancing schemes. In general, all four schemes have quite similar performance, but the weight-balanced tree slightly outperforms the others. They have the same speedup characteristics, getting around 73speedup on 72 cores (144 hyperthreads). Experimental results also show that our implementation outperforms existing parallel implementations, and our sequential version achieves close or much better performance than the sequential merging algorithm in C++ Standard Template Library (STL) on various input sizes.
登录
查看更多内容
DOI：
10.1145/3460874
发表时间：
2018-07
期刊：
ACM Transactions on Parallel Computing (TOPC)
影响因子：
--
作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
通讯作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
用于查找哈密顿循环的数据结构
影响因子：
1.1
作者：
M. Chrobak;Tomasz Szymacha;A. Krawczyk
通讯作者：
A. Krawczyk
STAPL 中的关联并行容器
DOI：
--
发表时间：
2007
期刊：
International Workshop on Languages and Compilers for Parallel Computing
影响因子：
--
作者：
Ilie Gabriel Tanase;C. Raman;Mauro Bianco;N. Amato;Lawrence Rauchwerger
通讯作者：
Lawrence Rauchwerger
只需加入并行有序集
DOI：
10.1145/2935764.2935768
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Daniel Ferizovic;Yihan Sun
通讯作者：
Yihan Sun
使用增强地图进行并行范围、线段和矩形查询
DOI：
10.1137/1.9781611975499.13
发表时间：
2018
期刊：
ACM Transactions on Database Systems (TODS)
影响因子：
--
作者：
Yihan Sun;G. Blelloch
通讯作者：
G. Blelloch