- author = "Eva Darulova and Viktor Kuncak and Rupak Majumdar and Indranil Saha",
- booktitle = "Proceedings of the International Conference on Embedded Software (EMSOFT 2013)",
- title = "Synthesis of fixed-point programs",
- year = "2013",
- month = sep # " 29-" # oct # " 4",
- keywords = "genetic algorithms, genetic programming, SBSE, Software Engineering, Design-Methodologies, synthesis, stochastic optimisation, embedded control software",
-
URL = "
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.368.1023",
-
DOI = "
doi:10.1109/EMSOFT.2013.6658600",
-
abstract = "Several problems in the implementations of control
systems, signal-processing systems, and scientific
computing systems reduce to compiling a polynomial
expression over the real numbers into an imperative
program using fixed-point arithmetic. Fixed-point
arithmetic only approximates real values, and its
operators do not have the fundamental properties of
real arithmetic, such as associativity. Consequently, a
naive compilation process can yield a program that
significantly deviates from the real polynomial,
whereas a different order of evaluation can result in a
program that is close to the real value on all inputs
in its domain.
We present a compilation scheme for real-valued arithmetic expressions to fixed-point arithmetic programs. Given a real-valued polynomial expression t, we find an expression t' that is equivalent to t over the reals, but whose implementation as a series of fixed-point operations minimises the error between the fixed-point value and the value of t over the space of all inputs. We show that the corresponding decision problem, checking whether there is an implementation t' of t whose error is less than a given constant, is NP-hard. We then propose a solution technique based on genetic programming. Our technique evaluates the fitness of each candidate program using a static analysis based on affine arithmetic. We show that our tool can significantly reduce the error in the fixed-point implementation on a set of linear control system benchmarks. For example, our tool found implementations whose errors are only one half of the errors in the original fixed-point expressions.",
- notes = "Also known as \cite{6658600}",
