Structural fault tolerance in VLSI-based systems

A system is structurally fault-tolerant (SFT) if it preserves a fault-free subsystem of a pre-determined interconnection structure when faults appear. We present a systematic approach to designing SFT VLSI-based systems that use shared buses as the main communication mechanism. To represent the target systems, we introduce a processor-bus-link (PBL) graph in which processing elements (PEs) and buses are both modeled as nodes. PE and bus faults correspond to the removal of nodes from the PBL graph. The node covering concept and the minimum-weight spanning arborescence algorithm are then applied to the design of SFT systems that can tolerate both PE and bus faults. The designs obtained have fewer spare communication ports than prior designs, no critical single point of failure, and simple circuitry for reconfiguration