soc logo

"No bird soars too high, if he soars with his own wings."   W. Blake

Efficient Search for Inputs Causing High Floating-point Errors

PPoPP 2014 screenshot

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.

Citation

Wei-Fan Chiang, Ganesh Gopalakrishnan, Zvonimir Rakamaric, Alexey Solovyev
Efficient Search for Inputs Causing High Floating-point Errors
Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 43--52, doi:10.1145/2555243.2555265, 2014.

BibTeX

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

Acknowledgements

Thanks to Alan Humphrey, Brandon Gibson, and Martin Berzins for providing us the DQMOM benchmark from the Uintah Framework. Chiang was supported in part by an Nvidia Graduate Fellowship and Gopalakrishnan by the SUPER (super-scidac.org). Additional support was provided by NSF grants ACI 1148127, CCF 1255776, CCF 1302449, and CCF 1346756.