A Markov chain sequence generator for power macromodeling

ABSTRACT

In this paper, we present a novel sequence generator based on a Markov chain model. Specifically, we formulate the problem of generating a sequence of vectors with given average input probability p, average transition density d, and spatial correlation s as a transition matrix computation problem, in which the matrix elements are subject to constraints derived from the specified statistics. We also give a practical heuristic that computes such a matrix and generates a sequence of l n-bit vectors in O(nl + n²) time. Derived from a strongly mixing Markov chain, our generator yields binary vector sequences with accurate statistics, high uniformity, and high randomness. Experimental results show that our sequence generator can cover more than 99% of the parameter space. Sequences of 2,000 48-bit vectors are generated in less than 0.05 seconds, with average deviations of the signal statistics p, d, and s equal to 1.6%, 1.8%, and 2.8%, respectively.Our generator enables the detailed study of power macromodeling. Using our tool and the ISCAS-85 benchmark circuits, we have assessed the sensitivity of power dissipation to the three input statistics p, d, and s. Our investigation reveals that power is most sensitive to transition density, while only occasionally exhibiting high sensitivity to signal probability and spatial correlation. Our experiments also show that input signal imbalance can cause estimation errors as high as 100% in extreme cases, although errors are usually within 25%.

REFERENCES

• 1: M. Abramovici, M. A. Breuer, and A. D. Friedman. Digital Systems Tesing and Testable Design. IEEE Press, Piscataway, NJ, 1995.
• 2: V. D. Agrawal and S. C. Seth. Test Generation for VLSI Chips. Computer Society Press, Washington D.C., 1988.
• 3: William Aiello , S. Raj Rajagopalan , Ramarathnam Venkatesan, Design of practical and provably good random number generators, Journal of Algorithms, v.29 n.2, p.358-389, Nov. 1998 [doi>10.1006/jagm.1998.0952]
• 4: , L. Benini, A. Bogliolo, B. Riccó M. Barocc , G. de Micheli, Lookup Table Power Macro-Models for Behavioral Library Components, Proceedings of the IEEE Alessandro Volta Memorial Workshop on Low-Power Design, p.173, March 04-05, 1999
• 5: Guiseppe Bernacchia , Marios C. Papaefthymiou, Analytical macromodeling for high-level power estimation, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.280-283, November 07-11, 1999, San Jose, California, United States
• 6: L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
• 7: R. Burch, F. Najm, P. Yang, and T. Trick. A Monte-Carlo approach for power estimation. In IEEE Trans. VLSI Systems, pages 63--71, January 1993.
• 8: Zhanping Chen , Kaushik Roy, A power macromodeling technique based on power sensitivity, Proceedings of the 35th annual conference on Design automation, p.678-683, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277216]
• 9: Zhanping Chen , Kaushik Roy , Tan-Li Chou, Power sensitivity—a new method to estimate power dissipation considering uncertain specifications of primary inputs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.40-44, November 09-13, 1997, San Jose, California, United States
• 10: Roberto Corgnati , Enrico Macii , Massimo Poncino, Clustered Table-Based Macromodels for RTL Power Estimation, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.354, March 04-06, 1999
• 11: Chih-Shun Ding , Cheng-Ta Hsieh , Qing Wu , Massoud Pedram, Stratified random sampling for power estimation, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.576-582, November 10-14, 1996, San Jose, California, United States
• 12: Nicola Dragone , Roberto Zafalon , Carlo Guardiani , Cristina Silvano, Power invariant vector compaction based on bit clustering and temporal partitioning, Proceedings of the 1998 international symposium on Low power electronics and design, p.118-120, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280819]
• 13: F. Ferrandi , F. Fummi , E. Macii , M. Poncino , D. Sciuto, Power estimation of behavioral descriptions, Proceedings of the conference on Design, automation and test in Europe, p.762-766, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 14: S. Gupta. Power macromodeling for high level power estimation. Master Thesis, Univ. of Illinois, September 1997.
• 15: Subodh Gupta , Farid N. Najm, Power macromodeling for high level power estimation, Proceedings of the 34th annual conference on Design automation, p.365-370, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266171]
• 16: Subodh Gupta , Farid N. Najm, Analytical Model for High Level Power Modeling of Combinational and Sequential Circuits, Proceedings of the IEEE Alessandro Volta Memorial Workshop on Low-Power Design, p.164, March 04-05, 1999
• 17: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 18: P. Landman and J. Rabaey. Activity-sensitive architectural power analysis. In IEEE Trans. CAD, pages 571--587, June 1996.
• 19: Alberto Macii , Enrico Macii , Massimo Poncino , Riccardo Scarsi, Stream synthesis for efficient power simulation based on spectral transforms, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.3, p.417-426, June 2001 [doi>10.1109/92.929576]
• 20: D. Marculescu, R. Marculescu, and M. Pedram. Information theoretic measures for power analysis. In IEEE Trans. CAD, pages 599--609, June 1996.
• 21: Diana Marculescu , Radu Marculescu , Massoud Pedram, Stochastic sequential machine synthesis with application to constrained sequence generation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.658-681, July 2000 [doi>10.1145/348019.348566]
• 22: R. Marculescu, D. Marculescu, and M. Pedram. Sequence compaction for power estimation: Theory and practice. In IEEE Trans. CAD, pages 973--993, July 1999.
• 23: Ueli M. Maurer , James L. Massey, Perfect local randomness in pseudo-random sequences, Proceedings on Advances in cryptology, p.100-112, July 1989, Santa Barbara, California, United States
• 24: Silvio Micali , Claus-Peter Schnorr, Efficient, Perfect Random Number Generators, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.173-198, August 21-25, 1988
• 25: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 26: V. N. Yarmolik , S. N. Demidenko, Generation and application of pseudorandom sequences for random testing, John Wiley & Sons, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Input/output circuits

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion

General Terms:
Experimentation, Standardization, Theory