Optimal simulations of tree machines
Optimal simulations of tree machines
复制标题
树木机器的优化模拟
DOI：
10.1109/sfcs.1986.38
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
A. Rosenberg
中科院分区：
文献类型：
--
作者：
S. Bhatt;F. C. Graham;F. Leighton;A. Rosenberg
通用网络提供的优势是，它们可以执行为更简单的体系结构编写的程序，而不会产生显著的运行时开销。在本文中，我们研究了树机器的模拟；事实上，分而治之的算法是在树上自然编程的，这激发了我们的研究。在并行计算的各种提议中，布尔超立方体已经成为一种特别通用的网络。众所周知，例如，通过将网格嵌入为超立方体的子图，可以在没有通信开销的超立方体上执行用于多维网格机的程序。我们的第一个结果是，任何树机器的程序都可以在超立方体上以恒定的开销执行。更准确地说，同步二叉树的每一个循环都可以在超立方体上以O(1)个循环来模拟，而与树的形状无关。在超立方体中嵌入树的算法以多项式时间运行。我们还给出了在完全二叉树、FFT和混洗交换网络上对任意二叉树的有效模拟。人们很自然地会问，是否有任何稀疏网络可以有效地模拟每棵二叉树。有些令人惊讶的是，我们在N个节点上构造了一个泛有界度网络，其中每个N节点的二叉树都是一个生成树。换句话说，每一棵二叉树都可以在我们的通用网络上模拟，而不需要任何开销。这改进了以前关于树的全能图的大小的界限。
Universal networks offer the advantage that they can execute programs written for simpler architectures without significant run-time overhead. In this paper we investigate simulations of tree machines; the fact that divide-and-conquer algorithms are programmed naturally on trees motivates our investigation. Among various proposals for parallel computing the boolean hypercube has emerged as a particularly versatile network. It is well known that programs for multidimensional grid machines, for example, can be executed on a hypercube with no communications overhead by embedding the grid as a subgraph of the hypercube. Our first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. We also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks. It is natural to ask if any sparse network can simulate every binary tree efficiently. Somewhat surprisingly, we construct a universal bounded-degree network on N nodes for which every N node binary tree is a spanning tree. In other words, every binary tree can be simulated on our universal network with no overhead. This improves previous bounds on the sizes of universal graphs for trees.