Exact minimum-width transistor placement without dual constraint for CMOS cells

ABSTRACT

This paper proposes flat and hierarchical approaches for generating a minimum-width transistor placement of CMOS cells in presence of non-dual P and N type transistors. Our approaches are the first exact method which can be applied to CMOS cells with any types of structure. We formulate the transistor placement problem into Boolean Satisfiability (SAT) problem considering the P and N type transistors individually. The experimental results show that our flat approach generates smaller width placement for 29 out of 103 dual cells than that of the conventional method, and the width of only 3 out of 147 cells solved by our hierarchical approach are larger than that of the flat approach. Using the hierarchical approach, 81% of 340 cells in an industrial standard-cell library of 90 nm technology are solved within one hour for each cell, whereas 32% using the conventional exact method.

REFERENCES

• 1: Mohan Guruswamy , Robert L. Maziasz , Daniel Dulitz , Srilata Raman , Venkat Chiluvuri , Andrea Fernandez , Larry G. Jones, CELLERITY: a fully automatic layout synthesis system for standard cell libraries, Proceedings of the 34th annual conference on Design automation, p.327-332, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266126]
• 2: abraCAD Documentation, Synopsys, Inc., 2003.
• 3: Progenesis Guide, Prolific, Inc., 2003.
• 4: Robert L. Maziasz , John P. Hayes, Exact width and height minimization of CMOS cells, Proceedings of the 28th conference on ACM/IEEE design automation, p.487-493, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127717]
• 5: Avaneendra Gupta , John P. Hayes, Width minimization of two-dimensional CMOS cells using integer programming, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.660-667, November 10-14, 1996, San Jose, California, United States
• 6: T. Uehara and W. M. vanCleemput, "Optimal Layout of CMOS Functional Arrays," IEEE Trans. on Computers, vol. C-30, No. 5, pp. 305--312, May 1981.
• 7: Tetsuya Iizuka , Makoto Ikeda , Kunihiro Asada, High speed layout synthesis for minimum-width CMOS logic cells via Boolean satisfiability, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.149-154, January 27-30, 2004, Yokohama, Japan
• 8: Fadi A. Aloul , Arathi Ramani , Igor L. Markov , Karem A. Sakallah, Generic ILP versus specialized 0-1 ILP: an update, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.450-457, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774638]
• 9: Matthew W. Moskewicz , Conor F. Madigan , Ying Zhao , Lintao Zhang , Sharad Malik, Chaff: engineering an efficient SAT solver, Proceedings of the 38th conference on Design automation, p.530-535, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379017]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

General Terms:
Algorithms, Design

Keywords:
boolean satisfiability, exact minimum-width transistor placement, non-dual