Checksum schemes for fault tolerant systolic computing

112. R. P. Brent, F. T. Luk and C. J. Anfinson, Checksum schemes for fault tolerant systolic computing, Mathematics in Signal Processing II (edited by J. G. McWhirter), Clarendon Press, Oxford, 1990, 791-804.

Abstract: dvi (3K), pdf (75K), ps (27K).

Paper: pdf (852K).


The weighted checksum scheme has been proposed as a low-cost fault tolerant procedure for parallel matrix computations.  To guarantee multiple error detection and correction, the chosen weight vectors must satisfy some very specific linear independence properties. We will provide a theoretical framework for those properties, and prove that for a distance d + 1 scheme, if a maximum of [d/2] errors ensue, the exact number of errors can be determined.  We will derive a procedure for correcting the errors.  Previous weight generating methods that fulfil the independence criteria have troubles with numerical overflow. We will present a new scheme that generates weight vectors to meet the independence requirements and to avoid the difficulties with overflow.


For related papers, see [109, 114].

Go to next publication

Return to Richard Brent's index page