Word-length optimization for differentiable nonlinear systems

ABSTRACT

This article introduces an automatic design procedure for determining the sensitivity of outputs in a digital signal processing design to small errors introduced by rounding or truncation of internal variables. The proposed approach can be applied to both linear and nonlinear designs. By analyzing the resulting sensitivity values, the proposed procedure is able to determine an appropriate distinct word-length for each internal variable in a fixed-point hardware implementation. In addition, the power-optimizing capabilities of word-length optimization are studied. Application of the proposed procedure to adaptive filters and polynomial evaluation circuits realized in a Xilinx Virtex FPGA has resulted in area reductions of up to 80% (mean 66%) combined with power reductions of up to 98% (mean 87%) and speed-up of up to 36%(mean 20%) over common alternative design strategies.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Cesare Alippi, Randomized Algorithms: A System-Level, Poly-Time Analysis of Robust Computation, IEEE Transactions on Computers, v.51 n.7, p.740-749, July 2002 [doi>10.1109/TC.2002.1017694]
• 3: Cantin, M.-A., Savaria, Y., and Lavoie, P. 2001. An automatic word length determination method. In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, CA. V-53--V-56.
• 4: Mark L. Chang , Scott Hauck, Automated Least-Significant Bit Datapath Optimization for FPGAs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.59-67, April 20-23, 2004
• 5: 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]
• 6: George A. Constantinides, Perturbation Analysis for Word-length Optimization, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.81, April 09-11, 2003
• 7: Constantinides, G. A., Cheung, P. Y. K., and Luk, W. 2003. Wordlength optimization for linear digital signal processing. IEEE Trans. Computer-Aid. Des. Integ. Circ. Syst. 22, 10 (Oct.), 1432--1442.
• 8: George A. Constantinides , Peter Y. K. Cheung , Wayne Luk, Synthesis And Optimization Of DSP Algorithms, Kluwer Academic Publishers, Norwell, MA, 2004
• 9: Constantinides, G. A. and Woeginger, G. J. 2002. The complexity of multiple wordlength assignment. Appl. Math. Lett. 15, 2 (Feb.), 137--140.
• 10: 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]
• 11: FREETEL. 1993. Esprit project 6166: FREETEL database.
• 12: Altaf Abdul Gaffar , Oskar Mencer , Wayne Luk , Peter Y. K. Cheung, Unifying Bit-Width Optimisation for Fixed-Point and Floating-Point Designs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.79-88, April 20-23, 2004
• 13: Simon Haykin, Adaptive filter theory (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 14: James Hwang , Brent Milne , Nabeel Shirazi , Jeffrey D. Stroomer, System Level Tools for DSP in FPGAs, Proceedings of the 11th International Conference on Field-Programmable Logic and Applications, p.534-543, August 27-29, 2001
• 15: Jackson, L. B. 1970. On the interaction of roundoff noise and dynamic range in digital filters. Bell Syst. Tech. J. 49 (Feb.), 159--184.
• 16: H. Keding , M. Willems , M. Coors , H. Meyr, FRIDGE: a fixed-point design and simulation environment, Proceedings of the conference on Design, automation and test in Europe, p.429-435, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 17: Kum, K.-I. and Sung, W. 2001. Combined word-length optimization and high-level synthesis of digital signal processing systems. IEEE Trans. Computer Aid Des. 20, 8 (Aug.), 921--930.
• 18: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987 [doi>10.1109/TC.1987.5009446]
• 19: Mahesh Mehendale , Sunil D. Sherlekar, VLSI Synthesis of DSP Kernels: Algorithmic and Architectural Transformations, Kluwer Academic Publishers, Norwell, MA, 2001
• 20: Mitra, S. K. 1998. Digital Signal Processing. McGraw-Hill, New York.
• 21: Muller, J. 1997. Elementary Functions. Springer-Verlag, Berlin, Germany.
• 22: 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
• 23: Janardhan H. Satyanarayana , Keshab K. Parhi, Theoretical analysis of word-level switching activity in the presence of glitching and correlation, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.2, p.148-159, April 2000 [doi>10.1109/92.831435]
• 24: Adel S. Sedra , Kenneth C. Smith, Microelectronic circuits, 2nd ed., Holt, Rinehart & Winston, Austin, TX, 1987
• 25: Sidahao, N., Constantinides, G. A., and Cheung, P. Y. K. 2003. Architectures for function evaluation on FPGAs. In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, CA.
• 26: SIMULINK. Simulink. http://www.mathworks.com.
• 27: 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
• 28: Accuracy Sensitive Word--Length Selection for Algorithm Optimization, Proceedings of the International Conference on Computer Design, p.54, October 05-05, 1998
• 29: Xilinx, Inc. 2002. Field Programmable Gate Arrays. Xilinx, Inc., San Jose, CA.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

General Terms:
Algorithms, Design, Performance

Keywords:
Signal processing, bitwidth, synthesis, word-length