An automated, efficient and static bit-width optimization methodology towards maximum bit-width-to-error tradeoff with affine arithmetic model

ABSTRACT

Ideally, bit-width analysis methods should be able to find the most appropriate bit-widths to achieve the optimum bit-width-to-error tradeoff for variables and constants in high level DSP algorithms when they are implemented into hardware. The tradeoff enables the fixed-point hardware implementation to be area efficient but still within the allowed error tolerance. Unfortunately, almost all the existing static bit-width analysis methods are Interval Arithmetic (IA) based that may overestimate bit-widths and enable fairly pessimistic bit-width-to-error tradeoff. We have developed an automated and efficient bit-width optimization methodology that is Affine Arithmetic (AA) based. Experiments have proven that, compared to the previous static analysis methods, our methodology not only dramatically reduces the fractional bit-width by more than 35% but also slightly reduces the integer bit-width. In addition, our probabilistic error analysis method further enlarges the bit-width-to-error tradeoff.

REFERENCES

• 1: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 2: Mark L. Chang , Scott Hauck, Précis: A Design-Time Precision Analysis Tool, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.229, September 22-24, 2002
• 3: M. L. Chang and S. Hauck, "Variable Precision Analysis for FPGA Synthesis," Nasa Earth Science Technology Conference 2003.
• 4: A. Nayak , M. Haldar , A. Choudhary , P. Banerjee, Precision and error analysis of MATLAB applications during automated hardware synthesis for FPGAs, Proceedings of the conference on Design, automation and test in Europe, p.722-728, March 2001, Munich, Germany
• 5: Claire Fang Fang , Rob A. Rutenbar , Markus Püschel , Tsuhan Chen, Toward efficient static analysis of finite-precision effects in DSP applications via affine arithmetic modeling, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775960]
• 6: Claire F. Fang , Rob A. Rutenbar , Tsuhan Chen, Fast, Accurate Static Analysis for Fixed-Point Finite-Precision Effects in DSP Designs, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.275, November 09-13, 2003 [doi>10.1109/ICCAD.2003.68]
• 7: K. Kum and W. Sung, "Combined word-length optimization and high-level synthesis of digital signal processing systems," IEEE Trans. on Computer-Aided Design, Aug, 2001.
• 8: Dong-U Lee , Altaf Abdul Gaffar , Oskar Mencer , Wayne Luk, MiniBit: bit-width optimization via affine arithmetic, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065799]
• 9: S. Kim, K.-I. Kum, and W. Sung, "Fixed-point optimization utility for C and C++ based digital signal processing programs," Workshop on VLSI and Signal Processing, Osaka, 1995.
• 10: N. Shirazi , A. Walters , P. Athanas, Quantitative analysis of floating point arithmetic on FPGA based custom computing machines, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines, p.155, April 19-21, 1995
• 11: J. Stolfi and L. H. de Figueiredo, "An introduction to affine arithmetic," TEMA Tend. Mat. Apl. Comput., 4, Vol.3, pp. 297--312, 2003.
• 12: http://www.systemc.org
• 13: D. Galloway, The Transmogrifier C hardware description language and compiler for FPGAs, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines, p.136, April 19-21, 1995
• 14: Goran Doncev , Miriam Leeser , Shantanu Tarafdar, High Level Synthesis for Designing Custom Computing Hardware, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.326, April 15-17, 1998
• 15: Brad L. Hutchings , Brent E. Nelson, Using general-purpose programming languages for FPGA design, Proceedings of the 37th conference on Design automation, p.561-566, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337581]
• 16: Mark Stephenson, "Bitwise: Optimization Bitwidths Using Data-Range Propagation," Master's thesis. Massachusetts Institute of Technology, May 2000.
• 17: Kiran Bondalapati , Viktor K. Prasanna, Dynamic Precision Management for Loop Computations on Reconfigurable Architectures, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.249, April 21-23, 1999
• 18: W. Sung and K. I. Kum. "Simulation-based word-length optimization method for fixed-point digital signal processing systems," IEEE Transactions on Signal Processing, vol. 43, no. 12, pp.3087--3090, December 1995.
• 19: Jason R. C. Patterson, Accurate static branch prediction by value range propagation, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.67-78, June 18-21, 1995, La Jolla, California, United States
• 20: R. Cmar , L. Rijnders , P. Schaumont , S. Vernalde , I. Bolsens, A methodology and design environment for DSP ASIC fixed point refinement, Proceedings of the conference on Design, automation and test in Europe, p.56-es, January 1999, Munich, Germany [doi>10.1145/307418.307503]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

General Terms:
Algorithms, Design, Performance