Synthesis of fixed-point programs

Created by W.Langdon from gp-bibliography.bib Revision:1.4420

  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 =          "",
  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}",

Genetic Programming entries for Eva Darulova Viktor Kuncak Rupak Majumdar Indranil Saha