PaperlayerView exact revision on arXiv

Source-linked AI summary

Silent error detection in numerical time-stepping schemes

Austin R. Benson, Sven Schmit, Robert Schreiber

arXiv:1312.2674v1math.NAcs.MScs.NA

TL;DR

Silent errors can leave time-dependent computations on a permanently erroneous track. This paper compares base and auxiliary numerical schemes at each step to detect them. In simulations, it flagged nearly all LTE-normalized errors above three while keeping the overall false positive rate below 10%, and it was most successful on errors with the greatest solution impact.

  • Problem

    Silent errors can perturb application state and put a time-dependent initial-value solution on a permanently erroneous track.

    Source: §1.1 · p. 1, §1.2 · p. 2

  • Method

    The approach compares base and auxiliary computations at every step, using their output difference as an error signal.

    Source: §1.3 · p. 2, §2 · p. 3

  • Results

    Nearly all LTE-normalized errors above three were flagged, with an overall false positive rate below 10% and often 0%.

    Source: §6 · p. 21

  • Takeaways & Limitations

    The detector is most successful on errors with the largest impact on the solution, measured by LTE-normalized error.

    Source: §6 · p. 21

    Detectors local in both space and time remain a possible extension of the approach.

    Source: §6 · p. 22

Abstract

from arXiv · show

Errors due to hardware or low level software problems, if detected, can be fixed by various schemes, such as recomputation from a checkpoint. Silent errors are errors in application state that have escaped low-level error detection. At extreme scale, where machines can perform astronomically many operations per second, silent errors threaten the validity of computed results. We propose a new paradigm for detecting silent errors at the application level. Our central idea is to frequently compare computed values to those provided by a cheap checking computation, and to build error detectors based on the difference between the two output sequences. Numerical analysis provides us with usable checking computations for the solution of initial-value problems in ODEs and PDEs, arguably the most common problems in computational science. Here, we provide, optimize, and test methods based on Runge-Kutta and linear multistep methods for ODEs, and on implicit and explicit finite difference schemes for PDEs. We take the heat equation and Navier-Stokes equations as examples. In tests with artificially injected errors, this approach effectively detects almost all meaningful errors, without significant slowdown.

1 Silent errors and checking schemes

Silent errors threaten time-dependent computations because perturbations can leave the solution on a permanently erroneous track. The paper proposes low-cost, step-by-step comparisons between base and auxiliary schemes and tests them with injected errors.

1.1 Silent errors are worrisome

  • Silent errors can arise from hardware or software problems and threaten computed results at extreme scale.The paper notes that a perturbation to application state may lead to a bad final solution.Source: §1.1 · p. 1

1.2 Algorithmic responses to silent errors

  • Perturbations to a computed solution in an initial-value problem can put it on a permanently erroneous track, motivating detection as errors occur.By contrast, residual checks are described as useful when the data defining an equation are assumed incorruptible.Source: §1.2 · p. 2
  • Prior error-monitoring approaches include checksums and algorithmic invariants, but they are useful yet fallible rather than comprehensive.The paper also notes that algorithmic self-correction does not address every possible corruption.Source: §1.2 · p. 2

1.3 Our approach

  • The approach detects errors by comparing a base time-stepping scheme with an auxiliary checking scheme at every step, using the same input data.Unlike straightforward duplication, the approach is cheaper and can detect problems duplication cannot.Source: §1.3 · p. 2
  • The paper extends numerical error-estimation schemes used for ODE step-size control and PDE mesh adaptation to detecting errors caused by a misbehaving computing system.Suitable checking schemes are available for common initial-value problems in ODEs and PDEs.Source: §1.3 · p. 2
  • Injected-error experiments show that the scheme catches errors with significant impact on the solution.The paper quantifies impact and reports results in subsequent numerical experiments.Source: §1.3 · p. 2

2 Outline of general method

The method compares an auxiliary computation with a base computation and judges the resulting difference sequence for anomalies. It uses an inexpensive, distinct checking scheme, balances false positives against missed errors, and proposes retry-based responses to flagged errors.

2 Outline of general method

  • At each iteration, the norm of the difference between auxiliary and base outputs estimates the current gap between the base result and an error-free solution.The checker should have accuracy comparable to or better than the base method while remaining fast; it need not be stable because it does not feed its own outputs forward.Source: §2 · p. 3

