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).
Abstract
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.
Comments
For related papers, see
[109,
114].
Go to next publication
Return to Richard Brent's index page