Reconfiguring a hypercube in the presence of faults

ABSTRACT

We consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. In particular, we describe algorithms for embedding an N/2-node hypercube in an N-node hypercube with faulty processors. Provided that the processors of the N-node hypercube are faulty with probability p < 1/2, and that the faults are independently distributed, we show that with high probability, adjacent cells in the N/2-node hypercube are mapped to functioning cells at distance 3 or less apart in the N-node hypercube. The algorithm is deterministic, easy to implement and runs in &Ogr;(log N) steps using only local control. We also describe ways to produce embeddings which allow for low delay simulations, as well as ways to use a faulty hypercube to efficiently simulate a completely functioning hypercube of the same size.

REFERENCES

• BS: B. Becker and H.U. Simon, "How Robust is the n-Cube?," Proc. 27'h Annu. IEEE Syrup. Foundations Comput. $ci., Oct. 1986, pp. 283- 291.
• BCLR: S. Bhatt, F. Chung, T. Leighton, and A. Rosenberg "Optimal Simulation of Tree Machines" Proc. 27~h Annu. IEEE Syrup. Foundations Cornput. $ci., Oct. 1986, pp. 274-282.
• DHSS: Danny Dolev , Joe Halpern , Barbara Simons , Ray Strong, A new look at fault tolerant network routing, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.526-535, December 1984 [doi>10.1145/800057.808723]
• EL: P. ErdSs and L. Lov~sz, "Problems and Results on 3-Chromatic Hypergraphs and ome Related Questions," Infinite and Finite Sets, North Holland, 1975.
• G: J. Greene, "Configuration of VLSI .Arrays ill the Presence of Defects," Ph.D. dissertation, Stanford Univ., Stanford, CA, 1983.
• GG: Jonathan W. Greene , Abbas El Gamal, Configuration of VLSI Arrays in the Presence of Defects, Journal of the ACM (JACM), v.31 n.4, p.694-717, Oct. 1984 [doi>10.1145/1634.2377]
• LL1: F.T. Leighton and C.E. Leiserson, "A Survey of Algorithms for Integrating Wafer-Scale Systolic Arrays,'' Wafer Scale Integration, edited by G. Saucier and J. Trilhe, IFIP, 1986, pp. 177- 195.
• LL2: F.T. Leighton and C.E. Leiserson, "Wafer-Scale Integration of Systolic Arrays," {EEE Transactions on Compuiers, Vol. C-34, No. 5, May 1985, pp. 448 - 461.
• S: J. Spencer, "Probabilistic Methods," Graphs and Combinatorics, 1, 1985, pp. 357- 382.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification