OPTIMAL RECONFIGURATION ALGORITHMS FOR REAL-TIME FAULT-TOLERANT PROCESSOR ARRAYS

In this paper we consider the problem of reconfiguring processor array s subject to computational loads that alternate between two modes. A s trict mode is characterized by a heavy computational load and severe c onstraints on response time while a relaxed models characterized by a relatively light computational load and relaxed constraints on respons e time. In the strict mode, reconfiguration is performed by a distribu ted local algorithm in order to achieve fast recovery from faults. In the relaxed mode, a global reconfiguration algorithm is used to restor e the system to a state that maximizes the probability that future fau lts occurring in subsequent strict modes will be repairable. Several n ew results are given for this problem. Efficient reconfiguration algor ithms are described for a number of general classes of architectures. These general algorithms obviate the need for architecture-specific al gorithms for architectures in these classes. We show that it is unlike ly that similar algorithms can be obtained for related classes of arch itectures since the reconfiguration problem for these classes is NP-co mplete. Finally, a general approximation algorithm is described that c an be used for any architecture. Experimental results are given, sugge sting that our algorithms are very effective.