Reliable Data Routing for Spatial-Temporal TMR Multiprocessor Systems

Mineo KANEKO  

IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.12   pp.1790-1800
Publication Date: 2001/12/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerance
systolic array,  fault tolerance,  on-line error correction,  routing,  network architecture,  ,  

Full Text: PDF>>
Buy this Article

This paper treats the data routing problem for fault-tolerant systolic arrays based on Triple Modular Redundancy (TMR) in mixed spatial-temporal domain. The number of logical links required in TMR systolic array is basically 9 times larger than the one for corresponding non-fault-tolerant systolic array. The link sharing is a promising method for reducing the number of physical links, which may, however, degrade the fault tolerance of TMR system. This paper proposes several robust data-routing and resource-sharing (plural data transfers share a physical link, or a data transfer and a computational task share a PE as a relay node for the former and as a processor for the latter), by which certain classes of fault tolerant property will be guaranteed. A stage and a dominated set are introduced to characterize the features of routing/resource-sharing in TMR systems, and conditions on the dominated set and their resultant fault-tolerant properties are derived.