000181818 001__ 181818
000181818 005__ 20190316235508.0
000181818 037__ $$aREP_WORK
000181818 245__ $$aOn the Generation of Precise Fixed-Point Expressions
000181818 269__ $$a2013
000181818 260__ $$c2013
000181818 300__ $$a10
000181818 336__ $$aReports
000181818 520__ $$aSeveral 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 minimizes 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.
000181818 6531_ $$afixed-point arithmetic
000181818 6531_ $$aroundoff error
000181818 6531_ $$asynthesis
000181818 6531_ $$agenetic programming
000181818 700__ $$0244059$$g191100$$aDarulova, Eva
000181818 700__ $$0240031$$g177241$$aKuncak, Viktor
000181818 700__ $$aMajumdar, Rupak$$0(EPFLAUTH)180715$$g180715
000181818 700__ $$aSaha, Indranil
000181818 8564_ $$uhttps://infoscience.epfl.ch/record/181818/files/fixpoints_techreport_1.pdf$$zPreprint$$s486682$$yPreprint
000181818 909C0 $$xU11739$$0252019$$pLARA
000181818 909CO $$ooai:infoscience.tind.io:181818$$qGLOBAL_SET$$pIC$$preport
000181818 917Z8 $$x191100
000181818 917Z8 $$x191100
000181818 917Z8 $$x191100
000181818 917Z8 $$x191100
000181818 937__ $$aEPFL-REPORT-181818
000181818 973__ $$sPUBLISHED$$aEPFL
000181818 980__ $$aREPORT