Back to overview

Towards a Compiler for Reals

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Author Darulova Eva, Kuncak Viktor,
Project Developing Capacity for High-Productivity Large-Scale Computing
Show all

Original article (peer-reviewed)

Journal ACM Trans. Program. Lang. Syst. (TOPLAS)
Publisher ACM
Volume (Issue) 39(2)
Page(s) 1 - 28
Title of proceedings ACM Trans. Program. Lang. Syst. (TOPLAS)
DOI 10.1145/3014426

Open Access

Type of Open Access Repository (Green Open Access)


Numerical software, common in scientific computing or embedded systems, inevitably uses a finite-precision approximation of the real arithmetic in which most algorithms are designed. In many applications, the roundoff errors introduced by finite-precision arithmetic are not the only source of inaccuracy, and measurement and other input errors further increase the uncertainty of the computed results. Adequate tools are needed to help users select suitable data types and evaluate the provided accuracy, especially for safety-critical applications. We present a source-to-source compiler called Rosa that takes as input a real-valued program with error specifications and synthesizes code over an appropriate floating-point or fixed-point data type. The main challenge of such a compiler is a fully automated, sound, and yet accurate-enough numerical error estimation. We introduce a unified technique for bounding roundoff errors from floating-point and fixed-point arithmetic of various precisions. The technique can handle nonlinear arithmetic, determine closed-form symbolic invariants for unbounded loops, and quantify the effects of discontinuities on numerical errors. We evaluate Rosa on a number of benchmarks from scientific computing and embedded systems and, comparing it to the state of the art in automated error estimation, show that it presents an interesting tradeoff between accuracy and performance.