CHANNEL MULTIPLEXING IN FAULT-TOLERANT MODULAR MULTIPROCESSORS

A systematic approach to the design of fault-tolerant multiprocessors is described in this paper. This design approach utilizes the concept of multiplexing different channels of communication links to reconfigu re fault-tolerant systems in the presence of faults. It is a simple ap proach which can be applied to different modular architectures and can implement different spare allocation strategies. In this paper, we de rive the theoretical bounds of the channel requirement per link to rec onfigure the system properly and utilize all the available spare nodes . For some links, this bound is as high as 2m, where m is the degree o f a node. However, it is shown that a constant number of channels per link allows the system to be reconfigured properly and to utilize all the available spare nodes almost 100% of the time. We apply this appro ach to the construction of fault-tolerant binary trees and fault-toler ant binary hypercubes. (C) 1995 Academic Press, Inc.