On the Generation of Precise Fixed-Point Expressions

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

@TechReport{oai:infoscience.epfl.ch:181818,
  author =       "Eva Darulova and Viktor Kuncak and Rupak Majumdar and 
                 Indranil Saha",
  title =        "On the Generation of Precise Fixed-Point Expressions",
  year =         "2013",
  institution =  "Ecole Polytechnique Federale de Lausanne",
  number =       "EPFL-REPORT-181818",
  address =      "Switzerland",
  keywords =     "genetic algorithms, genetic programming, fixed-point
                 arithmetic , roundoff error, synthesis",
  URL =          "http://infoscience.epfl.ch/record/181818/files/fixpoints_techreport_1.pdf",
  bibsource =    "OAI-PMH server at infoscience.epfl.ch",
  language =     "en",
  oai =          "oai:infoscience.epfl.ch:181818",
  oai =          "oai:CiteSeerX.psu:10.1.1.308.8582",
  URL =          "http://infoscience.epfl.ch/record/181818",
  URL =          "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.8582",
  abstract =     "Several problems in the implementations of control
                 systems, signal-processing systems, and scientific
                 computing systems reduce to compiling a polynomial
                 expression over the reals 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.",
}

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

Citations