Multi-level logic synthesis using communication complexity

ABSTRACT

We present a new multi-level logic synthesis technique based on minimizing communication complexity. Intuitively, we believe this approach is viable because for many types of circuits lower bounds on the area needed to implement those circuits have been obtained considering only communication complexity. It performs especially well for functions which are hierarchically decomposable (e.g., adders, parity generators, comparators, etc.). Unlike many other multi-level logic synthesis techniques, a lower bound can be computed to determine how well the synthesis was performed. We also present a new multi-level logic synthesis program based on the techniques described for reducing communication complexity.

REFERENCES

• BOI: J. A. Beekman , R. M. Owens , M. J. Irwin, Mesh arrays and LOGICIAN: a tool for their efficient generation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.357-362, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37942]
• BHJ: Bostick, D, et.al., The Boulder Optimal Logic Design System, Proc. of ICCAD, pp. 62-69, Nov. 1987.
• BHM: 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
• BRS: Brayton, R., R. Rudell, et.al., M/S: A Multiple-Level Logic Optimization System, IEEE Trans. on CAD, CAD-6, No. 6, pp. 1062-1081, Nov. 1987.
• DSA: DeMichelli G., A. Sangiovanni-Vinc:entelli, and Antognetti, Eds., Design Systems for VLSI Circuits, Kluwer, 1987.
• DGS: Pavol Duris , Zvi Galil , Georg Schnitger, Lower bounds on communication complexity, Information and Computation, v.73 n.1, p.1-22, April 1987 [doi>10.1016/0890-5401(87)90037-X]
• GBD: David Gregory , Karen Bartlett , Aart de Geus , Gary Hachtel, SOCRATES: a system for automatically synthesizing and optimizing combinational logic, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.79-85, July 1986, Las Vegas, Nevada, United States
• ISH: shidawa, J., et.al., A Rule Based Logic Reorganization System - LORES~, Proc. of IC'CD, pp. 262-266, Oct. 1988.
• Keu: 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]
• LBK: Lisanke, R., et.al., McMAP: A Fast Technology Mapping Procedure for Multi-Level Logic Synthesis, Proc. of lCCD, pp. 252-256, Oct. 1988.
• MeS: Kurt Mehlhorn , Erik M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.330-337, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802208]
• Yao: Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802483]

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.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

General Terms:
Algorithms, Design