Practical Floating-point Divergence Detection

Share

Wei-Fan Chiang, Ganesh Gopalakrishnan, Zvonimir Rakamaric. 28th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2015), Raleigh, NC, USA.
[pdf] [bib]

Abstract: Reducing floating-point precision allocation in HPC programs is of considerable interest from the point of view of obtaining higher performance. However, this can lead to unexpected behavioral deviations from the programmer’s intent. In this paper, we focus on the problem of divergence detection: when a given floating-point program exhibits different control flow (or differs in terms of other discrete outputs) with respect to the same program interpreted under reals. This problem has remained open even for everyday programs such as those that compute convex-hulls. We propose a classification of the divergent behaviors exhibited by programs, and propose efficient heuristics to generate inputs causing divergence. Our experimental results demonstrate that our input generation heuristics are far more efficient than random input generation for divergence detection, and can exhibit divergence even for programs with thousands of inputs.

Bibtex:

@inproceedings{lcpc2015-cgr,
  author = {Wei-Fan Chiang and Ganesh Gopalakrishnan and Zvonimir Rakamari\'c},
  title = {Practical Floating-point Divergence Detection},
  booktitle = {Proceedings of the 28th International Workshop on Languages
    and Compilers for Parallel Computing (LCPC)},
  series = {Lecture Notes in Computer Science},
  volume = {9519},
  publisher = {Springer},
  editor = {Xipeng Shen and Frank Mueller and James Tuck},
  year = {2015},
  pages = {271--286},
}