A Graph-Theoretic Approach to Minimizing the Number of Dangerous Processors in Fault-Tolerant Mesh-Connected Processor Arrays

Itsuo TAKANAMI

Summary :

First, we give a graph-theoretic formalization for the spare assignment problems for two cases of reconfiguring NN 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 numbers 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 faulty processors. The problem for the latter case, originally presented by Melhem, has already been discussed and solved by the O(N²) algorithm in [3], but it's procedure is very complicated. Using the above graph-theoretic formalization, we give efficient plain algorithms for minimizing the numbers of dangerous processors by which the problems for both the cases can be solved in O(N) time.

• Publication: IEICE TRANSACTIONS on Information Vol.E84-D No.11 pp.1462-1470
• Publication Date: 2001/11/01
• Type of Manuscript: Special Section PAPER (Special Issue on Function Integrated Information Systems)

Authors

Itsuo TAKANAMI

Keyword

fault tolerance,  reconfiguration algorithm,  dangerous processor,  mesh-connected processor array,  graph-theoretic approach