Dynamic range estimation for nonlinear systems

ABSTRACT

It has been widely recognized that the dynamic range information of an application can be exploited to reduce the datapath bitwidth of either processors or ASICs, and therefore the overall circuit area, delay and power consumption. While recent advances in analytical dynamic range estimation can deliver results accurate enough to account for both spatial and temporal correlation, the reported methods are only valid for linear systems. In this paper, we use a powerful mathematical tool, called polynomial chaos, which enables not only the orthogonal decomposition of random processes, but also the propagation of random processes through nonlinear systems with difficult constructs such as multiplications, divisions and conditionals. We show that when applied to interesting nonlinear applications such as adaptive filters, polynomial filters and rational filters, this method can produce complete, accurate statistics of each internal variable, thereby allowing the synthesis of bitwidth with the desired tradeoff between circuit performance and signal-to-noise ratio.

REFERENCES

• 1: [1] S. Mahlke, R. Ravindran, M. Schlansker, R. Schreiber, and T. Sherwood. Bitwidth cognizant architecture synthesis of custom hardware accelerators. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(11):1355-1371, November 2001.
• 2: 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
• 3: Alberto Garcia-Ortiz , Lukusa Kabulepa , Tudor Murgan , Manfred Glesner, Moment-Based Power Estimation in Very Deep Submicron Technologies, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.107, November 09-13, 2003 [doi>10.1109/ICCAD.2003.98]
• 4: 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]
• 5: Bin Wu , Jianwen Zhu , Farid N. Najm, An analytical approach for dynamic range estimation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996699]
• 6: [6] V. J. Mathews and G. L. Sicuranza. Polynomial Signal Processing. John Wiley & Sons, New York, 2000.
• 7: Yun Cao , Hiroto Yasuura, A system-level energy minimization approach using datapath width optimization, Proceedings of the 2001 international symposium on Low power electronics and design, p.231-236, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383142]
• 8: [8] K. Kum and W. Sung. Combined word-length optimization and high-level synthesis of digital signal processing systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(8):921-930, August 2001.
• 9: 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]
• 10: 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]
• 11: [11] L. B. Jackson. On the interaction of roundoff noise and dynamic range in digital filters. Bell System Technical Journal, 49:159-184, February 1970.
• 12: Joan Carletta , Robert Veillette , Frederick Krach , Zhengwei Fang, Determining appropriate precisions for signals in fixed-point IIR filters, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775998]
• 13: Roger G. Ghanem , Pol D. Spanos, Stochastic finite elements: a spectral approach, Springer-Verlag New York, Inc., New York, NY, 1991
• 14: [14] A. Papoulis. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, New York, NY, 2nd edition, 1984.
• 15: Olivier P. Le Maitre , Omar M. Kino , Habib N. Najm , Roger G. Ghanem, A stochastic projection method for fluid flow. I: basic formulation, Journal of Computational Physics, v.173 n.2, p.481-511, November 1, 2001 [doi>10.1006/jcph.2001.6889]
• 16: [16] J. C. Park and M. Schlansker. On predicated execution. Tech. Report. HPL-91-58, HP Laboratories, May 1991.
• 17: Viraphol Chaiyakul , Daniel D. Gajski , Loganath Ramachandran, High-level transformations for minimizing syntactic variances, Proceedings of the 30th international conference on Design automation, p.413-418, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164956]
• 18: [18] I. T. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, 2002.
• 19: Arne Dür, On the Optimality of the Discrete Karhunen--Loève Expansion, SIAM Journal on Control and Optimization, v.36 n.6, p.1937-1939, Nov. 1998 [doi>10.1137/S0363012997315750]
• 20: Robert H. Shumway , David S. Stoffer, Time Series Analysis and Its Applications (Springer Texts in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 21: [21] P. Hall. The Bootstrap and Edgeworth Expansion. Springer-Verlag, Berlin/New York, NY, 1992.