On the Generation of Precise Fixed-Point Expressions

Eva Darulová, Viktor Kunčak, Rupak Majumdar, Indranil SahaInfoscience 2013

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 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.

Introduction

In embedded systems, developers frequently utilize fixed-point arithmetic instead of floating-point to minimize hardware cost and power consumption. However, fixed-point arithmetic is mathematically "broken" in that it lacks properties like associativity and distributivity. While (a + b) + c and a + (b + c) are identical in real numbers, they can yield different results in fixed-point due to intermediate rounding and bit-shifting.

A naive implementation of a control law or signal processing algorithm can lead to significant precision loss. While prior research has focused on bitwidth allocation, this paper addresses the optimization of evaluation order. We prove that finding the optimal evaluation order to minimize error is an NP-hard problem, justifying the use of heuristic search strategies like genetic programming.

Methods

The proposed compilation scheme transforms real-valued polynomials into high-precision fixed-point programs using two primary pillars:

  1. Genetic Programming (GP): To navigate the massive search space of equivalent expressions, we use GP to evolve better implementations. Standard mathematical rewrite rules (associativity, commutativity, distributivity) serve as mutation and crossover operators, ensuring all candidates remain mathematically equivalent to the original.
  2. Static Analysis (Affine Arithmetic): To evaluate the "fitness" of candidate expressions, we use affine arithmetic to compute a sound upper bound on the worst-case round-off error. This analysis tracks first-order correlations between variables, providing a reliable metric for comparing different evaluation orders.
Figure 3: The optimization process showing the reduction of analyzed absolute error over successive generations of the genetic programming algorithm.

Key Results

We evaluated the approach on a suite of control system benchmarks, including linear models (bicycle, DC motor, inverted pendulum) and nonlinear benchmarks (rigid body controllers).

Our tool achieved error reductions of up to 70% compared to original expressions. This improvement represents precision gained "for free," as it requires no additional hardware bits. Furthermore, the GP-based search proved significantly more effective than random search, finding implementations for complex expressions that were over 50% more accurate within the same time budget.

Figure 6: Comprehensive results across various benchmarks, showing the original error and the relative improvement (reduction) achieved by the optimized evaluation order.

Beyond numerical accuracy, these optimizations have practical impacts on system performance. When integrated into controller synthesis, the optimized expressions improved the size of the "region of practical stability" by more than 50% for several benchmarks.

Conclusion

This work demonstrates that evaluation order is a critical factor in the precision of fixed-point implementations. By combining genetic programming with affine arithmetic, we can automatically synthesize programs that are substantially more accurate than those produced by naive compilation. Future work will focus on reducing the pessimism of static analysis for highly nonlinear functions and improving the scalability of the search for extremely large expressions.

Summary updated

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 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.
BibTeX
@inproceedings{darulova2013generation,
  author = {Eva Darulová and Viktor Kunčak and Rupak Majumdar and Indranil Saha},
  title = {{On the Generation of Precise Fixed-Point Expressions}},
  booktitle = {Infoscience},
  year = {2013},
}
Figure