Sequence compaction for probabilistic analysis of finite-state machines

ABSTRACT

The objective of this paper is to provide aneffective technique for accurate modeling of the externalinput sequences that affect the behavior of Finite StateMachines (FSMs). The proposed approach relies on adaptivemodeling of binary input streams as Markov sources of fixed-order.The input model itself is derived through a one-passtraversal of the input sequence and can be used to generatean equivalent sequence, much shorter in length compared tothe original sequence. The compacted sequence can besubsequently used with any available simulator to derive thesteady-state and transition probabilities, and the total powerconsumption in the target circuit. As the results demonstrate,large compaction ratios of orders of magnitude can beobtained without a significant loss (less than 3% on average)in the accuracy of estimated values.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: 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.
• 5: S. Devadas and A.R. Newton, 'Decomposition and factorization of Sequential Finite State Machines', in IEEE Trans. on Computer-Aided Design of Integrated Circuits, vol.8, No. 11, pp. 1206-1217, Nov. 1989.
• 6: T.E. Harris, 'On Chains of Infinite Order', in Pacific J. Math., vol. 5, pp. 707-724, 1955.
• 7: 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.
• 8: D. Marculescu, R. Marculescu, and M. Pedram, 'FSM Analysis Using High-Order Markov Models', Technical Report CENG 97-08, Univ. of Southern California, Oct. 1996.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

  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)

General Terms:
Design, Measurement, Performance, Reliability, Theory