Efficient latch optimization using exclusive sets

ABSTRACT

Controller circuits synthesized from high-level languagesoften have many more latches than the minimum,with a resulting sparse reachable state space thathas a particular structure. We propose an algorithmthatexploits this structure to remove latches. The reachablestate set (RSS) is much easier to compute for the new,smaller circuit and can be used to efficiently computethe RSS of the original. Thus we provide a method forobtaining the RSS, and two different initial implementationsfrom which to begin logic optimization.

REFERENCES

• 1: G. Berry. Esterel on hardware. Philosophical Transactions Royal Society of London A, 339:87-104, 1992.
• 2: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 3: C. Berthet, O. Coudert, and J.C. Madre. New Ideas on Symbolic Manipulations of Finite State Machines. In Proc oflC- CAD, October 1990.
• 4: Hyunwoo Cho , Gary D. Hachtel , Enrico Macii , Massimo Poncino , Fabio Somenzi, A Structural Approach to State Space Decomposition for Approximate Reachability Analysis, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.236-239, October 10-12, 1994
• 5: M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and Company, 1979.
• 6: B. Lin and A. Richard Newton. Exact Redundant State Registers Removal Based on Binary Decision Diagrams. In Proc of the International Workshop on Logic Synthesis, may 1991.
• 7: Ellen M. Sentovich , Horia Toma , Gérard Berry, Latch optimization in circuits generated from high-level descriptions, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.428-435, November 10-14, 1996, San Jose, California, United States
• 8: Ellen Sentovich , Kanwar Jit Singh , Cho W. Moon , Hamid Savoj , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Sequential Circuit Design Using Synthesis and Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.328-333, October 11-14, 1992
• 9: Thomas R. Shiple , Gerard Berry , Herve Touati, Constructive Analysis of Cyclic Circuits, Proceedings of the 1996 European conference on Design and Test, p.328, March 11-14, 1996
• 10: G. Stalmarck. A system for determining propositional logic theorems by applying values and rules to triplets that are generated from a formula. In U.S. patent 5 276 897, 1989.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Advanced technologies

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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