Boolean matching for large libraries

ABSTRACT

Boolean matching tackles the problem whether a subcircuit of a boolean network can be substituted by a cell from a cell library. In previous approaches [7, 10, 8] each pair of a subcircuit and a cell is tested for NPN equivalence. This becomes very expensive if the cell library is large. In our approach the time complexity for matching a subcircuit against a library L is almost independent of the size of L. CPU time also remains small for matching a subcircuit against the huge set of functions obtained by bridging and fixing cell inputs; but the use of these functions in technology mapping is very profitable. Our method is based on a canonical representative for each NPN equivalence class. We show how this representative can be computed efficiently and how it can be used for matching a boolcan function against a set of library functions.

REFERENCES

• 1: R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A.R. Wang. MIS: A Multiple-Level Logic Optimization System. IEEE Transactions on Computer- Aided Design, CAD-6(6):1062-1081, November 1987.
• 2: E. Detjens, G. Ganot, A. Sangiovanni-Vincentelli, and A. Wang. Technology mapping in MIS. In Proceedings of the International Conference of Computer Aided Design, pages 116-119, 1987.
• 3: U. Hinsberger and R. Kolla. Matching a Boolean Function against a Set of Functions. Technical Report No. 185, Preprint-Reihe, Institut fiir Informatik, Universit,it W/irzburg, 1997.
• 4: U. Hinsberger and R. Kolla. TEMPLATE: a generic TEchnology Mapping PLATform. Technical Report No. 186, Preprint-Reihe, Institut ffir Informatik, Universit/it Wfirzburg, 1997.
• 5: U. Hinsberger , R. Kolla, Optimal technology mapping for single output cells, Proceedings of the Fifth Great Lakes Symposium on VLSI (GLSVLSI'95), p.14, March 16-18, 1995
• 6: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 7: Frédéric Mailhot , Giovanni De Micheli, Technology mapping using boolean matching and don't care sets, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 8: J. Mohnke and S. Malik. Permutation and Phase Independent Boolean Comparison. In Proceedings of the European Design Automation Conference (EDAC93), pages 86-92, 1993.
• 9: Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.620-625, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123421]
• 10: Hamid Savoj , Mário J. Silva , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Boolean matching in logic synthesis, Proceedings of the conference on European design automation, p.168-174, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 11: S. Yang. Logic Synthesis and Optimization Benchmarks User Guide (Version 3.0). Technical report, Microelectronics Center of North Carolina, P.O. Box 12889, Research Triangle Park, NC 27709, January 1991.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  J. Computer Applications

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

Keywords:
emulation, functional simulation, reconstruction, visibility