For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Spare Processor Assignment for Reconfiguration of Fault-Tolerant Arrays
Chang CHEN An FENG Yoshihiro TAKADA Tohru KIKUNO Koji TORII
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/08/25
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on Fault-Tolerant Systems)
Full Text: PDF(834.4KB)>>
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).