A fault-tolerant mapping scheme for a configurable multiprocessor system

A fault-tolerant mapping scheme for a configurable multiprocessor system using multistage interconnection networks is presented. By adapting its interprocessor connections, the multiprocessor system can provide many regular topological configurations suitable for a variety of parallel computation applications. The configurability of the system is achieved by applying a set of configuration procedures to a linear address space of the system. The central idea behind the scheme is the use of two transformations to restore the linear address space in the presence of processor failures. The fault-tolerant mapping scheme is composed of three algorithms. The algorithms adaptively use the two transformations to handle three different types of faults: single faults, double faults, and triple or greater faults. It is shown that when there are a few processor failures, the algorithms can effectively achieve fault-free linear subspaces with graceful degradation.<>