Fault-tolerant embeddings in generalized hypercubes

A generic software-based fault-tolerant technique is presented in this paper. We present an algorithm for reconfiguration of parallel programs on hypercubic networks with some faulty processors. We show that our reconfiguration approach would retain features of the original parallel programs, written for fault-free network, such as the load cost and the dilation cost to the extent possible. The computational complexity of this algorithm is bounded above by a polynomial in size of cube. The graph theoretic properties of hypercubic networks are used to change the embedding of the parallel program, such that idle processors that is, processors not used by fault-free embedding, are used in place of faulty processors