The Algorithm-Based Fault Tolerance (ABFT) approach transforms a system that does not tolerate a specific type of faults, called the fault-intolerant system, to a system that provides a specific level of fault tolerance, namely recovery. The ABFT philosophy leads directly to a model from which error correction can be developed. By employing an ABFT scheme with effective convolutional code, the design allows high throughput as well as high fault coverage. The ABFT techniques that detect errors rely on the comparison of parity values computed in two ways. The parallel processing of input parity values produce output parity values comparable with parity values regenerated from the original processed outputs and can apply convolutional codes for the redundancy. This method is a new approach to concurrent error correction in fault-tolerant computing systems. This chapter proposes a novel computing paradigm to provide fault tolerance for numerical algorithms. The authors also present, implement, and evaluate early detection in ABFT.
TopIntroduction
ABFT, proposed by Huang and Abraham (1984), is a fault tolerance scheme that uses Concurrent Error Detection (techniques at a functional level). System level applications of ABFT techniques have also been investigated (Acree, Ullah, Karia, Rahmeh, and Abraham, 1993; Banerjee, Rahmeh, Stunkel, Nair, Roy, and Abraham, 1990). These techniques assume a general fault model which allows any single module in the system to be faulty (Huang, and Abraham, 1984). ABFT is widely applicable and it has proved its cost-effectiveness especially when applied to array processor (Jou, and Abraham, 1986). Fault detection and diagnosis are integral parts of any fault tolerance scheme. There are two ways to detect faults:
- 1.
By off-line checking.
- 2.
By concurrent checking.
In an off-line checking scheme, the process is checked for its correctness while it is not performing any useful computation. This approach has the beneficial that the performance of the computer will be unaffected by the checking operation; however, this kind of checking can detect only permanent faults. Transient faults, which constitute 76-81% of faults in a Digital system (Jou, and Abraham, 1986), will not be detected by off-line checks. So that detects transient faults, concurrent error detection schemes such as duplication and comparisons have been suggested. It has been observed that ABFT techniques are very cost effective when applied to process elements. It may be noted, however, that the application of ABFT techniques is not limited to multi-process systems; they are also applicable to algorithms running on single process, probably with less efficiency. An algorithm executing on a multiple process system is specified as a sequence of operations performed on a set of processes in some discrete time steps.
TopCharacteristics Of Abft
ABFT technique is distinctive by three characteristics:
- 1.
Encoding the input sequence.
- 2.
Plan again of the algorithm to act on the encoded input sequence.
- 3.
Distribution of the redundant computational steps among the individual computational units in order to adventure maximum parallelism.