Free dimensions-an effective approach to achieving fault tolerance in hypercube
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 170-177
- https://doi.org/10.1109/ftcs.1992.243603
Abstract
In the n-dimensional hypercube, Q/sub n/, for large n, faults can occur with relatively high probability. How to use the inherent redundancy present in the hypercube to obtain fault tolerance is discussed, along with computing in faulty hypercubes. The authors study the fault tolerance independently present in hypercubes by defining and using the concept of free dimensions. Briefly, in Q/sub n/, a dimension is said to be free if no pair of nodes across the dimension link are both faulty. Efficient algorithms are presented for finding free dimensions, given a set of faulty nodes, and it is shown that at least n-f+1 free dimensions exist with f<or=n faulty nodes. Free dimensions can be used to partition Q/sub n/ into subcubes such that each subcube contains at most one fault. Such a partitioning helps in achieving fault tolerance via emulation, embedding, and reconfiguration. It also helps in designing efficient routing and broadcasting algorithms in faulty hypercubes.Keywords
This publication has 16 references indexed in Scilit:
- An automorphic approach to the design of fault-tolerant multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Embedding and reconfiguration of binary trees in faulty hypercubesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Optimal broadcasting in faulty hypercubesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Running algorithms efficiently on faulty hypercubes (extended abstract)ACM SIGARCH Computer Architecture News, 1991
- How robust is the n-cube?Information and Computation, 1988
- Routing and broadcasting in faulty hypercube computersPublished by Association for Computing Machinery (ACM) ,1988
- The iPSC/2 direct-connect communications technologyPublished by Association for Computing Machinery (ACM) ,1988
- A survey of the theory of hypercube graphsComputers & Mathematics with Applications, 1988
- Reconfiguring a hypercube in the presence of faultsPublished by Association for Computing Machinery (ACM) ,1987
- Optimal BPC Permutations on a Cube Connected SIMD ComputerIEEE Transactions on Computers, 1982