SYNTHESIS OF ALGORITHM-BASED FAULT-TOLERANT SYSTEMS FOR DEPENDENCE GRAPHS

Algorithm-Based Fault Tolerance (ABFT) is a scheme to improve the reli ability of parallel architectures used for computation-intensive tasks . The exact implementation of an ABFT scheme is algorithm-dependent. A BFT systems have very low overhead compared to other fault tolerance s chemes with similar benefits. Few results are available in the area of general synthesis of ABFT systems. A two-stage approach to the synthe sis of ABFT systems is proposed. In the first stage a system-level cod e is chosen to encode the data used in the algorithm. In the second st age the optimal architecture to implement the scheme is chosen using d ependence graphs. Dependence graphs are a graph-theoretic form of algo rithm representation. We demonstrate that not all architectures are id eal for the implementation of a particular ABFT scheme. We propose new measures to characterize the fault tolerance capability of a system t o better exploit the proposed synthesis method. Dependence graphs can also be used for the synthesis of ABFT schemes for non-linear problems . An example of a fault-tolerant median filter is provided to illustra te their utility for such problems.