Generalized matching from theory to application

ABSTRACT

We present a novel approach for post-mapping optimization. We exploit the concept of generalised matching, a technique that finds symbolically all possible matching assignments of library cells to a multi-output network specified by a Boolean relation. Several objectives are targeted: area minimization under delay constraints; power minimization under delay constraints; and unconstrained delay minimization. We describe the theory of generalized matching and the algorithmic optimization required for its efficient and robust implementation. A tool based on generalized matching has been implemented and tested on large examples of the MCNC'91 benchmark suite. We obtain sizable improvements in: speed (6% in average, up to 20.7%); area under speed constraints (13.7% an average, up to 29.5%); and power under speed constraints (22.3% in average, up to 38.1%).

REFERENCES

• 1: F. Somenzi et al., "Minimization of Boolean relations," in IS- CAS, pp. 738-473, 1989.
• 2: R. Brayton et al., "Multilevel logic synthesis," IEEE Proceedings, vol. 78, pp. 264-300, 1990.
• 3: H. Savoj et al., "Extracting local don't cares for network optimization," in ICCAD, pp. 514-517, 1991.
• 4: Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997 [doi>10.1145/264995.264996]
• 5: 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
• 6: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 7: K. Cheng et al., "Multi-level logic optimization by redundancy addition and removal," in Euro-DAC, pp. 373-377, 1993.
• 8: Wolfgang Kunz , Prem R. Menon, Multi-level logic optimization by implication analysis, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.6-13, November 06-10, 1994, San Jose, California, United States
• 9: Berhard Rohfleisch , Bernd Wurth , Kurt Antreich, Logic clause analysis for delay optimization, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.668-672, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217608]
• 10: Shih-Chieh Chang , Lukas P. P. P. van Ginneken , Malgorzata Marek-Sadowska, Fast Boolean optimization by rewiring, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.262-269, November 10-14, 1996, San Jose, California, United States
• 11: 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]
• 12: Y. Watanabe et al., "Permissible functions for multioutput components in combinational logic optimization," IEEE TCAD ICAS, vol. 15, no. 7, pp. 734-744, 1996.
• 13: R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States
• 14: F. Somenzi. The CUDD package User's guide. Version 1.0.5 1995.
• 15: S. Yang, "Logic Synthesis and Optimization Benchmarks User Guide Version 3.0," Tech. Rep. MCNC, 1991.
• 16: P. Vuillod , L. Benini , G. De Micheli, Re-mapping for low power under tight timing constraints, Proceedings of the 1997 international symposium on Low power electronics and design, p.287-292, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263354]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

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

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

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

Keywords:
Boolean relation, MCNC 91 benchmark suite, algorithmic optimization, area minimization, delay constraints, generalized matching, library cells, logic CAD, multi-output network, post-mapping optimization, power minimization, unconstrained delay minimization