On the Generation of Precise Fixed-Point Expressions

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

@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