Compile-time and instruction-set methods for improving floating- to fixed-point conversion accuracy

ABSTRACT

This paper proposes and evaluates compile time and instruction-set techniques for improving the accuracy of signal-processing algorithms run on fixed-point embedded processors. These techniques are proposed in the context of a profile guided floating- to fixed-point compiler-based conversion process. A novel fixed-point scaling algorithm (IRP) is introduced that exploits correlations between values in a program by applying fixed-point scaling, retaining as much precision as possible without causing overflow. This approach is extended into a more aggressive scaling algorithm (IRP-SA) by leveraging the modulo nature of 2's complement addition and subtraction to discard most significant bits that may not be redundant sign-extension bits. A complementary scaling technique (IDS) is then proposed that enables the fixed-point scaling of a variable to be parameterized, depending upon the context of its definitions and uses. Finally, a novel instruction-set enhancement—fractional multiplication with internal left shift (FMLS)—is proposed to further leverage interoperand correlations uncovered by the IRP-SA scaling algorithm. FMLS preserves a different subset of the full product's bits than traditional fractional fixed-point or integer multiplication. On average, FMLS combined with IRP-SA improves accuracy on processors with uniform bitwidth register architectures by the equivalent of 0.61 bits of additional precision for a set of signal-processing benchmarks (up to 2 bits). Even without employing FMLS, the IRP-SA scaling algorithm achieves additional accuracy over two previous fixed-point scaling algorithms by averages of 1.71 and 0.49 bits. Furthermore, as FMLS combines multiplication with a scaling shift, it reduces execution time by an average of 9.8%. An implementation of IDS, specialized to single-nested loops, is found to improve accuracy of a lattice filter benchmark by the equivalent of more than 16-bits of precision.

REFERENCES

