A Systematic Design of Fault Tolerant Systolic Arrays Based on Triple Modular Redundancy in Time-Processor Space

Mineo KANEKO  Hiroyuki MIYAUCHI  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.12   pp.1676-1689
Publication Date: 1996/12/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing
VLSI array processor,  systolic array,  fault tolerance,  communication link,  dependence graph,  

Full Text: PDF(1.1MB)>>
Buy this Article

A systematic procedure to configure faulttolerant systolic arrays based on Triplicated Triple Modular Redundancy is proposed. The design procedure consists of the triplication of the dependence graph which is formed from a target regular algorithm and the transformation onto physical time-processor domain. The resultant systolic arrays tolerate failures not only on processing elements but also on communication links. While it needs sophisticated connection scheme between processing elements to guarantee the fault-tolerance on communication links, the link complexity is possibly reduced by optimizing redundant operation scheme. Unconstrained and constrained link minimization problems are introduced, and the possibility and the constraints required for link complexity reduction are investigated.