A comparison of four two-dimensional gate matrix layout tools

ABSTRACT

A comparison of four layout tools is presented. The layout style is a two-dimensional gate matrix. The first layout tool discussed uses “standard” simulated annealing. Annealing on gate clusters instead of individual gates can be used to improve the layout results. Two different ways of determining good gate clusters for use in the annealing process are compared. The first way uses clusters derived from user specified gate hierarchies, while the second determines clusters based on gate connectivity. The fourth layout tool uses a decomposition scheme based on quadrisection. Layout results for a set of benchmark circuits are presented for each of the tools.

REFERENCES

• DuK: Dtmlop, A. and B. Kemighan, A Procedure for Placement of Standard-Cell VLSI Circuits, IEEE Trans on CAD, VCAD4-1, 92-98, 1985.
• FOI: Fuh, C-S, et.al., VLSI Layout Expectations, VLSI Technical Bulletin, V2-3, 57-64, 1987.
• Hi1: Hill, D., Sc2: A Hybrid Automatic Layout System, Proc oflCCAD, 172-174, Nov 1985.
• Hi2: Hill, D., Alternative Strategies for Applying Min-cut to VLSI Placement, Proc of ICCD, 440-444, Oct 1988.
• KeL: Kernighan, B. and S. Lin, An Efficient Heuristic Procedure for Partitioning Graphs, Bell System Tech. Journal, V49-2, 291-308, 1970.
• KGV: Kirkpatrick, S., et.al., Optimization by Simulated Annealing, Science, V220-4598, 671-680, May 1983.
• LiG: Lin, Y-L and D. Gajsld, LES: A Layout Expert System, 1EEE Trans on CAD, VCAD7-8, 868-876, 1988.
• LoL: Lopez, A. and H. 13aw, A Dense Gate Matrix Layout Method for MOS VLSI, Trans on Elec Devices, ED- 27-8, 1671-1675, 1980.
• MaG: Sivanarayana Mallela , Lov K. Grover, Clustering based simulated annealing for standard cell placement, Proceedings of the 25th ACM/IEEE conference on Design automation, p.312-317, June 12-15, 1988, Atlantic City, New Jersey, United States
• OwI: Owens, R.M. and M.J. Irwin, Clustering Based Simulated Annealing Sea-of-Transistor Layout Tools, CS- 88-09, PSU, also submitted to IEEE Trans on CAD.
• RoS: Romeo, F. and A. Sangiovarmi-Vincentelli, Probabilistic Hill Climbing Algorithms, Proc of the Chapel Hill Conf on VLS1, 393-419, May 1985.
• SeS: Sechen, C. and A. Sangiovanni-Vincentelli, The TimberWolf Placement and Routing Package, IEEE Journal of Solid-State Circuits, April 1985.
• SSK: Yoichi Shiraishi , Jun'ya Sakemi , Makoto Kutsuwada , Akira Tsukizoe , Takashi Satoh, A high packing density module generator for CMOS logic cells, Proceedings of the 25th ACM/IEEE conference on Design automation, p.439-444, June 12-15, 1988, Atlantic City, New Jersey, United States
• SuK: Suaris, P. and G. Kedem, Quadrisection: A New Approach to Standard Cell Layout, Proc of ICCAD, Nov 1987.
• TKH: Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, Proud: a fast sea-of-gates placement algorithm, Proceedings of the 25th ACM/IEEE conference on Design automation, p.318-323, June 12-15, 1988, Atlantic City, New Jersey, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout; Placement and routing

General Terms:
Algorithms, Design