2.1 Choosing an auxiliary scheme

  • Repeating the base computation as the checker costs as much and can reproduce identical wrong results when both use corrupted input or share a repeatable fault.A useful auxiliary scheme should reuse base computation where possible yet differ enough to disagree in the presence of errors.Source: §2.1 · p. 3
  • Embedded Runge-Kutta and paired linear multistep schemes provide distinct checks, while explicit auxiliaries can be effective and inexpensive alongside implicit base schemes.The paired multistep approach combines saved and new solution and derivative values in different ways.Source: §2.1 · p. 3

2.2 The detector

  • Because the error-free difference can vary by orders of magnitude, a hard threshold is ineffective; sudden changes in the difference sequence better indicate errors.Threshold selection trades false positives against false negatives, with the paper treating missed errors as worse than mildly annoying false alarms.Source: §2.2 · pp. 3–4

2.3 What to do if an error is flagged

  • After a flag, the proposed response is to redo steps from a trusted iteration and compare the retry with the original result.A retry with a significantly different result suggests an unreliable platform component; the same retry result leaves several causes ambiguous.Source: §2.3 · p. 5
  • The authors propose using memory checks or smaller time steps to help distinguish corrupted inputs, persistent component errors, and flags caused by local problem difficulty.When input corruption is ruled out, repeated step-size reductions may resolve a local-difficulty flag; a persistent flag suggests a component error.Source: §2.3 · p. 5

3 Applications

For ODEs and PDEs, the paper pairs a base time-stepping scheme with a checking scheme and uses their difference to identify errors. It describes Runge-Kutta, linear multistep, finite-difference, and extrapolation choices for constructing these pairs.

3.1 ODE solvers

  • Embedded Runge-Kutta pairs let a cheaper auxiliary scheme check the base solution, and the van der Pol example shows an injected error producing a difference jump.The midpoint and Euler schemes form an embedded pair; RKF45 is identified as a common accurate scheme.Source: §3.1 · p. 6, Figure 1 · p. 6
  • For an order-p Adams-Bashforth base method, an order-(p−1) auxiliary reuses data without extra storage or function evaluations.The paper also considers same-order interpolating multistep auxiliaries, which require storing prior solutions.Source: §3.1 · p. 6
  • With an implicit Adams-Moulton base, an explicit Adams-Bashforth auxiliary avoids a second costly implicit solve while reusing computed values.The paper notes that this auxiliary does not suffer from the instability of explicit methods on stiff ODEs because it uses values and function evaluations already computed by the implicit base.Source: §3.1 · p. 7

3.2 PDE solvers

  • For PDEs, backward and forward Euler pair an implicit linear solve with a cheaper matrix-vector product, while Richardson can match Crank–Nicolson's time accuracy.The Richardson scheme reuses Crank–Nicolson computations but requires solutions from two previous time steps.Source: §3.2 · p. 8
  • In the heat-equation example, an injected error at iteration 120 produces a spike in the sequence of differences between the schemes.The paper examines Richardson/Crank–Nicolson and forward/backward Euler pairs for error detection.Source: Figure 2 · p. 7, §3.2 · p. 8

3.3 Extrapolation

  • When a related auxiliary scheme is not obvious, extrapolation provides a cheap option for error detection, though it is not useful as a basic solver.The paper uses extrapolation in the A/B scheme for the Navier-Stokes equations.Source: §3.3 · p. 8

4 Error detection

The detector tracks changes in the difference between base and auxiliary schemes using jump and variance indicators with adaptively tuned thresholds. Its reliability depends on predictable error-free differences; rapid solution changes can produce false positives.

4 Error detection

  • The detector uses the jump in the difference sequence and a change in its variance as indicators of possible errors.The window size is controlled by p, set to 10 in the experiments.Source: §4 · pp. 8–9
  • An error is flagged only when both indicators exceed their current thresholds, a strategy reported to improve sensitivity at a fixed false positive rate.The detector uses relatively large changes in the difference sequence rather than its magnitude because the scale of error-free variation can change.Source: §4 · pp. 8–9
  • Closed-loop threshold tuning raises thresholds when indicators exceed them and lowers them otherwise, keeping thresholds near typical values.The paper reports that this reduces false negatives without causing many false positives and that performance is not sensitive to the tested parameter choices.Source: §4 · p. 9

