About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
Embedding complete binary trees in faulty hypercubes
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 (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.