RECURSIVE STAR-TREE PARALLEL DATA STRUCTURE
RECURSIVE STAR-TREE PARALLEL DATA STRUCTURE
复制标题
DOI：
10.1137/0222017
复制
发表时间：
1993-04-01
影响因子：
1.6
通讯作者：
VISHKIN, U
中科院分区：
文献类型：
--
作者：
BERKMAN, O;VISHKIN, U
本文介绍了一种新的并行数据结构，称为递归星型树（记为“* 树”）。对于它的定义，使用了 * 泛函的推广（其中对于函数f * f（n）= min{i\f（i）（n）小于或等于1}，f（i）是f的第i阶）。递归 *-树是根据逆阿克曼函数的思想，通过递归方法得到的，递归 *-树数据结构为并行算法提供了一种新的设计范式。这种范例允许非常快的并行计算，具体来说，O（alpha（n））时间（其中alpha（n）是Ackermann函数的逆），在（最弱的）并发读、并发写并行随机存取机器上使用最优数量的处理器这些计算只需要恒定的时间，如果将以下关于并行计算模型的非标准假设添加到CRCW PRAM，则使用最佳处理器数量：极少数处理器，每个处理器都可以同时写入同一个字的不同位。应用包括通过比该问题的已知算法简单得多的新算法来寻找树中的最低共同祖先，限制域合并，括号匹配，和一个新的并行约简。
This paper introduces a novel parallel data structure called the recursive star-tree (denoted ''*-tree''). For its definition a generalization of the * functional is used (where for a function f * f (n) = min{i\f(i)(n) less-than-or-equal-to 1} and f(i) is the ith iterate of f). Recursive *-trees are derived by using recursion in the spirit of the inverse Ackermann function.The recursive *-tree data structure leads to a new design paradigm for parallel algorithms. This paradigm allows for extremely fast parallel computations, specifically, O(alpha(n)) time (where alpha(n) is the inverse of the Ackermann function), using an optimal number of processors on the (weakest) concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM).These computations need only constant time, and use an optimal number of processors if the following nonstandard assumption about the model of parallel computation is added to the CRCW PRAM: an extremely small number of processors each can write simultaneously into different bits of the same word.Applications include finding lowest common ancestors in trees by a new algorithm that is considerably simpler than the known algorithms for the problem, restricted domain merging, parentheses matching, and a new parallel reducibility.