VLSI-based processor arrays have been widely used for computation intensive applications such as matrix and graph algorithms. Algorithm-based fault tolerance designs employing various encoding/decoding schemes have been proposed for such systems to effectively tolerate operation time fault. In this paper, we propose an efficient algorithm-based fault tolerance design using the weighted data-check relationship, where the checks are obtained from the weighted data. The relationship is systematically defined as a new (n, k, N/sub w/) Hamming checksum code, where n is the size of the code word, k is the number of information elements in the code word, and N/sub w/ is the number of weights employed, respectively. The proposed design with various weights is evaluated in terms of time and hardware overhead as well as overflow probability and round-off error. Two different schemes employing the (n, k, 2) and (n, k, 3) Hamming checksum code are illustrated using important matrix computations. Comparison with other schemes reveals that the (n, k, 3) Hamming checksum scheme is very efficient, while the hardware overhead is small.

In this brief contribution a new algorithm-based concurrent error detection scheme employing the checksum approach is proposed for FFT networks. Our design allows high error coverage with low false alarm rate by applying the linear weight factors to the checksums. Due to the simplicity, the hardware overhead is relatively small and errors can be quickly detected. The design is also shown to be easily expanded for multidimensional FFT networks.>

A scheme is proposed by which nonlinear graph problems can be efficiently solved using processor arrays even in the presence of multiple faults. The fault tolerance capability is achieved using the majority voting approach, and virtually no extra hardware overhead is necessary by maximizing the utilization of the processing elements (PEs). In addition to this, the proposed scheme also allows a significant reduction in the size of the array such that a [3N/5]/spl times/N processor array is enough for processing an N/spl times/N input data for shortest path problem (SPP). Computation time of the proposed design is bound to 9N-2 for SPP, while it is 5N-4 for non-fault tolerant designs.>

Fault tolerance has been one of the major issues for the VLSI based FFT networks. In this paper, two efficient approaches for concurrent error location and correction of FFT networks are proposed. Using our approach, a faulty component can be located at an additional try followed by log/sub 2/m comparisons of m corrupted outputs. An error can also be corrected, once it is detected, at a small modification of basic module with an additional try. Moreover, our approaches are general in the sense that they can be implemented with any concurrent error detection scheme employing a checksum approach for FFT networks.>