Reconfiguration Algorithm for Modular Redundant Linear Array

Chang CHEN  An FENG  Yoshiaki KAKUDA  Tohru KIKUNO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.2   pp.210-218
Publication Date: 1993/02/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing
Keyword: 
fault tolerant computing,  systolic array,  N-modular redundancy,  reconfigurable modular redundant linear array,  reconfiguration algorithm,  

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




Summary: 
A typical fault-tolerance technique of systolic arrays is to include redundant processors and links so that the array is reconfigurable when some processors fail. Another typical technique is to implement each processor by a majority voter and N (N3) copies of processors so that the faults of up to N-2 copies of processors can be masked without reconfiguration. This paper proposes a systolic linear array called reconfigurable modular redundant linear array (RMA) that combines these techniques with N4. When up to 2 copies of each processor fail in RMA, the faults can be masked without reconfiguration. When some voters or more than 2 copies of a processor fail, RMA can be reconfigured by specifying a new switch pattern. In order to perform reconfiguration efficiently, we present a reconfiguration algorithm with time complexity O (n), where n is the number of processors in RMA.