On-the-fly detection of instability problems in floating-point program execution

Tao Bao, Xiangyu ZhangOOPSLA 2013 · DOI

TL;DR

This paper introduces an "on-the-fly" technique to detect instability in floating-point computations. Instead of expensive high-precision calculations, it uses a lightweight bit-tagging system to track potential error inflations, allowing for efficient prediction of unstable executions and on-demand switching to higher precision.

What Problem Does This Paper Address?

Floating-point arithmetic, while essential for scientific and engineering computations, is inherently imprecise due to finite representation. This imprecision can lead to "instability problems" where small errors accumulate and magnify, causing program behavior to diverge from its mathematically intended outcome. These divergences can manifest as altered control flow, incorrect results, and even catastrophic failures (like the Patriot missile incident). Existing solutions, such as using higher-precision data types or complex error analysis, are often too computationally expensive for real-time or on-the-fly detection, making it difficult to guarantee stability without significant performance penalties.

Methods

The core of the proposed technique is an "on-the-fly" monitoring system that doesn't explicitly compute errors. Instead, it uses a single "inflation bit" to approximate whether a floating-point value has a significantly inflated relative error. This bit is propagated through operations, with specific rules designed to detect when an error inflates (e.g., during subtractions of nearly equal numbers) and when it's suppressed (e.g., when a small, erroneous value is added to a much larger, accurate one). The system tracks these inflation bits to critical "discrete factors" (like conditional branches or type casts). If an inflation bit reaches a discrete factor, the execution is flagged as potentially unstable. This allows for a practical approach: most executions run with standard precision, and only those flagged as potentially unstable are automatically restarted with higher precision.

Datasets

Not discussed in the paper. The evaluation uses standard benchmarks like SPEC CFP 2000, a biochemical data processing program (deisotope), and a motivating example program (poly).

Key Insights and Ideas

  • Instability is rare but inevitable: Floating-point instability bugs only affect a tiny fraction of the input domain, making it impractical to always use high-precision arithmetic.
  • Discrete factors are key: Instability problems often manifest as "discrete differences" at specific points in the program (e.g., a branch condition changing outcome), rather than just a gradual drift in output.
  • Error inflation vs. suppression: Not all error inflations lead to instability. The technique's novelty lies in tracking both inflation and suppression, focusing on errors that persist and reach critical decision points.
  • Bit-tagging for efficiency: Using a single bit to represent error inflation is a lightweight approximation that significantly reduces overhead compared to full error tracking or high-precision computation.

Key Results

  • The proposed technique can correctly predict that over 99.999996% of executions are stable with a specific threshold setting (τc=48).
  • It achieves an average slowdown of 7.91 times, which is about 14 times faster than state-of-the-art high-precision computation approaches.
  • While the technique flags 7.5-93 times more cases as potentially unstable than ground truth (due to its conservativeness), these flagged cases represent a minuscule fraction of the overall input domain (1.5E-11% to 3.3E-6%).
  • A traditional approach solely based on cancelled bit detection produced a large number of false warnings, whereas this method effectively filters them.

Limitations and Future Work

  • Threshold tuning: The technique relies on two thresholds (τc for inflation, τs for suppression). While a uniform configuration worked for the studied programs, its effectiveness for other programs is unknown.
  • Manual annotations: The current implementation requires manual annotation of "continuous cores" and "convergence test predicates" to suppress false warnings. The authors suggest language-level support or automated detection for these.
  • Approximation limitations: The single-bit approximation can lead to false negatives in rare cases where an error is suppressed due to the approximation itself (e.g., a very small value with a large relative error being treated as zero).
  • Future work: The authors plan to explore more sophisticated error modeling (more than one bit), automated annotation detection, and address pipeline behavior differences for instrumentation.

Summary updated

BibTeX
@inproceedings{bao2013fly,
  author = {Tao Bao and Xiangyu Zhang},
  title = {{On-the-fly detection of instability problems in floating-point program execution}},
  booktitle = {OOPSLA},
  year = {2013},
  doi = {10.1145/2509136.2509526},
}
Figure