Fault-tolerance embedding of rings into hypercubes

Abstract EN

The hypercube is emerging as one of the most effective and popular network architectures for large-scale parallel machines.

Hypercube based machines are becoming more popular due to many of their attractive features in parallel computing.

In the last decade as progress in VLSI has led to small size, low cost, and high performance processors.

It has become practical to build parallel computers containing a very large number of processors.

A main concern in the development of such a system is fault-tolerance.

Since the probability of one or more processor faulting in such systems is quite large, it is desirable to build some fault-tolerance features into them.

In this paper, we present divide-conquer techniques to embed rings into faulty hypercubes by wasting one no-fault processor for every faulty processor with up to 2n-3 faulty processors.