Herbie at PLDI’15

Automatically Improving Accuracy for Floating Point Expressions was published at PLDI’2015, where it won the Distinguished Paper Award.

Abstract

Scientific and engineering applications depend on floating point arithmetic to approximate real arithmetic. This approximation introduces rounding error, which can accumulate to produce unacceptable results. While the numerical methods literature provides techniques to mitigate rounding error, applying these techniques requires manually rearranging expressions and understanding the finer details of floating point arithmetic.

We introduce Herbie, a tool which automatically discovers the rewrites experts perform to improve accuracy. Herbie's heuristic search estimates and localizes rounding error using sampled points (rather than static error analysis), applies a database of rules to generate improvements, takes series expansions, and combines improvements for different input regions. We evaluated Herbie on examples from a classic numerical methods textbook, and found that Herbie was able to improve accuracy on each example, some by up to 60 bits, while imposing a median performance overhead of 40%. Colleagues in machine learning have used Herbie to significantly improve the results of a clustering algorithm, and a mathematical library has accepted two patches generated using Herbie.

Paper

The paper describes Herbie’s internals: how ground-truth exact values are found; how Herbie generates new programs that may improve accuracy; how different programs are combined into one. Several of the internal steps are technically interesting on their own, such as the localization heuristic, the rule rewriter, the simplification algorithm, and the regime inference algorithm. The paper also relates several experiments that tested Herbie’s accuracy improvement.

The paper is available in PDF format. TeX sources are available upon request.

Video Abstract

The PLDI organizers asked every paper to put together a minute-long video advertising the talk to conference attendees. This didn't make too much sense for the Herbie talk—begin a distinguished paper, the talk would already be given by the time the video abstracts were shown, and it was presented at a plenary session, so no one had to choose whether or not to see the talk. So we decided to be a little more creative.

Talk

The Herbie talk was delivered by Pavel Panchekha in a 25 minute slot on . We recorded another take a week after the conference with the same slides, which you can watch below. You can also download the slides in Keynote or PDF format.