TY - GEN

T1 - Embedding complete binary trees in faulty hypercubes

AU - Wang, A.

AU - Cypher, R.

AU - Mayr, E.

N1 - Publisher Copyright:
© 1991 IEEE.

PY - 1991

Y1 - 1991

N2 - 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 (n2/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.

AB - 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 (n2/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.

UR - http://www.scopus.com/inward/record.url?scp=0001189162&partnerID=8YFLogxK

U2 - 10.1109/SPDP.1991.218290

DO - 10.1109/SPDP.1991.218290

M3 - Conference contribution

AN - SCOPUS:0001189162

T3 - Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing 1991

SP - 112

EP - 119

BT - Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing 1991

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 3rd IEEE Symposium on Parallel and Distributed Processing, PDPS 1991

Y2 - 2 December 1991 through 5 December 1991

ER -