Wave-steering one-hot encoded FSMs

ABSTRACT

In this paper we address the problem of pipelining FSMs by extending wave-steering scheme from combinational to sequential realm. A unified approach employs direct mapping of State Transition Graph into a circuit realization. Experimental result on MCNC benchmarks show performance improvement of 2 to 4 times at the cost of an average area increase of 2.9 times.

REFERENCES

• 1: E Ashar, S. Devadas and A.R.Newton: Optimum and Heuristic Algorithm for an Approach to Finite State Machines Decomposition, IEEE TCAD, March 1991.
• 2: L. Benini, E. Macii, M. Poncino, and G. De Micheli: Telescopic Units: A New Paradigm for Performance Optimization of VLSI Designs, IEEE TCAD vol. 17 no. 3, March 1998.
• 3: V. Bertacco, et al.: Decision Diagrams and Pass Transistor Logic Synthesis, IWLS'97, Lake Tahoe, May 1997.
• 4: Premal Buch , Amit Narayan , A. Richard Newton , A. Sangiovanni-Vincentelli, Logic synthesis for large pass transistor circuits, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.663-670, November 09-13, 1997, San Jose, California, United States
• 5: C. Chao and H.H. Loomis: High Rate Realization of Finite- State Machines, IEEE Trans. on Comp. vol. C-24, July 1975.
• 6: G. De Micheli: Synchronous Logic Synthesis: Algorithms for cycle time minimization, IEEE TCAD, Jan 1991.
• 7: G. Fettweis and H. Meyr: Parallel Viterbi decoding by breaking the compare-select feedback bottleneck, in Proc. IEEE Int. Conf. Communications, June 1989.
• 8: A.D. Friedman: Feedback in Synchronous sequential Switching Circuits, IEEE Trans. on Comp. vol EC-15, June 1966.
• 9: Juris Hartmanis, Algebraic structure theory of sequential machines (Prentice-Hall international series in applied mathematics), Prentice-Hall, Inc., Upper Saddle River, NJ, 1966
• 10: Andre Hertwig , Hans-Joachim Wunderlich, Fast Controllers for Data Dominated Applications, Proceedings of the 1997 European conference on Design and Test, p.84, March 17-20, 1997
• 11: H.-D. Lin, D.G. Messerschmitt: Finite state machine has unlimited concurrency. IEEE Transactions on Circuits and Systems, vol.38, (no.5), May 1991.
• 12: Arindam Mukherjee , Ranganathan Sudhakar , Malgorzata Marek-Sadowska , Stephen I. Long, Wave steering in YADDs: a novel non-iterative synthesis and layout technique, Proceedings of the 36th ACM/IEEE conference on Design automation, p.466-471, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309981]
• 13: A. Mukherjee, M. Marek-Sadowska, S.I. Long: Wave Pipelining YADDs, CICC'99, San Diego, 1999.
• 14: M. Shamanna, K. Cameron, S.R. Whitaker: Multiple-input, Multiple-output Pass Transistor Logic, Int'l J. Electronics vol. 79 n. 1, July 1995.
• 15: K. Taki: A Survey for Pass-Transistor Logic Technologies, ASP-DAC'98, Yokohama, February 1998.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

  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)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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