Parallel Binary Search Tree Construction Inspired by Thread-Level Speculation
Parallel Binary Search Tree Construction Inspired by Thread-Level Speculation
复制标题
受线程级推测启发的并行二叉搜索树构建
DOI：
10.1109/snpd-summer57817.2022.00021
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Nunome Atsushi
中科院分区：
文献类型：
--
作者：
Hirata Hiroaki;Nunome Atsushi
二叉搜索树（BST）是计算机科学中最重要的数据结构之一。 BST 的并行构造算法可以很容易地从顺序算法导出。然而，由于生成的BST的结构根据插入节点的顺序而不同，因此这种并行算法不能生成与顺序算法生成的BST具有相同结构（节点位置）的BST。因此，本文提出了一种新的并行算法来构造BST，其结构与顺序算法构造的BST具有相同的结构。该算法是基于线程级推测的概念衍生的，但它是一种纯粹的（非推测性的）并行算法。我们的实验表明，对于足够大的 BST 大小，实现我们的新算法的程序可以构建具有单一结构的 BST，与每次执行时构建具有不同结构的 BST 的程序相比，性能损失仅为 9%。
Binary search trees (BSTs) are one of the most important data structures in computer science. A parallel construction algorithm of a BST can be easily derived from the sequential algorithm. Since the structure of the generated BST is different depending on the order of inserted nodes, however, such a parallel algorithm cannot generate a BST with the same structure (node position) as a BST generated by the sequential algorithm. So this paper presents a new parallel algorithm to construct a BST having the same structure as a BST the sequential algorithm constructs. This algorithm was derived based on the concept of thread-level speculation but is a purely (non-speculatively) parallel one. Our experiments showed that for the large enough size of BSTs, the program implementing our new algorithm could construct a BST with a single structure by only 9% performance loss than the program that constructs BST having different structures every time of execution.
DOI：
10.4172/2165-7866.1000103
发表时间：
2011
期刊：
影响因子：
--
作者：
Jian Feng;D. Naiman;B. Cooper
通讯作者：
B. Cooper