REAL-NUMBER CODES FOR FAULT-TOLERANT MATRIX OPERATIONS ON PROCESSOR ARRAYS

Various checksum codes have been suggested for fault-tolerant matrix computations on processor arrays. Use of these codes is limited due to inflexibility of the encoding schemes and also due to potential numerical problems. Numerical errors may also be misconstrued as errors due to physical faults in the system. In this paper, we develop a generalization of the existing schemes as a possible solution to these shortcomings. We prove that linearity is a necessary and sufficient condition for codes used for fault-tolerant matrix operations such as matrix addition, multiplication, transposition, and LU decomposition. We also prove that for every linear code defined over a finite field, there exists a corresponding linear real-number code with similar error detecting and correcting capabilities. Encoding schemes are given for some of the example codes which fall under the general set of real-number codes. With the help of experiments, we derive a rule of thumb for the selection of a particular code for a given application. The performance overhead of fault tolerance schemes using the generalized encoding schemes is shown to be very low, and this was substantiated through simulation experiments. Since the overall error in the code will also depend on the method of implementation of the coding scheme, we also suggest the use of specific algorithms and special hardware realizations for the check element computation. © 1990 IEEE