Floating Point Fault Tolerance with Backward Error Assertions

Daniel Boley; Gene H. Golub; Samy Makar; Nirmal Saxena; Edward J. McCluskey

doi:10.1109/12.364541

Floating Point Fault Tolerance with Backward Error Assertions

Daniel Boley, Gene H. Golub, Samy Makar, Nirmal Saxena, Edward J. McCluskey

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

This paper introduces an assertion scheme based on the backward error analysis for error detection in algorithms that solve dense systems of linear equations, Ax = b. Unlike previous methods, this Backward Error Assertion Model is specifically designed to operate in an environment of floating point arithmetic subject to round-off errors, and it can be easily instrumented in a Watchdog processor environment The complexity of verifying assertions is 0(n2), compared to the 0(n3) complexity of algorithms solving Ax = b. Unlike other proposed error detection methods, this assertion model does not require any encoding of the matrix A. Experimental results under various error models are presented to validate the effectiveness of this assertion scheme.

Original language	English (US)
Pages (from-to)	302-311
Number of pages	10
Journal	IEEE Transactions on Computers
Volume	44
Issue number	2
DOIs	https://doi.org/10.1109/12.364541
State	Published - Feb 1995

Bibliographical note

Funding Information:
Manuscript received November 29, 1993; revised April 21, 1994. This work was supported in part by the Hewlett-Packard Resident Fellowship, by the National Science Foundation under Grants MIP-8709128, CCR-8821078, and CCR-8813493, by the Army Research Office under Grant DAAL03-87-K-0095, and by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization administered through the Office of Naval Research under Contract “14-85-K-0600. The work of G. H. Golub was supported in part by the National Science Foundation under Grant NSF CCR-8821078. The work of E. J. McCluskey was supported in part by the Innovative Science and Technology Office of the Strategic Defense Initiative and administered through the Office of Naval Research under Contract N0001492-J-1782, and in part by the National Science Foundation under Grant MIP-9107760. The work of D. Boley was carried out while on leave at the Stanford University Computer Science Dept., whose hospitality is gratefully acknowledged.

Access

10.1109/12.364541

OpenUrl availability

Full text

Cite this

@article{ee36eaa046c644eeaf5777928f362ea2,

title = "Floating Point Fault Tolerance with Backward Error Assertions",

abstract = "This paper introduces an assertion scheme based on the backward error analysis for error detection in algorithms that solve dense systems of linear equations, Ax = b. Unlike previous methods, this Backward Error Assertion Model is specifically designed to operate in an environment of floating point arithmetic subject to round-off errors, and it can be easily instrumented in a Watchdog processor environment The complexity of verifying assertions is 0(n2), compared to the 0(n3) complexity of algorithms solving Ax = b. Unlike other proposed error detection methods, this assertion model does not require any encoding of the matrix A. Experimental results under various error models are presented to validate the effectiveness of this assertion scheme.",

author = "Daniel Boley and Golub, {Gene H.} and Samy Makar and Nirmal Saxena and McCluskey, {Edward J.}",

note = "Funding Information: Manuscript received November 29, 1993; revised April 21, 1994. This work was supported in part by the Hewlett-Packard Resident Fellowship, by the National Science Foundation under Grants MIP-8709128, CCR-8821078, and CCR-8813493, by the Army Research Office under Grant DAAL03-87-K-0095, and by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization administered through the Office of Naval Research under Contract “14-85-K-0600. The work of G. H. Golub was supported in part by the National Science Foundation under Grant NSF CCR-8821078. The work of E. J. McCluskey was supported in part by the Innovative Science and Technology Office of the Strategic Defense Initiative and administered through the Office of Naval Research under Contract N0001492-J-1782, and in part by the National Science Foundation under Grant MIP-9107760. The work of D. Boley was carried out while on leave at the Stanford University Computer Science Dept., whose hospitality is gratefully acknowledged.",

year = "1995",

month = feb,

doi = "10.1109/12.364541",

language = "English (US)",

volume = "44",

pages = "302--311",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "2",

}

TY - JOUR

T1 - Floating Point Fault Tolerance with Backward Error Assertions

AU - Boley, Daniel

AU - Golub, Gene H.

AU - Makar, Samy

AU - Saxena, Nirmal

AU - McCluskey, Edward J.

N1 - Funding Information: Manuscript received November 29, 1993; revised April 21, 1994. This work was supported in part by the Hewlett-Packard Resident Fellowship, by the National Science Foundation under Grants MIP-8709128, CCR-8821078, and CCR-8813493, by the Army Research Office under Grant DAAL03-87-K-0095, and by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization administered through the Office of Naval Research under Contract “14-85-K-0600. The work of G. H. Golub was supported in part by the National Science Foundation under Grant NSF CCR-8821078. The work of E. J. McCluskey was supported in part by the Innovative Science and Technology Office of the Strategic Defense Initiative and administered through the Office of Naval Research under Contract N0001492-J-1782, and in part by the National Science Foundation under Grant MIP-9107760. The work of D. Boley was carried out while on leave at the Stanford University Computer Science Dept., whose hospitality is gratefully acknowledged.

PY - 1995/2

Y1 - 1995/2

N2 - This paper introduces an assertion scheme based on the backward error analysis for error detection in algorithms that solve dense systems of linear equations, Ax = b. Unlike previous methods, this Backward Error Assertion Model is specifically designed to operate in an environment of floating point arithmetic subject to round-off errors, and it can be easily instrumented in a Watchdog processor environment The complexity of verifying assertions is 0(n2), compared to the 0(n3) complexity of algorithms solving Ax = b. Unlike other proposed error detection methods, this assertion model does not require any encoding of the matrix A. Experimental results under various error models are presented to validate the effectiveness of this assertion scheme.

AB - This paper introduces an assertion scheme based on the backward error analysis for error detection in algorithms that solve dense systems of linear equations, Ax = b. Unlike previous methods, this Backward Error Assertion Model is specifically designed to operate in an environment of floating point arithmetic subject to round-off errors, and it can be easily instrumented in a Watchdog processor environment The complexity of verifying assertions is 0(n2), compared to the 0(n3) complexity of algorithms solving Ax = b. Unlike other proposed error detection methods, this assertion model does not require any encoding of the matrix A. Experimental results under various error models are presented to validate the effectiveness of this assertion scheme.

UR - http://www.scopus.com/inward/record.url?scp=0029254186&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029254186&partnerID=8YFLogxK

U2 - 10.1109/12.364541

DO - 10.1109/12.364541

M3 - Article

AN - SCOPUS:0029254186

SN - 0018-9340

VL - 44

SP - 302

EP - 311

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 2

ER -

Floating Point Fault Tolerance with Backward Error Assertions

Abstract

Bibliographical note

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this