| Summary: | Abstract: "The problem of tolerating faulty processors in hypercubes has been studied by many researchers, either by using spares or by reconfiguration. In this paper, we present two algorithms for reconfiguration of faulty hypercubes using spanning trees to achieve communication between the unfaulty processors. The first algorithm uses the completely unbalanced spanning tree (CUST), and the second one uses the balanced spanning tree (BST). Both algorithms use, at most, one used link and one unused link for every reconstructed path in the reconfigured hypercube. These reconstruction algorithms can reconfigure around any single fault in O(1) reconfiguration time with no dilation and will increase the congestion of a link by, at most, one. Both algorithms are optimal, in terms of the reconfiguration time, and can be used for reconfiguration of spanning trees in a hypercube in the presence of node failures. Simulation results for both algorithms under multiple faults also are presented. Results show that the algorithms provide close to 100% fault coverage of double and triple faults for hypercubes having a dimension of 10 or more. Fault coverage and congestion results for up to 60 faults having different cube sizes are presented."
|
|---|