Toward efficient static analysis of finite-precision effects in DSP applications via affine arithmetic modeling

ABSTRACT

We introduce a static error analysis technique, based on smart interval methods from affine arithmetic, to help designers translate DSP codes from full-precision floating-point to smaller finite-precision formats. The technique gives results for numerical error estimation comparable to detailed simulation, but achieves speedups of three orders of magnitude by avoiding actual bit-level simulation. We show results for experiments mapping common DSP transform algorithms to implementations using small custom floating point formats.

REFERENCES

• 1: L. H. de Figueiredo and J. Stolfi. Self-validated numerical methods and applications. Brazilian Mathematics Colloquium monograph, IMPA, Rio de Janeiro, Brazil, July 1997.
• 2: F. Fang, T. Chen, and R. Rutenbar. Floating-point bit-width optimization for low-power signal processing applications. In International Conf. on Acoustic, Speech, and Signal Processing, May 2002.
• 3: F. Fang, T. Chen, and R. Rutenbar. Lightweight floating-point arithmetic: Case study of inverse discrete cosine transform. EURASIP J. Sig. Proc.; Special Issue on Applied Implementation of DSP and Communication Systems, 2002(9):879--892, Sept. 2002.
• 4: Walter Krämer, A Priori Worst Case Error Bounds for Floating-Point Computations, IEEE Transactions on Computers, v.47 n.7, p.750-756, July 1998 [doi>10.1109/12.709374]
• 5: T. L. Laakso and L. B. Jackson. Bounds for floating-point roundoff noise. IEEE Trans. Circ. Sys II: Analog and Digital Signal Processing, 41:424--426, June 1994.
• 6: Andreas Lemke , Lars Hedrich , Erich Barke, Analog circuit sizing based on formal methods using affine arithmetic, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.486-489, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774643]
• 7: B. Liu and T. Kaneko. Error analysis of digital filters realized with floating-point arithmetic. Proc. IEEE, 57:1735--1747, Oct. 1969.
• 8: R. E. Moore. Interval Analysis. Prentice-Hall, 1966.
• 9: Markus Püschel , José M. F. Moura , Bryan Singer , Jianxin Xiong , Jeremy Johnson , David Padua , Manuela Veloso , Robert W. Johnson, Spiral: A Generator for Platform-Adapted Libraries of Signal Processing Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.21-45, February 2004 [doi>10.1177/1094342004041291]
• 10: B. D. Rao. Floating point arithmetic and digital filters. IEEE Trans. Sig. Proc., 40:85--95, Jan. 1992.
• 11: P. H. Sterbenz. Floating-Point Computation. Prentice-Hall, 1974.
• 12: C. Tsai. Floating-point roundoff noises of first- and second-order sections in parallel form digital filters. IEEE Trans. Circ. Sys II: Analog and Digital Signal Processing, 44:774--779, Sept. 1997.
• 13: C. Weinstein and A. V. Oppenheim. A comparison of roundoff noise in floating point and fixed point digital filter realizations. Proc. IEEE, 57:1181--1183, June 1969.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance

Keywords:
Static error analysis, affine arithmetic, custom floating-point, embedded hardware, probabilistic error bound