Approaches to multi-level sequential logic synthesis

ABSTRACT

In this paper, we present approaches to multi-level sequential logic synthesis — algorithms and techniques for the area and performance optimization of interconnected finite state machine descriptions. Interacting finite state machines are common in industrial chip designs. While optimization techniques for single finite state machines are relatively well developed, the problem of optimization across latch boundaries has received much less attention. Techniques to optimize pipelined combinational logic so as to improve area/throughout have been proposed. However, logic cannot be straightforwardly migrated across latch boundaries when the basic blocks are sequential rather than combinational circuits. We present new techniques for the exploitation of sequential don't cares in arbitrary, interconnected sequential machine structures. Exploiting these don't care sequences can result in significant improvements in area and performance. We address the problem of migrating logic across state machine boundaries so as to make particular machines less complex at the possible expense of making others more complex. This can be useful from both an area and performance point of view. We present new optimization algorithms that incrementally modify state machine structures across latch boundaries. We discuss the use of more global state machine decomposition and factorization algorithms for area optimization. Finally, we present experimental results using these algorithms on sequential circuits.

REFERENCES

• 1: D. B. Armstrong. A programmed algorithm for assigning internal codes to sequential machines. In {RE Transactions on Electron Computers, pages 466-472, August 1962.
• 2: R. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang. Mis: a multiple-level logic optimization system. In IEEE Transactions on CAD, pages 1062-1081, November 1987.
• 3: S. Devadas, II-K. T. Ma, A. R. Newton, and A. Sangiovanni-Vincentelli. Mustang: state assignment of finite state machines targeting multi-level logic implementations. In 1EEE Transactions on CAD, pages 1290-1300, December 1988.
• 4: S. Devadas and A. R. Newton. Decomposition and factorization of sequential finite state machines. In int'l Conference on Computer-Aided Design, November 1988.
• 5: Juris Hartmanis, Algebraic structure theory of sequential machines (Prentice-Hall international series in applied mathematics), Prentice-Hall, Inc., Upper Saddle River, NJ, 1966
• 6: C. E. Leiserson, F. M. Rose, and J. B. Saxe. Optimizing synchronous circuitry by retiming. In Proc. of Third CalTeeh Conference on VLSI, March 1983.
• 7: G. De Micheli. Symbolic design of combinational and sequential logic circuits implemented by twolevel macros. In IEEE Transactions on CAD, pages 597-616, September 1986.
• 8: G. De Micheli, R. K. Rrayton, and A. Sangiovanni- Vincentelli. Optimal state assignment of finite state machines. In IEEE Transactions on CAD, pages 269-285, July 1985.
• 9: M. C. Paul and S. H. Unger. Minimizing the number of states in incompletely specified sequential circuits. In IRE Transactions on Electronic Computers, pages 356-357, September 1959.

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.1 Design Styles
          Subjects: Combinational logic
      B.6.3 Design Aids
          Subjects: Optimization

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Management