4.1 Discussion

  • The method assumes accurate base and auxiliary schemes and predictable difference behavior; rapid solution changes can trigger false positives.Such a flag may reflect underresolution rather than an error caused by an unstable platform.Source: §4.1 · p. 10
  • A flag can arrive one step after the faulty iteration, so the paper recommends restarting from two iterations earlier.The discussion also says more sophisticated time-series peak-detection algorithms are outside the paper's focus.Source: §4.1 · p. 10

5 Numerical experiments

The experiments inject faults into important computations or data and assess their effects using LTE-normalized error. Across ODE and PDE tests, large-impact errors were easier to detect, with low false-positive rates in the reported heat-equation and Navier–Stokes results.

5.1 Fault injection and LTE-normalized error

  • Faults were injected into function or source evaluations, linear-system right-hand sides, or previous solutions; LTE-normalized error relates their impact to local truncation error.The random multiplicative corruptions were chosen to avoid the readily flagged Infs and NaNs produced by bit flips.Source: §5.1 · pp. 10–11

5.2 Van der Pol equation

  • On Van der Pol, Adams-Bashforth detected many derivative faults one step late and stored-state faults effectively, while Runge-Kutta struggled with stored-state corruption.Higher-order RK45 and AB45 generally performed slightly better than RK23 and AB23.Source: §5.2 · pp. 11, 13

5.3 Heat Equation

  • Heat-equation trials covered three configurations and fault locations; the same corruption was more easily detected by R/CN than FE/BE, so R/CN used smaller injection variances.The configurations included source-term, implicit-solve right-hand-side, and previous-solution faults.Source: §5.3 · pp. 13, 18

5 Numerical experiments

  • Across heat-equation tests, large LTE-normalized errors were easier to detect, checking one step later often improved detection, false positives were at most 1.2%, and smaller time steps improved or maintained detection.For Navier–Stokes tests, large LTE-normalized errors were also easily detected and the false-positive rate was small.Source: §5.3 · p. 18, §5.6 · p. 21

5.4 Detection indicators for the heat equation

  • Using only relative jump raised the false-positive rate to 14%, and variance-only raised it to 2%; the combined indicators produced no false positives with only modest TPR changes for single indicators.Source: §5.4 · pp. 18–19

5.5 Tardy error detection with the heat equation

  • For source-term faults, FE/BE can detect an error one step late: backward Euler first produces a small difference, then forward Euler accepts the corrupted source for a full step.The infinity norm helps expose spatially localized spikes, but differences in component scales can make faults at low-difference locations harder to detect; examining differences locally in space and time is future work.Source: §5.5 · pp. 19–20

5.6 Incompressible Navier-Stokes equations

  • In the Navier–Stokes tests, the simple extrapolation auxiliary scheme detected large LTE-normalized errors, with a small false-positive rate.The tests used a projection method for driven-cavity flow and injected faults into either a previous velocity solution or a linear-system right-hand side.Source: §5.6 · pp. 20–21

6 Discussion

The scheme detects nearly all LTE-normalized errors above three while keeping overall false positives below 10%, with many cases producing none. The discussion identifies formal error analysis, fault characterization, and spatially local detection as areas for future work.

6 Discussion

  • Nearly all LTE-normalized errors above three are flagged, with an overall false positive rate below 10% and many cases at 0%.The detector is most successful on errors with the largest impact on the solution.Source: §6 · p. 21
  • Typical error bounds are too loose in their constants for practical fault-threshold guarantees, motivating more formal analysis.The authors seek to establish when a difference-sequence value above a computed threshold implies that a fault occurred.Source: §6 · p. 21
  • Identifying what caused a fault remains future work; checksums can reveal prior-solution corruption, but function-evaluation errors are harder to determine.Source: §6 · p. 21
  • A heat-equation source-term perturbation changes the solution locally, and the resulting delay can make spatial localization useful for improving detection and identifying the affected processor.The discussion connects processor identification to parallel solvers that assign spatial locations to different processors.Source: §6 · pp. 21–22
  • Detectors local in both space and time are proposed as a possible extension that may improve sensitivity.Source: §6 · p. 22
Loading 1312.2674v1…