Multi-level logic simplification using don't cares and filters

ABSTRACT

Simplication of a multi-level network is used to perform transformations on parts of the network to obtain an alternate structure that is optimal with respect to area. A technique for obtaining such an optimal structure involves the use of two-level logic minimization on the components of the multi-level logic network. At each component, the structure of the network is captured by intermediate and fan-out don't care sets, which are utilized in the two-level minimization. However, the generation of all the don't cares yield very large sets for most networks and consequently the complete minimization of the components of the circuits require a very large amount of computer time. In this paper we describe algorithms to reduce the size of the don't care sets, so that only the portions that will be useful in minimization at each component of the circuit are retained. We develop both an exact filter and a heuristic filter that prove to be very effective for a large set of benchmark examples. Results show that our technique achieves the same quality as that obtained by doing complete minimizations at each component of the circuits but in much shorter time. This new approach to simplification of multi-level networks has been incorporated into the MIS (version 2.1) logic synthesis system.

REFERENCES

• 1: K. Bartlett, R. Brayton, G. Hachtel, R. Jacoby, C. Morrison, R. Kudell, A. Sangiovanni-Vincentelli, and A. Wang. Multi-level logic minimization using implicit don't cares. IEEE Transaclions on Computer-aided design, 7(6):723-740, June 1988.
• 2: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 3: Ft. Brayton, R. Rudell, A. Sangiovanni-VincentelIi, and A.R. Wang. MIS: A multiple-level logic optimization system. IEEE Transactions on Compuler-aided design, CAD-6(6)'1062-1081, November 1987.
• 4: A. Malik, R. Brayton, A. Newton, and A. Sangiovanni-Vincentelli. A modified approach to two-level minimization. In The Proceedings of the International Conference on Computer-Aided Design, I988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory