RECONFIGURATION OF RINGS AND MESHES IN FAULTY HYPERCUBES

In this paper we present schemes for reconfiguration of embedded task graphs in hypercubes. Previous results, which use either fault-toleran t embedding or an automorphism approach, can be expensive in terms of either the required number of spare nodes or reconfiguration time. Usi ng the free dimension concept, we combine the above two approaches in our schemes which can tolerate about n faulty nodes under the worst ca se while keeping task migration time small. With expansion-2 initial e mbedding, three distributed reconfiguration schemes are presented in t his paper. The first scheme, applied to chains and rings, can tolerate any f less-than-or-equal-to n - 2 faulty nodes in an n-dimensional hy percube. The second and third schemes are applied to meshes or tori. F or a mesh or torus of size 2m1 ... * 2md, the second scheme can tole rate any f less-than-or-equal-to m(i) - 1 faulty nodes, where mi is th e largest direction of the mesh and n = m1 + ... + m(d) + 1. By embedd ing two copies of meshes or tori in cube, the third scheme can tolerat e any f less-than-or-equal-to n - 1 faulty nodes with the dilation of embedding after reconfiguration degraded to 2. The third scheme is qui te general and can be applied to any task graph. (C) 1994 Academic Pre ss, Inc.