Efficient fault tolerance approaches for parallel architectures solving linear and nonlinear algorithms

LSI-based processor arrays have been widely used for computation intensive applications such as matrix computations, FFT, and graph problems. In these systems, fault tolerance is a primary concern because even a single fault can cause a catastrophic outcome. In this dissertation, an efficient algorithm-based fault tolerance design employing a new checksum coding technique is first examined to solve matrix computations. Comparisons with other schemes reveal that the proposed scheme is very efficient in terms of time and hardware overhead.;Two new concurrent error detection schemes for FFT networks are then proposed. The first scheme calculating the checksums at the input and output site allows high error coverage with low false alarm rate by applying the linear weight factors to the checksums. Hardware overhead is relatively small and errors can be quickly detected. In the second scheme which computes the checksums in each stage, multiple errors can be efficiently and promptly detected. Fault coverage is almost 100% for any size FFT networks with very small hardware overhead. Efficient error location and correction schemes for FFT networks are also proposed, which can be used along with any error detection schemes employing the checksum approaches. A faulty component can be located at an additional try with smaller number of comparisons than existing designs. An error can also be corrected at a small modification of basic modules with an additional try.;A generalized fault tolerance approach for two-dimensional processor arrays is then presented. The proposed approach can effectively tolerate multiple faults in the array solving linear or nonlinear algorithms by properly scheduling the flow of data and employing the majority voting approach. Most earlier fault tolerance designs are restricted to the array solving linear algorithms. Hardware overhead is almost zero in the approach compared to nonfault tolerant designs, while small time overhead much less than 100% is needed. The number of I/O links is also reduced to about...