Stochastic sequential machine synthesis with application to constrained sequence generation

ABSTRACT

In power estimation, one is faced with two problems: (1) generating input vector sequences that satisfy a given statistical behavior (in terms of signal probabilities and correlations among bits); (2) making these sequences as short as possible so as to improve the efficiency of power simulators. Stochastic sequential machines (SSMs) can be used to solve both problems. In particular, this paper presents a general procedure for SSM synthesis and describes a new framework for sequence characterization to match designers' needs for sequence generation or compaction. Experimental results demonstrate that compaction ratios of 1–3 orders of magnitude can be obtained without much loss in accuracy of total power estimates.

REFERENCES

• 1: Paul H. Bardell , William H. McAnney , Jacob Savir, Built-in test for VLSI: pseudorandom techniques, Wiley-Interscience, New York, NY, 1987
• 2: Tan-Li Chou , Kaushik Roy , Sharat Prasad, Estimation of circuit activity considering signal correlations and simultaneous switching, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.300-303, November 06-10, 1994, San Jose, California, United States
• 3: DAVIS, A. 1961. Markov chains as random input automata. Am. Math. Monthly 68, 264-267.
• 4: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: A. Ghosh , S. Devadas , K. Keutzer , J. White, Estimation of average switching activity in combinational and sequential circuits, Proceedings of the 29th ACM/IEEE conference on Design automation, p.253-259, June 08-12, 1992, Anaheim, California, United States
• 7: GILL, A. 1962. Synthesis of probability transformers. J. Franklin Inst. 274, 1-19.
• 8: Arthur Gill, On a Weight Distribution Problem, with Application to the Design of Stochastic Generators, Journal of the ACM (JACM), v.10 n.1, p.110-121, Jan. 1963 [doi>10.1145/321150.321159]
• 9: 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]
• 10: KERNIGHAN, B. AND LIN, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. (Feb.), 291-307.
• 11: MARCULESCU, R., MARCULESCU, D., AND PEDRAM, M. 1998. Probabilistic modeling of dependencies during switching activity analysis. IEEE Trans. CAD/ICAS 17, 2 (Feb.), 73-83.
• 12: José Monteiro , Srinivas Devadas, Techniques for the power estimation of sequential logic circuits under user-specified input sequences and programs, Proceedings of the 1995 international symposium on Low power design, p.33-38, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224088]
• 13: Farid N. Najm, Transition density, a stochastic measure of activity in digital circuits, Proceedings of the 28th conference on ACM/IEEE design automation, p.644-649, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127744]
• 14: PAPOULIS, A. 1984. Probability, Random Variables and Stochastic Processes. McGraw-Hill, Inc., New York, NY.
• 15: Azaria Paz, Introduction to probabilistic automata (Computer science and applied mathematics), Academic Press, Inc., Orlando, FL, 1971
• 16: Massoud Pedram, Power minimization in IC design: principles and applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.3-56, Jan. 1996 [doi>10.1145/225871.225877]
• 17: RABIN, M. 1963. Probabilistic automata. Inf. Control 6, 230-245.
• 18: James A. Storer, Data compression: methods and theory, Computer Science Press, Inc., New York, NY, 1987
• 19: Chi-Ying Tsui , Massoud Pedram , Alvin M. Despain, Efficient estimation of dynamic power consumption under a real delay model, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.224-228, November 07-11, 1993, Santa Clara, California, United States
• 20: 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]
• 21: VON NEUMANN, J. 1956. Probabilistic logics and synthesis of reliable organisms from unreliable components. Ann. Math. Stud. 34, 43-98.
• 22: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory; Simulation
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded); Computability theory

General Terms:
Algorithms, Design, Performance, Theory