EMBEDDING OF RINGS AND MESHES ONTO FAULTY HYPERCUBES USING FREE DIMENSIONS

Fault tolerance in hypercubes is achieved by exploiting inherent redun dancy and executing tasks on faulty hypercubes. We consider tasks that require linear chain, ring, mesh, and torus structure, which are quit e useful in parallel and pipeline computations. In this brief contribu tion, we assume the number of faults is on the order of the number of dimensions of the hypercube. Our techniques are based on a key concept called free dimension, which can be used to partition a cube into sub cubes such that each subcube contains, at most, one faulty node. Subgr aphs are embedded in each subcube and then merged to form the entire g raph. Using this approach, we obtain the following results in an n-dim ensional hypercube. A ring of length 2n-2f or a chain of length 2n-2f1 can be found, given any f < n-2 faulty nodes. The length of chains o r rings obtained is optimal (longest) in the worst case of fault distr ibution. A mesh or size at least (2m1-2f+1) 2m2 * ... * 2md, or a to rus of size at least (2m1-2f) 2m2 * ... * 2md, can be found when f l ess-than-or-equal-to m1-2, where n = m1 + m2 + ... + m(d), and m1 is t he largest direction of mesh. A mesh or torus of size at least (2m1-k) 2m2 * ... * 2md can be found with dilation 2 when 1 less-than-or-eq ual-to f less-than-or-equal-to n, where k = min (f,[2m1/2n-f+1]). The processor utilization of this embedding scheme is high. In particular, 1) for one-dimensional mesh or torus (linear chain or ring), the proc essor utilization of embedding is 100%; and 2) for 1 less-than-or-equa l-to f less-than-or-equal-to n - m1 + 1, a mesh or torus with the opti mal size of (2m1-1) + 2m2 + ... 2md is obtained. All the embeddings can be constructed in a distributed manner with time complexity O(n).