Dynamic Parallel Tree Contraction
Dynamic Parallel Tree Contraction
复制标题
动态并行树收缩
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
S. Tate
中科院分区：
文献类型：
--
作者：
J. Reif;S. Tate
并行树收缩已被发现是设计一大类高效图算法的有用且相当强大的工具。我们提出了一种用于并行解决增量问题的相应技术。作为我们的计算模型，我们假定一种并发读并发写并行随机存取机（CRCW PRAM）的变体，在其中我们可以通过一个派生操作动态地激活处理器。我们考虑一棵具有≤n个节点且深度无界的动态二叉树T。我们描述了一个过程，我们称之为动态并行树收缩算法，它增量式地处理各种并行修改请求和查询：（1）添加或删除T的叶子，或修改T的内部节点或叶子的标签的并行请求，以及（2）需要重新计算指定节点的值的并行树收缩查询。每个修改或查询都是针对T中的一组节点U。我们的动态并行树收缩算法是一种随机算法，它使用O(|U| log n log(|U| log n))个处理器，在期望的并行时间O(log(|U| log n))内完成。我们给出了大量应用（具有相同的界），包括：（a）维护常见的树属性（如祖先数量、先序等），（b）欧拉环游，（c）表达式求值，（d）最近公共祖先，以及（e）树的规范形式。以前，对于增量式地维护和并行解决此类问题，在并行时间小于Θ(log n)的情况下，没有已知的并行算法。在推导我们的增量算法时，我们在相同的渐近界内解决了一个关键子问题，即处理器激活问题，这在其他并行增量算法的设计中可能是有用的。该算法使用了一种有趣的持久化并行数据结构，涉及一种非平凡的构造。在后续的一篇论文中，我们将我们的动态并行树收缩技术应用于各种增量图问题：维护并行串联图、外平面图、赫林网络、带宽受限网络以及具有常数分隔器大小的各种其他图的各种属性（如着色、最小覆盖集、最大匹配等）。
Parallel tree contraction has been found to be a useful and quite powerful tool for the design of a wide class of efficient graph algorithms. We propose a corresponding technique for the parallel solution of incremental problems. As our computational model, we assume a variant of the CRCW PRAM where we can dynamically activate processors by a forking operation. We consider a dynamic binary tree T of ≤ n nodes and unbounded depth. We describe a procedure, which we call the dynamic parallel tree contraction algorithm, which incrementally processes various parallel modification requests and queries: (1) parallel requests to add or delete leaves of T , or modify labels of internal nodes or leaves of T , and also (2) parallel tree contraction queries which require recomputing values at specified nodes. Each modification or query is with respect to a set of nodes U in T . Our dynamic parallel tree contraction algorithm is a randomized algorithm that takesO(log(|U | logn)) expected parallel time using O( |U| log n log(|U| log n) ) processors. We give a large number of applications (with the same bounds), including: (a) maintaining the usual tree properties (such as number of ancestors, preorder, etc.), (b) Eulerian tour, (c) expression evaluation, (d) least common ancestor, and (e) canonical forms of trees. Previously, there where no known parallel algorithms for incrementally maintaining and solving such problems in parallel time less than Θ(log n). In deriving our incremental algorithms, we solve a key subproblem, namely a processor activation problem, within the same asymptotic bounds, which may be useful in the ∗This research was supported by DARPA/ISTO Grant N00014-91J-1985, Subcontract KI-92-01-0182 of DARPA/ISTO prime Contract N00014-92-C-0182, NSF Grant NSF-IRI-91-00681, and NASA subcontract 550-63 of prime Contract NAS5-30428. †Permanent address: Department of Computer Science, Duke University, Box 90129, Durham, NC 27708–0129 design of other parallel incremental algorithms. This algorithm uses an interesting persistent parallel data structure involving a non-trivial construction. In a subsequent paper, we apply our dynamic parallel tree contraction technique to various incremental graph problems: maintaining various properties, (such as coloring, minimum covering set, maximum matching, etc.) of parallel series graphs, outerplanar graphs, Helin networks, bandwidth-limited networks, and various other graphs with constant separator size.