Scalable Analytical Accuracy Models for Fixed-Point Arithmetic Implementations

Signal processing algorithms for embedded systems are usually designed and specified with floating-point datatypes, but many embedded architectures do not even feature floating-point operators. Before being implemented in hardware, the algorithm must hence undergo a conversion to fixed-point arithmetic. This conversion is a tedious process and can cause a degradation in the accuracy of the algorithm. This degradation must be evaluated in order to guarantee the proper functioning of the system. Also, a typical requirement is to minimize the cost of the system as long as the accuracy criterion is satisfied. It is called wordlength optimization. Until recently, the only methods available for accuracy evaluation were based on bitaccurate simulations. Simulation times prohibited the use of automatic optimization algorithms. During the last decade, new analytical methods have emerged. These methods still face severe scaling limitations and cannot handle parametric programs. In this work, we study the relevance of the polyhedral model and of polyhedral intermediate representations for the development of a new analytical technique for accuracy estimation. We show that the formalism of Systems of Affine Recurrence Equations (SAREs) can be used to perform noise analysis. We derive a method and a set of program transformations that allow us to handle some classes of programs, and even some recursive filters