Accurate Residues for Floating-Point Debugging

Floating-point arithmetic is error-prone and unintuitive. Floating-point debuggers instrument programs to monitor floating-point arithmetic at run time and flag numerical issues. To do so, they estimate residues-the difference between actual floating-point and ideal real values-for every floating-point value in the program. A large literature has explored various approaches for computing these residues accurately (leading to few false reports, i.e., false positives and false negatives) and efficiently (leading to low overhead over uninstrumented execution). Unfortunately, the most efficient methods, based on "error-free transformations", have a high rate of false positives, while the most accurate methods, based on high-precision arithmetic, are very slow. This paper builds on error-free-transformations-based approaches and aims to improve their accuracy while preserving efficiency.

To more accurately compute residues, this paper divides residue computation into two steps-rounding error computation and residue function evaluation-and shows how to perform each step accurately via careful improvements to the current state of the art. We evaluate on 44 large scientific computing workloads, focusing on the 14 benchmarks where prior tools produce false reports: our approach eliminates false reports on 10 benchmarks and substantially reduces them on the remaining 3 benchmarks.

Moreover, we find that more complex numerical issues, such as those found in numerical analysis textbooks, require additional care, because floating-point debuggers suffer from absorption, in which two different machine-precision residues cannot both be computed accurately in a single execution. To address absorption, this paper introduces residue override, which re-executes the program multiple times, computing different residues in different executions and assembling a final "patchwork" execution where all residues are accurately computed. We evaluate on 169 standard benchmarks drawn from numerical analysis papers and textbooks, requiring only 3.6 re-executions on average. Among 34 benchmarks with false reports in the initial run, residue override is triggered on 29 of them and reduces false reports on 25 of them, averaging 7.1 re-executions.