A stimulus-free graphical probabilistic switching model for sequential circuits using dynamic bayesian networks

ABSTRACT

We propose a novel, nonsimulative probabilistic model for switching activity in sequential circuits, capturing both spatio-temporal correlations at internal nodes and higher order temporal correlations due to feedback. This model, which we refer to as the temporal dependency model (TDM), can be constructed from the logic structure and is shown to be a dynamic Bayesian network. Dynamic Bayesian networks are extremely powerful in modeling high order temporal, as well as spatial, correlations; TDM is an exact model for the underlying conditional independencies. The attractive feature of this graphical representation of the joint probability function is not only that it makes the dependency relationships amongst nodes explicit, but it also serves as a computational mechanism for probabilistic inference. We report average errors in switching probability of 0.006, with errors tightly distributed around mean error values, on ISCAS'89 benchmark circuits involving up to 10000 signals.

REFERENCES

• 1: Sanjukta Bhanja , N. Ranganathan, Dependency preserving probabilistic modeling of switching activity using bayesian networks, Proceedings of the 38th conference on Design automation, p.209-214, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378465]
• 2: Sanjukta Bhanja , N. Ranganathan, Swtiching activity estimation of VLSI circuits using Bayesian networks, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.4, p.558-567, August 2003 [doi>10.1109/TVLSI.2003.816144]
• 3: Bhanja, S. and Ranganathan, N. 2004. Cascaded Bayesian inferencing for switching activity estimation with correlated inputs. IEEE Trans. VLSI Syst. 12, 12 (Dec.), 1387--1397.
• 4: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 5: Chen, Z. and Roy, K. 1997. An efficient statistical method to estimate average power in sequential circuits considering input sensitivities. In Proceedings of the ASIC Conference and Exhibit, 189--193.
• 6: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan , David J. Spiegelhater, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 7: Ding, C. S., Tsui, C. Y., and Pedram, M. 1998. Gate-Level power estimation using tagged probabilistic simulation. IEEE Trans. Comput. Aided Des. Integrated Circuits Syst. 17, 11 (Nov.), 1099--1107.
• 8: Ercolani, S., Favalli, M., Damiani, M., Olivo, P., and Ricco, B. 1992. Testability measures in pseudorandom testing. IEEE Trans. CAD 11, 794--800.
• 9: Genie 2006. Graphical network interface. url: http://www.sis.pitt.edu/genie/genie2.
• 10: Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Probabilistic analysis of large finite state machines, Proceedings of the 31st annual conference on Design automation, p.270-275, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196374]
• 11: Henrion, M. 1988. Propagation of uncertainty in Bayes' networks by probabilistic logic sampling. In Uncertainty in Artificial Intelligence. Elsevier Science, New York, 149--163.
• 12: Hugin. 2006. Hugin. url: http://www.hugin.com/.
• 13: Kjaerulff, U. 1995. Dhugin: A computational system for dynamic time-sliced Bayesian networks. Int. J. Forecasting 11, 89--111.
• 14: Joseph N. Kozhaya , Farid N. Najm, Power estimation for large sequential circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.2, p.400-407, April 2001 [doi>10.1109/92.924063]
• 15: S. Manich , J. Figueras, Maximizing the weighted switching activity in combinational CMOS circuits under the variable delay model, Proceedings of the 1997 European conference on Design and Test, p.597, March 17-20, 1997
• 16: Diana Marculescu , Radu Marculescu , Massoud Pedram, Theoretical bounds for switching activity analysis in finite-state machines, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.3, p.335-339, June 2000 [doi>10.1109/92.845899]
• 17: Marculescu, R., Marculescu, D., and Pedram, M. 1998. Probabilistic modeling of dependencies during switching activity analysis. IEEE Trans. Comput. Aided Des. Integrated Circuits Syst. 17, 2 (Feb.), 73--83.
• 18: Marculescu, R., Marculescu, D., and Pedram, M. 1999. Sequence compaction for power estimation: Theory and practice. IEEE Trans. Comput. Aided Des. Integrated Circuits Syst. 18, 7, 973--993.
• 19: Murphy, K. P., Weiss, Y., and Jordan, M. I. 1999. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the Conference on Uncertainty in AI, 467--475.
• 20: Farid N. Najm , Shashank Goel , Ibrahim N. Hajj, Power estimation in sequential circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.635-640, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217602]
• 21: Najm, F. N. 1993. Transition density: A new measure of activity in digital circuits. IEEE Trans. Comput. Aided Des. Integrated Circuits Syst. 12, 2 (Feb.), 310--323.
• 22: David Nguyen , Abhijit Davare , Michael Orshansky , David Chinnery , Brandon Thompson , Kurt Keutzer, Minimization of dynamic and static power through joint assignment of threshold voltages and sizing optimization, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871545]
• 23: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: Shiva Shankar Ramani , Sanjukta Bhanja, Any-time probabilistic switching model using bayesian networks, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013263]
• 25: Rejimon, T. and Bhanja, S. 2006. A timing-aware probabilistic model for single-event-upset analysis. IEEE Trans. VLSI Syst.
• 26: Vikram Saxena , Farid N. Najm , Ibrahim N. Hajj, Estimation of state line statistics in sequential circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.455-473, July 2002 [doi>10.1145/567270.567275]
• 27: Ashish Srivastava , Dennis Sylvester , David Blaauw, Power minimization using simultaneous gate sizing, dual-Vdd and dual-Vth assignment, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996777]
• 28: Stamoulis, G. I. 1996. A Monte-Carlo approach for the accurate and efficient estimation of average transition probabilities in sequential logic circuits. In Proceedings of the IEEE Custom Integrated Circuits Conference, 221--224.
• 29: Chi-Ying Tsui , José Monteiro , Massoud Pedram , Srinivas Devadas , Alvin M. Despain , Bill Lin, Power estimation methods for sequential logic circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.404-416, Sept. 1995 [doi>10.1109/92.406998]
• 30: Yuan, C. and Druzdzel, M. J. 2003. An importance sampling algorithm based on evidence pre-propagation. In Proceedings of the 19th Annual Conference on Uncertainty on Artificial Intelligence, 624--631.
• 31: Li-Pen Yuan , Chin-Chi Teng , Sung-Mo Kang, Statistical estimation of average power dissipation in sequential circuits, Proceedings of the 34th annual conference on Design automation, p.377-382, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266175]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Theory

Keywords:
Dynamic Bayesian networks, TDM, sequential circuits