Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-10-01
2003-04-15
Niebling, John F. (Department: 2812)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06550046
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to a method for the automated placement of cells in the generation of an automated layout of an integrated circuit, and more specifically to a method for the automated placement of cells in an integrated circuit layout that accommodates symmetry constraints that are often encountered in the layout of analog devices.
A number of techniques exist for the computer-aided design (CAD) and layout of integrated circuit devices. The integrated circuit device is first divided into a number of cells that can be used to implement the desired integrated circuit function. The cells can be, for example, an individual device, a capacitor, or, often, a plurality of transistors and other devices that make up a logic block. Most of the prior art techniques then involve the placement of the cells either in accordance with a trial and error method or in accordance with a mathematical algorithm. The known placement techniques usually handle the cells as rectangles and move and position the rectangular cells in such a manner to optimize the size of the integrated circuit layout.
Although the known automated layout techniques are not ideal, they are reasonably effective for providing a workable layout for digital circuits. Unfortunately, however, the known techniques are not practical or efficient for optimum layout of an analog integrated circuit. In addition to the obvious functional differences between analog and digital circuits, analog circuits differ from digital circuits in that an analog circuit layout often requires aspects of symmetry and device matching in order for the resulting integrated circuit to achieve optimum performance.
Known techniques for laying out integrated circuits are not efficient for laying out circuits requiring symmetry and matching. Dealing with symmetry and matching using the known automated layout techniques requires unacceptable amounts of computing time and/or computing power.
A need therefore existed for an improved method for the automated placement of cell in the generation of integrated circuit layouts, and especially for the automated placement of cells in the layout of analog circuits that require aspects of device symmetry and device matching.
BRIEF SUMMARY OF THE INVENTION
In accordance with one embodiment of the invention, a method is provided for the automated packing of an integrated circuit layout, and especially for the automated packing of an integrated circuit layout within which certain cells of the circuit must be symmetrically arranged. In accordance with one embodiment of the invention, the circuit to be designed is considered as a plurality of generally rectangular cells. From the plurality of cells making up the integrated circuit, a subset of cells that must exhibit symmetry are identified. Symmetry constraints are defined for the subset of symmetric cells. The packing of the cells, in accordance with one embodiment of the invention, is encoded as ordered sequence-pairs starting with an initial sequence-pair that is symmetric-feasible. The encoding is then optimized using simulated annealing, with each movement of cells during the annealing subject to the symmetry constraints.
REFERENCES:
Bourai, “Symmetry detection for automatic analog layout recycling”, IEEE Jan. 1999. pp. 5-8.*
Hatta, K. et al., “Solving the rectangular packing problem by an adaptive GA based on sequence-pair”, Jan. 1999, IEEE, pp. 181-184.*
Murata, H. et al., “Rectangule-packing based module placement”, Nov. 1995, IEEE, pp. 472-479.*
Malavasi, E. et al., “Automation of IC layout with analog constraints”, Aug. 1996, IEEE, pp. 923-942.*
F. Balasa, K. Lampaert, “Module Placement for Analog Layout Using the Sequence-Pair Representation,”Proc. 36thACM/IEEE Design Automation Conf., pp. 274-279, New Orleans. LA, Jun. 1999.
Y.-X Pang, F. Balasa, K. Lampaert, C.-K. Cheng, “Block Placement with Symmetry Constraints Based on the O-Tree Non-Slicing Representation,”Proc. 37thACM/IEEE Design Automation Conf., pp. 464-467, Los Angeles CA, Jun. 2000.
F. Balasa, K. Lamaert, “Symmetry Within the Sequence-Pair Representation in the Context of Placement for Analog Design,”IEEE Trans. On Comp.-Aided Design of Integrated Circuits and Systems, vol. 19, No. 7, pp. 721-731, Jul. 2000.
F. Balasa, “Modeling Non-Slicing Floorplans with Binary Trees,”Proc. IEEE Int. Conf. Comp.-Aided Design, pp. 13-16, San Jose CA, Nov. 2000.
F. Balasa, “Device-Level Placement for Analog Layout: An Opportunity for Non-Slicing Topological Representations,”,Proc. Asia South Pacific Design Automation Conf., pp. 281-286, Yokohama, Japan, Jan.-Feb. 2001.
F. Balasa, S.C. Maruvada, “Using Non-Slicing Topological Representations for Analog Placement,”IEICE Trans. On Fundamentals of Electronics, Communications and Computer Sciences(Special Section on VLSI Designa nd CAD Algorithms), Japan 2001.
IEEE Journal Article titled KOAN / ANAGRAM II: New Tools for Device-Level Analog Placement and Routing, by John M. Cohn, et al., 1991, pp. 330-342.
Article titled An O-Tree Representation of Non-Slicing Floorplan and Its Applications, by Pei-Ning Guo, et al., 1999, pp. 268-273.
IEEE Journal Article titled “A New Algorithmm for Floorplan Design”, by D.F. Wong and C.L. Liu, 1986, pp. 101-107.
IEEE Journal Article titled “Genetic Placement”, by James P. Cohoon and William D. Paris, 1987, pp. 956-964.
IEEE Journal Article titled “SALIM: A Layout Generation Tool for Analog ICs”, by M. Kayal, et al., 1988, pp. 7.5.1-7.5.4.
IEEE Journal Article titled GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization, by Jurgen M. Kleinhans, et al., 1991, pp. 356-365.
IEEE Journal Article titled “A Performance-Driven Placement Tool for Analog Integrated Circuits”, by Koen lampaert, et al., 1995, pp. 773-780.
Article titled “Module Placement for Analog Layout Using the Sequence-Pair Representation”, by Florin Balasa and Koen Lampaert, 1999, pp. 274-279.
IEEE Journal Article titled “Module Packing Based on the BSG-Structure and IC Layout”, by Shigetoshi Nakatake, et al., 1998, pp. 519-530.
Society for Industrial and Applied Mathematics Article titled “Orthogonal Packings in Two Dimensions”, by Brenda S. Baker, et al., 1980, pp. 846-855.
IEEE Journal Article titled “An Efficient Methodology for Symbolic Compaction of Analog IC's wiht Multiple Symmetry Constraints”, by Eric Felt, et al., 1992, pp. 148-153.
IEEE Journal Article titled “Automation of IC Layout with Analog Constraints”, by Enrico Malavasi, et al., 1996, pp. 923-942.
IEEE Journal Article titled “Quick Placement with Geometric Constraints”, by Enrico Malavasi, et al., 1997, pp. 561-564.
IEEE Journal Article titled “STAT: A Schematic to Artwork Translator for Custom Analog Cells”, by Stacy W. Mehranfar, 1990, pp. 30.2.1-30.2.3.
Article for IEEE Design Automoation Conference titled “Branch-and Bound Placement for Building Block Layout”, by Hidetoshi Onodera, et al., 1991, pp. 433-439.
IEEE Journal Article titled “ILAC: An Automated Layout Tool for Analog CMOS Circuits”, by Jef RijMenants, et al., 1989, pp. 417-423.
IEEE Journal Article titled “Efficient and Effective Placement for Very Large Circuits”, by Wern-Jieh Sun and Carl Sechen, 1995, pp. 349-359.
IEEE Journal Article titled “An Analytical Approach to Floorplan Design and Optimization”, by Suphachai Sutanthavibul, et al., 1991, pp. 761-769.
IEEE Journal Article titled “An Analytical Approach to Floorplanning for Hierarchical Building Blocks Layout”, by Chang-Sheng Ying and Joshua Sook-Leung Wong, 1989, pp. 403-412.
IEEE Journal Article titled “VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair”, by Hiroshi Murata, et al., 1996, pp. 1518-1524.
IEEE Journal Article titled “The Timberwolf Placement and Routing Package”, by Carl Sechen and Alberto Sangiovanni-Vincentelli, 1985, pp. 510-522.
The Kluwer International Series in Engineering and Computer Science article titled “Analog Device-Level Layout Automation”, by John M. Cohn, et al., pp. vi-vii and pp. 21-104.
Article titled “Virtual Symmetry Axes for the Layout of Analog IC's”, by
Balasa Florin
Lampaert Koen
Conexant Systems Inc.
Niebling John F.
Thomas Kayden Horstemeyer & Risley LLP
Whitmore Stacy A
LandOfFree
Method for automated placement of cells in an integrated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for automated placement of cells in an integrated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for automated placement of cells in an integrated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3026069