FRIDGE

Fixed-point pRogrammIng DesiGn Environment

Project goal

System level design environment for specification and implementation of digital fixed-point systems (hardware as well as software) 

    Motivation

    Digital system design is characterized by ever increasing system complexity that has to be implemented within reduced time, resulting in minimum costs and especially a short time-to-market. These characteristics call for a seamless design flow that allows to perform the suitable design steps on the highest level of abstraction.

    Fixed-point implementations are preferred to floating-point implementations whenever the system is sensitive to power consumption, execution speed, chip size and device prices. On the other hand, fixed-point system design requires a specific design flow, which up to now is time consuming and error prone. This design flow is illustrated by the following diagram.

    Algorithm design starts from a floating-point description. This allows to ignore the effects of finite word lengths and fixed exponents and to abstract from all implementation details. The algorithm space can be evaluated in the most efficient way, only concentrating on whether the algorithm fulfills the performance requirements of the system, such as bit error rate or speech quality. The abstraction allows a maximum of design reuse. The floating-point description can be done using a block diagram description (which up to now is very much limited to dataflow oriented applications), where the functional blocks can be user defined (using a high level language) or come from a library. As well, a high level language such as 'C' can be used for the floating-point description of the algorithm. Most of the block diagram descriptions can be automatically translated into a high level language description.

    On the fixed-point level, to all operands a fixed word length and a fixed exponent is assigned, while the control structure and the operations of the floating point program remain unchanged. This description is used to analyze whether the fixed-point model fulfills the algorithmic system requirements.

    The transformation from the floating-point level to the fixed-point level is not unique but a complex design space exists. Design criterion is a performance true transformation, expressing that the fixed-point specification fulfills the system requirements. Especially for HW and SW implementations, different fixed-point specifications might be preferable, so that for a typical design (and especially in HW/SW codesign) multiple transformations from the floating-point level to the fixed-point level are necessary to result in a near optimum solution.

    So far, this transformation has to be done manually. This is an error prone and time consuming process even for a single transformation. For more complex applications this takes more than 50% of the design time once the floating-point algorithm is fixed. Keeping increasing system complexities and time-to-market pressure in mind, there is a strong demand for an automated transformation. On the implementational level, the fixed-point model of the algorithm has to be transferred into the best suited target description, either using a hardware description language (HDL) or a programming language. These transformations are not unique but address a large design space. 

      The FRIDGE design flow

      The components of the FRIDGE design flow in more detail:

       

      • Floating-point algorithm (ANSI-C):
      • The designer describes the functionality using floating-point data types available in ANSI-C (float, double).
         
      • Annotation:
      • The designer annotates some key operands with information with bit-true attribues, e.g. the word length, the integer wordlength, etc. Additionally, he provides information about the casting rules that describe how to perform data type conversions. This is done using the new data types that come with the fixed-point desrciption language fixed-C.  They allow to assign an arbitrary word length and an arbitrary location of the exponent to the operand. Notice that the existing integer  data types of ANSI-C represent a subset of fixed, having a fixed word length and the exponent fixed to 2° . Using  fixed-C the error prone task of assigning explicit shift operations can be skipped, since the semantics of fixed-C guarantee correct arithmetic operations, i.e. considers the location of the binary point. Operand annotation allows to assign local information, in contrast to global annotation where a variable will take the same representation throughout the complete program, regardless of the context it is used in.
         
      • Hybrid Algorithm (fixed-C):
      • Annotation results in a hybrid description of the algorithm since only some of the operands are converted to fixed-point, but the others remain as floating-point operands.
         
      • HYBRIS - hybrid system simulation classes:
      • HYBRIS supports the complete specification of fixed-C. It therefore allows to simulate fixed-point specifications in a bit-true way. A hybrid simulation is required whenever the designer wants to check the effect of his local annotations. As soon as all operands are specified as fixed-point data types, HYBRIS allows bit-true simulations of the algorithm. Of course, this bit-true simulation is platform independent.

        In addition, with HYBRIS the designer can collect data that is helpful for the program annotation, such as min, max, mean, variance. This information can be collected locally for each operand, not only for variables. It is possible to collect data concerning the overflow behavior of the fixed-point operands, as well as generating histograms that allow to analyze the distribution of values that the operand takes.

      • Interpolation:
      • Today, fixed-point design requires the designer to explicitely annotatate all operands in the code, which has to be done manually. This is a time-consuming and error-prone task. By wordlength interpolation, FRIDGE takes advantage of the information inherent to the local annotations of the hybrid code adn transfers the remaining floating-point operands into fixed-point operands. The interpolation is based on a comprehensive control and data flow analysis. Special attention is paid to loops and pointers, which are completely supported by the system.

        Interpolation frees the designer from over-specification but allows to bring in all his specific knowledge and requirements by means of explicit annotations.

        The interpolation concept has been presented at DAC'97.

      • Fixed-point algorithm (fixed-C):
      • All operands of the algorithm are of type fixed. Therefore a bit-true behavior of the algorithm is specified. The bit-true performance can be simulated and analyzed using HYBRIS. Traditional fixed-point simulators increase simulation time by up to two orders of magnitude. This is due to the fact that there is no built-in fixed-point data type on the host machine, so the fixed-point arithmetic has to be emulated. While existing concepts perform all of these emulations at runtime, FRIDGE supports a compiled simulation approach, that performs compile-time analysis that increases simulation speed by one order of magnitude.

        The fast-simualtion concept was presented at DATE'98.

      • Optimization for a fixed-point algorithm (ANSI-C):
      • There are many tools such as compilers that support ANSI-C, but only very recent approaches support extensions coming with fixed-C  [JW98]. Therefore it is necessary to generate a fixed-point description of the algorithm that makes use of the fixed-point data types of ANSI-C only. In order to adjust the representable dynamic ranges of the operands, shift operations have to be included. The optimizer within FRIDGE automatically determines the appropriate shift sizes and generates an ANSI-C fixed-point program.

        The transformation can either be done bit-true (which might be necessary for standards which have been defined in a bit-true way) or performance true, guaranteeing that the algorithm fulfills the performance criteria as the bit-true specification did. In general, the transformation addresses a complex design space, and the designer is enabled to specify optimization criteria such as minimum runtime or minimum memory consumption.

        The ANSI-C code generation concept was presented at ICSPAT'97.

        Summary: Features of FRIDGE

        • supports the generalized fixed-point data type fixed coming as an extension to ANSI-C. fixed-C allows fixed-point algorithm specifications as well as hybrid specifications (with some operands specified as fixed-point using data type fixed while other remain with floating-point accuracy).
        • HYBRIS: a HYBRId Simulation classes supporting the complete fixed-C syntax. This allows to perform bit-true simulations. Comprehensive compile-time analysis allows to decrease simulation times for fixed-point algorithms by one order of magnitude compared to existing simulation environments.
        • tool supported transformation of floating-point programs written in ANSI-C into fixed-point programs written in fixed-C based on an interpolative approach.
        • optimized transformation of fixed-point programs written in fixed-C into fixed-point programs written in ANSI-C by automatically including appropriate shift operations.

          Future plans

          • optimized transformation of fixed-point programs written in fixed-C into a behavioral Hardware Description Language (HDL) as input to a behavioral synthesis tool
          • transformation of fixed-C algorithms into integer C, both for dedicated DSP compilers (such as TI's C62x C Compiler) or as ANSI C.
          • optimized transformation of fixed-point programs written in fixed-C into assembly code for DSPs. (we strongly believe in the future of optimizing DSP compilers!)

           

          Publications

          Keding, H., Coors, M. and Meyr, H.: Efficient Design Flow for Fixed-Point Systems, G. S. Moschytz. Kluwer Academic Publishers, , ISBN: 0-306-47303-8 Jan/2000, ISBN: 0-306-47303-8


          Keding, H., Hürtgen, F., Willems, M. and Coors, M.: Transformation of Floating-Point into Fixed-Point Algorithms by Interpolation Applying a Statistical Approach, in Proc. Int. Conf. on Signal Processing Application and Technology (ICSPAT) in Proc. Int. Conf. on Signal Processing Application and Technology (ICSPAT) , (Toronto) Sep/1998


          Keding, H., Willems, M., Coors, M. and Meyr, H.: FRIDGE: A Fixed-Point Design and Simulation Environment, in Proceedings of the European Conference on Design, Automation and Test (DATE) in Proceedings of the European Conference on Design, Automation and Test (DATE) , p.p. 429-435 , (Paris) Feb/1998


          Willems, M., Bürsgens, V. .. and Meyr, H.: FRIDGE: Floating-Point Programming of Fixed-Point Digital Signal Processors, in Proc. Int. Conf. on Signal Processing Application and Technology (ICSPAT) in Proc. Int. Conf. on Signal Processing Application and Technology (ICSPAT) , p.p. 1000-1005 , (San Diego) Sep/1997


          Willems, M., Bürsgens, V. .. and Meyr, H.: FRIDGE: Fliesskomma-Programmierung von Festkomma-DSPs, In Proc. of DSP Deutschland 97 1997


          Willems, M., Bürsgens, V. .., Keding, H., Grötker, T. and Meyr, H.: System Level Fixed-Point Design Based on an Interpolative Approach, in Proceedings of the Design Automation Conference (DAC) , p.p. 293-298 , (Anaheim) Jun/1997


          Willems, M., Bürsgens, V. .., Grötker, T. and Meyr, H.: FRIDGE: An Interactive Fixed-Point Code Generation Environment for HW/SW CoDesign, In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 1997