Efficient Search for Inputs Causing High Floating-point Errors

Wei-Fan Chiang, Ganesh Gopalakrishnan, Zvonimir Rakamaric, Alexey Solovyev. 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2014), Orlando, FL, USA.
[pdf] [bib]

Abstract: Tools for floating-point error estimation are fundamental to program understanding and optimization. In this paper, we focus on tools for determining the input settings to a floating point routine that maximizes its result error. Such tools can help support activities such as precision allocation, performance optimization, and auto-tuning. We benchmark current abstraction-based precision analysis methods, and show that they often do not work at scale, or generate highly pessimistic error estimates, often caused by non-linear operators or complex input constraints that define the set of legal inputs. We show that while concrete-testing-based error estimation methods based on maintaining shadow values at higher precision can search out higher error-inducing inputs, suitable heuristic search guidance is key to finding higher errors. We develop a heuristic search algorithm called Binary Guided Random Testing (BGRT). In 45 of the 48 total benchmarks, including many real-world routines, BGRT returns higher guaranteed errors. We also evaluate BGRT against two other heuristic search methods called ILS and PSO, obtaining better results.

Bibtex:

@inproceedings{ppopp2014-cgrs,
  author = {Wei-Fan Chiang and Ganesh Gopalakrishnan and Zvonimir Rakamari\'c and
    Alexey Solovyev},
  title = {Efficient Search for Inputs Causing High Floating-point Errors},
  booktitle = {Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice
    of Parallel Programming (PPoPP)},
  publisher = {ACM},
  year = {2014},
  pages = {43--52},
}