Spare Processor Assignment for Reconfiguration of Fault-Tolerant Arrays

Chang CHEN  An FENG  Yoshihiro TAKADA  Tohru KIKUNO  Koji TORII  

IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.8   pp.1247-1256
Publication Date: 1990/08/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on Fault-Tolerant Systems)

Full Text: PDF(834.4KB)>>
Buy this Article

To provide the processor arrays with adequate fault-tolerant capabilities, a number of spare or redundant processors are prepared within the arrays. For such processor arrays, reconfiguration should be executed to bypass faulty processors. Concerning reconfiguration of processor arrays, Melhem presented a minimization problem (called the SPA problem). The SPA problem is to find an assignment of spare processors to faulty processors that minimizes the number of dangerous processors. Here, the dangerous processors are processors, for which there remains no longer any spare processor to be assigned when one more faults occur. In this paper, we present a more rigorous definition of the SPA problem, in which input parameters are n2 ordinary processors, 2n spare processors and m (mn2) faulty processors, and the output is an optimal assignment of spare processors to faulty processors, in the sense that the number of dangerous processors is minimum. Then, we develop an efficient algorithm based on the necessary and sufficient conditions, which allows highly efficient computation of spare processor assignment. The worstcase time complexity of the proposed algorithm is O(n2).