Embedding complete binary trees in faulty hypercubes
- 9 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 112-119
- https://doi.org/10.1109/spdp.1991.218290
Abstract
This paper studies the ability of the hypercube to implement tree-structured algorithms in the presence of faults. The hypercube is able to implement a wide range of algorithms efficiently, and the authors' selection of tree computations is motivated by the fact that many parallel algorithms, including broadcasting, parallel prefix, and other divide-and-conquer algorithms, have a natural tree structure. The authors' primary result is that there exists a function f(n) such that f(n)= Omega (n/sup 2//log n) and any n-dimensional hypercube with f(n) faulty nodes and/or edges contains as a subgraph a fault-free complete binary tree with 2/sup n-1/-1 nodes. Previously, the hypercube was known to contain such a tree only when there were fewer than 2n faults. In addition, they prove an upper bound on the number of faults that can be avoided when a natural class of embedding techniques is used.Keywords
This publication has 14 references indexed in Scilit:
- Asymptotically tight bounds for computing with faulty arrays of processorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fault tolerant sorting networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Running algorithms efficiently on faulty hypercubesPublished by Association for Computing Machinery (ACM) ,1990
- Fast computation using faulty hypercubesPublished by Association for Computing Machinery (ACM) ,1989
- Expanders might be practical: fast algorithms for routing around faults on multibutterfliesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- How robust is the n-cube?Information and Computation, 1988
- Take a walk, grow a treePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- A new look at fault-tolerant network routingInformation and Computation, 1987
- Reconfiguring a hypercube in the presence of faultsPublished by Association for Computing Machinery (ACM) ,1987
- Optimal simulations of tree machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986