• 1: Aamodt, T. 2001. Floating-point to Fixed-Point Compilation and Embedded Architectural Support. M.S. thesis, University of Toronto.
• 2: Tor Aamodt , Paul Chow, Embedded ISA support for enhanced floating-point to fixed-point ANSI-C compilation, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.128-137, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354899]
• 3: Alta Group. 1994. Fixed-Point Optimizer User's Guide. Cadence Design Systems, Inc. Sunnyvale, CA.
• 4: Anspach, K. M., Bomar, B. W., Engels, R. C., and Joseph, R. D. 1996. Minimization of fixed-point roundoff noise in extended state-space digital filters. IEEE Trans. Circuits Syst. II 43, 3 (Mar.).
• 5: Scott A. Bortoff, Approximate state-feedback linearization using spline functions, Automatica (Journal of IFAC), v.33 n.8, p.1449-1458, Aug. 1997 [doi>10.1016/S0005-1098(97)00070-8]
• 6: Chung, J.-G. and Parhi, K. K. 1995. Scaled normalized lattice digital filter structures. IEEE Trans. Circuits Syst. II 42, 4 (Apr.).
• 7: Hwang, S. Y. 1977. Minimum uncorrelated unit noise in state-space digital filtering. IEEE Transactions on Accoustics, Speech, and Signal Processing ASSP-25, 273--281.
• 8: Jackson, L. B. 1970a. On the interaction of roundoff noise and dynamic range in digital filters. Bell Syst. Tech. J. 49, 2 (Feb.).
• 9: Jackson, L. B. 1970b. Roundoff-noise analysis for fixed-point digital filters realized in cascade or parallel form. In IEEE Transactions on Audio and Electroacoustics AU-18, 2 (June).
• 10: Kim, S. and Sung, W. 1994. A floating-point to fixed-point assembly program translator for the TMS 320C25. IEEE Trans. Circuits Syst. II 41, 11 (Nov.).
• 11: Kim, S. and Sung, W. 1998. Fixed-point optimization utility for C and C++ based digital signal processing programs. IEEE Trans. Circuits Syst. II 45, 11 (Nov.).
• 12: Kum, K.-I. and Sung, W. 2001. Combined word-length optimization and high-level synthesis of digital signal processing systems. In IEEE Trans. Comput.-Aided Design Integ. Circuits Syst. 20, 8 (Aug.), 921--930.
• 13: Kum, K.-I., Kang, J., and Sung, W. 1997. A floating-point to fixed-point C converter for fixed-point digital signal processors. In Proceedings of the 2nd SUIF Compiler Workshop.
• 14: Ki-Il Kum , Jiyang Kang , Wonyong Sung, A floating-point to integer C converter with shift reduction for fixed-point digital signal processors, Proceedings of the Acoustics, Speech, and Signal Processing, 1999. on 1999 IEEE International Conference, p.2163-2166, March 15-19, 1999 [doi>10.1109/ICASSP.1999.758363]
• 15: Kum, K.-I., Kang, J., and Sung, W. 2000. AUTOSCALER for C: An optimizing floating-point to integer C program converter for fixed-point digital signal processors. IEEE Trans. Circuits Syst. II 47, 9 (Sept.), 840--848.
• 16: Daniel Menard , Daniel Chillet , François Charot , Olivier Sentieys, Automatic floating-point to fixed-point conversion for DSP code generation, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581674]
• 17: Mullis, C. T. and Roberts, R. A. 1976. Synthesis of minimum roundoff noise fixed-point digital filters. IEEE Transactions on Circuits and Systems CAS-23, 551--561.
• 18: Oppeheim, A. V. 1970. Realization of digital filters using block-floating-point arithmetic. IEEE Transactions on Audio and Electroacoustics AU-18, 2 (June).
• 19: Peng, S. 1999. UTDSP: A VLIW programmable DSP processor in 0.35 μm CMOS. M.S. thesis, University of Toronto. http://www.eecg.utoronto.ca/~speng.
• 20: Pujare, S., Lee, C. G., and Chow, P. 1995. Machine-independent compiler optimizations for the UofT DSP architecture. In Proceedings of the 6th ICSPAT. 860--865.
• 21: Saghir, M. A. 1993. Architectural and compiler support for DSP applications. M.S. thesis, University of Toronto.
• 22: Saghir, M. A. 1998. Application-specific instruction-set architectures for embedded DSP applications. Ph.D. thesis, University of Toronto.
• 23: Saghir, M. A., Chow, P., and Lee, C. G. 1994. Application-driven design of DSP architectures and compilers. In Proceedings of the ICASSP. II--437--II--440.
• 24: Singh, V. 1992. An optimizing C compiler for a general purpose DSP architecture. M.S. thesis, Univeristy of Toronto.
• 25: Spang, H. A. and Schultheiss, P. M. 1962. Reduction of quantization noise by use of feedback. IRE Trans. Commun. CS-10, 373--380.
• 26: Mark G. Stoodley , Corinna G. Lee, Software pipelining loops with conditional branches, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.262-273, December 02-04, 1996, Paris, France
• 27: Sundaramoorthy, K., Purser, Z., and Rotenberg, E. 2000. Slipstream processors: Improving both performance and fault tolerance. In ASPLOS-IX. 257--268.
• 28: Synopsys 2000a. Press Release: Synopsys Accelerates System-Level C-Based DSP Design With CoCentric Fixed-Point Designer Tool. Synopsys Inc.
• 29: Synopsys 2000b. Synopsys CoCentric Fixed-Point Designer Datasheet. Synopsys Inc.
• 30: Texas Instruments. 1993. TMS320C5x User's Guide.
• 31: M. Willems , V. Biirsgens , T. Grotker , H. Meyr, FRIDGE: An Interactive Code Generation Environment for HW/SW CoDesign, Proceedings of the 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '97) -Volume 1, p.287, April 21-24, 1997
• 32: Craig Zilles , Gurindar Sohi, Master/slave speculative parallelization, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Preprocessors

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Design, Economics, Performance

Keywords:
Compilation, digital signal processing, fixed-point, fractional multiplication, scaling, signal-to-noise ratio