CLIP: integer-programming-based optimal layout synthesis of 2D CMOS cells

ABSTRACT

A novel technique, CLIP, is presented for the automatic generation of optimal layouts of CMOS cells in the two-dimensional (2D) style. CLIP is based on integer-linear programming (ILP) and solves both the width and height minimization problems for 2D cells. Width minimization is formulated in a precise form that combines all factors influencing the 2D cell width—transistor placement, diffusion sharing, and vertical interrow connections—in a common problem space; this space is then searched in a systematic manner by the branch-and-bound algorithms used by ILP solvers. For height minimization, cell height is modeled accurately in terms of the horizontal wire routing density, and a minimum-height layout is found from among all layouts of minimum width. For exact width minimization alone, CLIP's run times are in seconds for large circuits with 30 or more transistors. For both height and width optimization, CLIP is practical for circuits with up to 20 transistors. To extend CLIP to larger circuits, hierarchical methods are necessary. Since CLIP is optimum under the modeling assumptions, its layouts are significantly better than those generated by other, heuristic, layout tools.

REFERENCES

• 1: Donald G. Baltus , Jonathan Allen, SOLO: a generator of efficient layouts from optimized MOS circuit schematics, Proceedings of the 25th ACM/IEEE conference on Design automation, p.445-452, June 12-15, 1988, Atlantic City, New Jersey, United States
• 2: Peter Barth, Logic-based 0-1 constraint programming, Kluwer Academic Publishers, Norwell, MA, 1995
• 3: BASARAN, B. AND RUTENBAR, R. 1996. Efficient area minimization for dynamic CMOS circuits. In Proceedings of the IEEE Conference on Custom Integrated Circuits (Santa Clara, CA), IEEE Press, Piscataway, NJ, 505-508.
• 4: Bulent Basaran , Rob A. Rutenbar, An O(n) algorithm for transistor stacking with performance constraints, Proceedings of the 33rd annual conference on Design automation, p.221-226, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240559]
• 5: CADENCE DESIGN SYSTEMS, INC., 1992. Virtuoso layout synthesizer tutorial and reference. Cadence Design Systems, Inc..
• 6: C. Y. Roger Chen, Transistor Chaining in CMOS Leaf Cells of Planar Topology, Proceedings of the 6th Great Lakes Symposium on VLSI, p.194, March 22-23, 1996
• 7: CHAKRAVARTY, S., HE, X., AND RAVI, S. S. 1991. Minimum area layout of series-parallel transistor networks is NP-hard. IEEE Trans. Comput.-Aided Des. 10, 6 (June), 770-782.
• 8: C. C. Chen , S.-L. Chow, The layout synthesizer: an automatic Netlist-to-Layout system, Proceedings of the 26th ACM/IEEE conference on Design automation, p.232-238, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74422]
• 9: Amit Chowdhary , John P. Hayes, Technology mapping for field-programmable gate arrays using integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.346-352, November 05-09, 1995, San Jose, California, United States
• 10: CPLEX OPTIMIZATION, INC., 1990. CPLEX documentation. CPLEX Optimization, Inc., Incline Village, NV.
• 11: FOURER, R., GAY, D. M., AND KERNIGHAN, B.W. 1993. AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, Boston, MA.
• 12: Avaneendra Gupta , Siang-Chun The , John P. Hayes, XPRESS: A Cell Layout Generator with Integrated Transistor Folding, Proceedings of the 1996 European conference on Design and Test, p.393, March 11-14, 1996
• 13: 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
• 14: Avaneendra Gupta , John P. Hayes, A Hierarchical Technique for Minimum-Width Layout of Two-Dimensional CMOS Cells, Proceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications, p.15, January 04-07, 1997
• 15: Avaneendra Gupta, Integer-programming-based layout synthesis of two-dimensional CMOS cells, University of Michigan, Ann Arbor, MI, 1997
• 16: Avaneendra Gupta , John P. Hayes, CLIP: an optimizing layout generator for two-dimensional CMOS cells, Proceedings of the 34th annual conference on Design automation, p.452-455, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266198]
• 17: Avaneendra Gupta , John P. Hayes, Optimal 2-D cell layout with integrated transistor folding, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.128-135, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288590]
• 18: Avaneendra Gupta , John P. Hayes, Near-Optimum Hierarchical Layout Synthesis of Two-Dimensional CMOS Cells, Proceedings of the 12th International Conference on VLSI Design - 'VLSI for the Information Appliance', p.453, January 10-13, 1999
• 19: HEINBUCH, D.V. 1988. CMOS3 Cell Library. Addison-Wesley, Reading, MA.
• 20: HER, T. W. AND WONG, D. F. 1995. On over-the-cell channel routing with cell orientation consideration. IEEE Trans. Comput.-Aided Des. 14 (June), 766-771.
• 21: HILL, D. 1985. Sc2: A hybrid automatic layout system. In Proceedings of the IEEE International Conference on Computer-Aided Design (Nov. 18-21), IEEE Computer Society Press, Los Alamitos, CA, 172-174.
• 22: HSIEH, Y. C., HWANG, C. Y., LIN, Y. L., AND HSU, Y. C. 1991. LiB: A CMOS cell compiler. IEEE Trans. Comput.-Aided Des. 10 (Aug.), 994-1005.
• 23: IBM CORP., 1992. Optimization subroutine library guide and reference (issue 1). Palo Alto Scientific Center, IBM Corp., Palo Alto, CA.
• 24: Jaewon Kim , S. M. Kang, A timing-driven data path layout synthesis with integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.716-719, November 05-09, 1995, San Jose, California, United States
• 25: MALAVASI, E. AND PANDINI, D. 1995. Optimum CMOS stack generation with analog constraints. IEEE Trans. Comput.-Aided Des. 14, 1, 107-122.
• 26: MAULIK, P., CARLEY, L., AND RUTENBAR, R.A. 1995. Integer programming based topology selection of cell-level analog circuits. IEEE Trans. Comput.-Aided Des. 14, 4 (Apr.).
• 27: MAZIASZ, R. L. AND HAYES, J. P. 1992. Layout Minimization of CMOS Cells. Kluwer Academic, Dordrecht, Netherlands.
• 28: Brian T. Murray , John P. Hayes, Testing ICs: Getting to the Core of the Problem, Computer, v.29 n.11, p.32-38, November 1996 [doi>10.1109/2.544235]
• 29: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 30: C.-L. Ong , J.-T. Li , C.-Y. Lo, GENAC: an automatic cell synthesis tool, Proceedings of the 26th ACM/IEEE conference on Design automation, p.239-244, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74423]
• 31: POIRIER, C.J. 1989. Excellerator: Custom CMOS leaf cell layout generator. IEEE Trans. Comput.-Aided Des. 8, 7 (July), 744-755.
• 32: R. L. Rivest , C. M. Fiduccia, A “GGreedy” channel router, Papers on Twenty-five years of electronic design automation, p.256-262, June 1988 [doi>10.1145/62882.62912]
• 33: TANI, K., IZUMI, K., KASHIMURA, M., MATSUDA, T., AND FUJII, T. 1991. Two-dimensional layout synthesis for large-scale CMOS circuits. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14, 1991), IEEE Computer Society Press, Los Alamitos, CA, 490-493.
• 34: T. Uehara , W. M. vanCleemput, Optimal layout of CMOS functional arrays, Papers on Twenty-five years of electronic design automation, p.182-191, June 1988 [doi>10.1145/62882.62902]
• 35: A. Josep Velasco , Xavier Marin , Jordi Carrabina , Rafael Peset Llopis, A Combined Pairing and Chaining Algorithm for CMOS Layout Generation, Proceedings of the 1996 European conference on Design and Test, p.609, March 11-14, 1996
• 36: WILLIAMS, H. P. 1985. Model Building in Mathematical Programming. John Wiley, New York, NY.
• 37: WIMER, S., PINTER, R. Y., AND FELDMAN, J.A. 1987. Optimal chaining of CMOS transistors in a functional cell. IEEE Trans. Comput.-Aided Des. 6 (Sept.), 795-801.
• 38: ZHANG, H. AND ASADA, K. 1993. An improved algorithm of transistors pairing for compact layout of non-series-parallel CMOS networks. In Proceedings of the Conference on Custom Integrated Circuits,

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Algorithms, Design, Theory

Keywords:
CMOS networks, circuit clustering, diffusion sharing, integer linear programming, integer programming, layout optimization, leaf cell synthesis, module generation, transistor chains, two-dimensional layout