Hierarchical sequence compaction for power estimation

ABSTRACT

This paper presents an effective technique forcompacting a large sequence of input vectors into a muchsmaller one such that when the two sequences are applied toany circuit, the resulting power dissipations are nearly thesame. Specifically, this paper introduces the hierarchicalmodeling of Markov chains as a flexible framework forcapturing not only complex spatiotemporal correlations, butalso dynamic changes in the characteristics of the inputsequence. The new framework has a high degree ofadaptability, i.e. the hierarchical model is dynamically grownaccording to the sequence behavior. Experimental resultsdemonstrate that large compaction ratios can be obtainedwithout a significant loss in accuracy (less than 5% on average)of power estimates.

REFERENCES

• 1: EN. Najm, 'A Monte Carlo Approach for Power Estimation', IEEE Transactions on VLSI Systems, Vol. 1, No. 1, pp. 63-71, Mar. 1993.
• 2: Charlie X. Huang , Bill Zhang , An-Chang Deng , Burkhard Swirski, The design and implementation of PowerMill, Proceedings of the 1995 international symposium on Low power design, p.105-110, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224100]
• 3: E N. Najm, 'Transition Density: A New Measure of Activity in Digital Circuits', IEEE Transactions on CAD, Vol. 12, No.2, pp. 310- 323, Feb. 1993.
• 4: Radu Marculescu , Diana Marculescu , Massoud Pedram, Efficient power estimation for highly correlated input streams, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.628-634, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217601]
• 5: D. Marculescu, R. Marculescu, and M. Pedram, 'Information Theoretic Measures for Power Analysis', in IEEE Trans. on Computer-Aided Design of Integrated Circuits, vol. 15, No. 6, June 1996.
• 6: M. Nemani and F. Najm, 'Towards A High-Level Power Estimation Capability', in IEEE Trans. on Computer-Aided Design of Integrated Circuits, vol. 15, No. 6, June 1996.
• 7: Diana Marculescu , Radu Marculescu , Massoud Pedram, Stochastic sequential machine synthesis targeting constrained sequence generation, Proceedings of the 33rd annual conference on Design automation, p.696-701, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240650]
• 8: Chi-Ying Tsui , Radu Marculescu , Diana Marculescu , Massoud Pedram, Improving the efficiency of power simulators by input vector compaction, Proceedings of the 33rd annual conference on Design automation, p.165-168, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240549]
• 9: G. V. Ormack , R. N. S. Horspool, Data compression using dynamic Markov modelling, The Computer Journal, v.30 n.6, p.541-550, Dec. 1987
• 10: R. Marculescu, D. Marculescu, and M. Pedram, 'Adaptive Models for Input Data Compaction for Power Simulators', in Proc. Asia and South-Pacific Design Automation Conference, pp. 391-396, Japan, Jan. 1997.
• 11: A. Papoulis, 'Probability, Random Variables, and Stochastic Processes', McGraw-Hill Co., 1984.
• 12: J.W. Green and K.J. Supowit, 'Simulated Annealing without Rejected Moves', in Digest. of Intl. Conference on Computer Design, pp. 658-663, Oct. 1984.
• 13: Shi-Yu Huang , Kuang-Chien Chen , Kwang-Ting Cheng , Tien-Chien Lee, Compact vector generation for accurate power simulation, Proceedings of the 33rd annual conference on Design automation, p.161-164, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240548]
• 14: R. Marculescu, D. Marculescu, and M. Pedram, 'Vector Compaction Using Hierarchical Markov Models', Technical Report CENG 97-07, Univ. of Southern California.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  C. Computer Systems Organization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.1 Project and People Management
          Subjects: Systems analysis and design

General Terms:
Design, Measurement, Performance, Theory