Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts
Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts
复制标题
DOI：
10.1109/tc.2021.3075392
复制
发表时间：
2021-04
影响因子：
3.7
通讯作者：
Kyle Berney;H. Casanova;Ben Karsin;Nodari Sitchinava
中科院分区：
文献类型：
--
作者：
Kyle Berney;H. Casanova;Ben Karsin;Nodari Sitchinava
我们提出了并行算法，有效地置换成水平顺序二叉搜索树（BST），水平顺序B树（B树），和货车Emde博厄斯（vEB）布局的地方排序数组。我们分析确定我们的算法的复杂性和经验衡量其性能。当考虑就地置换数据和执行一系列搜索查询的总时间时，vEB布局在CPU上提供了最佳性能。给定$N$N= 5.37亿个64位整数的输入，当执行$N$N查询的0.37%时，查询性能的好处（与二进制搜索相比）超过就地置换的成本。在GPU上，结果取决于特定的架构，B树和vEB布局表现最好。使用二进制搜索达到收支平衡点所需的查询数量从$N$N= 10.74亿个32位整数的1.3%到8.9%不等。
We present parallel algorithms to efficiently permute a sorted array into the level-order binary search tree (BST), level-order B-tree (B-tree), and van Emde Boas (vEB) layouts in-place. We analytically determine the complexity of our algorithms and empirically measure their performance. When considering the total time to permute the data in-place and to perform a series of search queries, the vEB layout provides the best performance on the CPU. Given an input of $N$N=537 million 64-bit integers, the benefits of query performance (compared to binary search) outweigh the cost of in-place permutation when performing as few as 0.37% of $N$N queries. On the GPU, results depend on the particular architecture, with the B-tree and vEB layouts performing the best. The number of queries necessary to reach the break-even point with binary search ranges from 1.3% to 8.9% of $N$N=1,074 million 32-bit integers.