Symbolic noise analysis approach to computational hardware optimization

ABSTRACT

This paper addresses the problem of computational error modeling and analysis. Choosing different word-lengths for each functional unit in hardware implementations of numerical algorithms always results in an optimization problem of trading computational error with implementation costs. In this study, a symbolic noise analysis method is introduced for high-level synthesis, which is based on symbolic modeling of the error bounds where the error symbols are considered to be specified with a probability distribution function over a known range. The ability to combine word-length optimization with high-level synthesis parameters and costs to minimize the overall design cost is demonstrated using case studies.

REFERENCES

• 1: 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]
• 2: K.-I. Kum and W. Sung, "Combined word-length optimization and high-level synthesis of digital signal processing systems," IEEE Trans. CAD, vol. 20, no. 8, pp. 921--930, 2001.
• 3: George A. Constantinides, Word-length optimization for differentiable nonlinear systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.1, p.26-43, January 2006 [doi>10.1145/1124713.1124716]
• 4: George A. Constantinides , Peter Y. K. Cheung , Wayne Luk, Synthesis And Optimization Of DSP Algorithms, Kluwer Academic Publishers, Norwell, MA, 2004
• 5: C. Shi and R. W. Brodersen, "A perturbation theory on statistical quantization effects in fixed-point DSP with non-stationary inputs," in ISCAS '04, vol. 3, 2004, pp. III-373--6.
• 6: 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
• 7: Sanghamitra Roy , Prith Banerjee, An Algorithm for Trading Off Quantization Error with Hardware Resources for MATLAB-Based FPGA Design, IEEE Transactions on Computers, v.54 n.7, p.886-896, July 2005 [doi>10.1109/TC.2005.106]
• 8: B. Le-Gal, C. Andriamisaina, and E. Casseau, "Bit-width aware high-level synthesis for digital signal processing systems," in IEEE International SOC Conference, 2006, pp. 175--178.
• 9: Kyungtae Han , Brian L. Evans, Optimum wordlength search using sensitivity information, EURASIP Journal on Applied Signal Processing, v.2006 n.1, p.76-76, 01 January [doi>10.1155/ASP/2006/92849]
• 10: N. S. Nedialkov, V. Kreinovich, and S. A. Starks, "Interval arithmetic, affine arithmetic, taylor series methods: Why, what next?" Numerical Algorithms, vol. 37, no. 1--4, pp. 325--336, 2004.
• 11: D.-U. Lee, A. Abdul-Gaffar, R. C. C. Cheung, O. Mencer, W. Luk, and G. A. Constantinides, "Accuracy-guaranteed bit-width optimization," IEEE Trans. CAD, vol. 25, no. 10, pp. 1990--2000, 2006.
• 12: Yu Pu , Yajun Ha, An automated, efficient and static bit-width optimization methodology towards maximum bit-width-to-error tradeoff with affine arithmetic model, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118500]
• 13: 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]
• 14: Nobuhiro Doi , Takashi Horiyama , Masaki Nakanishi , Shinji Kimura, Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E89-A n.12, p.3427-3434, December 2006 [doi>10.1093/ietfec/e89-a.12.3427]
• 15: Alan V. Oppenheim , Ronald W. Schafer , John R. Buck, Discrete-time signal processing (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 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: D. Berleant, "Automatically verified reasoning with both intervals and probability density functions," Interval Computations, no. 2, pp. 48--70, 1993.
• 18: J. A. Lopez, C. Carreras, and O. Nieto-Taladriz, "Improved interval-based characterization of fixed-point LTI systems with feedback loops," IEEE Trans. CAD, vol. 26, no. 11, pp. 1923--1933, 2007.
• 19: A. Ahmadi and M. Zwolinski, "Multiple-width bus partitioning approach to datapath synthesis," in ISCAS '07: IEEE International Symposium on Circuits and Systems, 2007., May 2007, pp. 2994--2997.
• 20: Arash Ahmadi , Mark Zwolinski, Symbolic noise analysis approach to computational hardware optimization, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391573]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES

General Terms:
Algorithms, Design

Keywords:
computational error, computer arithmetic, high level synthesis, word-length optimization