M32: a constructive multilevel logic synthesis system

ABSTRACT

We describe a new constructive multilevel logic synthesis system that integrates the traditionally separate technology-independent and technology-dependent stages of modern synthesis tools. Dubbed M32, this system is capable of generating circuits incrementally based on both functional as well as structural considerations. This is achieved by maintaining a dynamic structural representation of the evolving implementation and by refining it through progressive introduction of gates from a target technology library. Circuit construction proceeds from the primary inputs towards the primary outputs. Preliminary experimental results show that circuits generated using this approach are generally superior to those produced by multi-stage synthesis.

REFERENCES

• 1: P. Abouzeid , K. Sakouti , G. Saucier , F. Poirot, Multilevel synthesis minimizing the routing factor, Proceedings of the 27th ACM/IEEE conference on Design automation, p.365-368, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123307]
• 2: K. Bartlett, W. Cohenand A. de Geus, andG. Hachtel. Synthesis and optimization of multilevel logic under timing constraints. ZEEE Trans. CAD ZC, CAD-5 1986.
• 3: R. Brayton, E. Detjens, S. Krishna et al. Multiple-level optimization system. In Proc. ZCCAD, Nov. 1986.
• 4: R.K. Brayton, G. D. Hachtel, L. A. Hemachandra et al. A comparison of logic minimization strategies using ESPRESSO. In Proc. IEEE lnternSymp. Circ. Systems, pp. 42--48, May 1982.
• 5: R.K. Brayton and C. McMullen. Synthesis and optimization of multistage logic. InProc. ZCCD, pp. 23-28, 1984.
• 6: 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
• 7: R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang. MIS: A multiple-level logic optimization system. IEEETCADZC, 6:1062-1081,Nov. 1987.
• 8: Cascade Design Automation, Bellevue, WA 981506.EP- OCH User' sManual, v er.3.2 ,1995.
• 9: E. Davidson. An algorithm for NAND decomposition under network constraints. ZEEETC, C-18(12):1098-1109, Dec. 1969.
• 10: E. Detjens, G. Gannot, R. Rudell, et al. Technology mapping in MIS. InProc. ZCCAD, pp. 116-119, Nov. 1987.
• 11: Dietmeyer, Logic design of digital systems, Allyn & Bacon, Inc., Needham Heights, MA, 1988
• 12: E.M. Sentovich et. al. SIS: A system for sequential circuit synthesis. Technical ReportUCB/ERL M92/41, UC Berkeley, Electronics Research Laboratory, May 1992.
• 13: J. P. Fishburn, LATTIS: an iterative speedup heuristic for mapped logic, Proceedings of the 29th ACM/IEEE conference on Design automation, p.488-491, June 08-12, 1992, Anaheim, California, United States
• 14: 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
• 15: G. Hachtel, R. M. lacoby, K. Keutzer et al. On properties of algebraic transformations and the synthesis ofmultifault-irredundant circuits. ZEEE TCAD ZC, 11(3):313-321, March 1992.
• 16: 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]
• 17: Kurt Keutzer , A. Richard Newton , Narendra Shenoy, The future of logic synthesis and physical design in deep-submicron process geometries, Proceedings of the 1997 international symposium on Physical design, p.218-224, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267725]
• 18: V.N. Kravets and K.A. Sakallah. Constructive multilevel logic synthesis under properties of boolean algebra. Technical Report CSE-TR-359-98, March 1998.
• 19: Eric Lehman , Yosinori Watanabe , Joel Grodstein , Heather Harkness, Logic decomposition during technology mapping, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.264-271, November 05-09, 1995, San Jose, California, United States
• 20: P. McGeer, R. Brayton, and A. Sangiovanni-Vincentelli. Performance enhancement through the generalized bypass transform. In Proc. ZCCAD, pp. 184-187, Nov. 1991.
• 21: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 22: 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]
• 23: Massoud Pedram , Narasimha Bhat, Layout driven technology mapping, Proceedings of the 28th conference on ACM/IEEE design automation, p.99-105, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127635]
• 24: G. Saucier, J. Fron, and P. Abouzied. Lexicographical expressions of boolean functions with applications to multilevel synthesis. ZEEE TCADZC, 12: 1642-1654, Nov. 1993.
• 25: P.R. Schneider and D. L. Dietmeyer. An algorithm for synthesis of multiple-output combinational logic. IEEE TC, C- 17(2):117-128, Feb. 1968.
• 26: K. Scott and K. Keutzer. Improving cell libraries for synthesis. In Proc. IEEE Custom Integrated CircuitLConf., pp. 721-724, 1994.
• 27: Kanwar Jit Singh , Alberto Sangiovanni-Vincentelli, A heuristic algorithm for the fanout problem, Proceedings of the 27th ACM/IEEE conference on Design automation, p.357-360, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123303]
• 28: H.J. Touati, H. Savoj, and R. KBrayton. Delay optimization of combinational logic circuits and partial collapsing. In Proc. 28th DAC., pp. 188-191, June 1991.
• 29: Hirendu Vaishnav , Massoud Pedram, Minimizing the routing cost during logic extraction, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.70-75, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217509]
• 30: S. Yang. Logicsynthesisandoptimizationbenchmarksuser guide-version3.0. MCNC, Research Triangle Park, NC, January 1991.
• 31: Ko Yoshikawa , Hiroshi Ichiryu , Hisato Tanishita , Sigenobu Suzuki , Nobuyoshi Nomizu , Akira Kondoh, Timing optimization on mapped circuits, Proceedings of the 28th conference on ACM/IEEE design automation, p.112-117, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127639]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

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

  J. Computer Applications

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

Keywords:
congestion, global routing, quadratic placement, relaxed pins, routing models, supply-demand