A graph-theoretic approach to minimizing the number of dangerous processors in fault-tolerant mesh-connected processor arrays

First, we give a graph-theoretic formalization for the spare assignment pro blems for two cases of reconfiguring N x N mesh-connected processor arrays with spares on a diagonal line in the array or two orthogonal lines at the edges of the array. Second, we discuss the problems for minimizing the numb ers of "dangerous processors" for the cases. Here, a dangerous processor is a nonfaulty one for which there remains no spare processor to be assigned if it becomes faulty, without modifying the spare assignments to other faul ty processors. The problem for the latter case, originally presented by Mel hem [1], [2], has already been discussed and solved by the O(N-2) algorithm in [3], but it's procedure is very complicated. Using the above graph-theo retic formalization, we give efficient plain algorithms for minimizing the numbers of dangerous processors by which the problems for both the cases ca n be solved in O(N) time.