Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-04-03
2002-08-13
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06434721
ABSTRACT:
RELATED APPLICATION
1. Field of the Invention
The present invention relates to layout compaction for integrated circuit design automation, and more particularly to constraint graph-based layout compaction that compacts circuit elements in two dimensions during the design automation stage of a circuit layout with reduced computational requirements.
2. Description of Related Art
Compaction is an important design automation stage in the phased approach to layout synthesis of integrated circuits (ICs), such as a very large scale integration (VLSI) design. The compaction operation converts symbolic layouts generated by other layout synthesis tools into mask data or physical layouts and attempts to optimize the area of the layout without changing the circuit or violating the design rules. In other words, it is desired to make each chip as small as possible while maintaining design rule correctness (DRC). Today, the most attractive approach to mask layout compaction is graph-based compaction, which provides a robust basis for a one- and two-dimensional compaction.
Layout compaction algorithms typically range between one-dimensional and two-dimensional compaction. In one-dimensional compaction, only one coordinate of the layout geometry is changed at a time, such as either X compaction or Y compaction. The goal of one-dimensional compaction is to minimize the length of one dimension or direction, whereas the other direction, referred to as the shear or orthogonal direction, is not affected and remains constant. It is noted that dimension and direction are often used interchangeably herein. The goal of two-dimensional compaction is to modify both X and Y coordinates simultaneously in order to minimize area. Many one-dimensional compaction algorithm versions can be solved efficiently without consuming significant computational resources. A few proposed versions of one-dimensional compaction and most two-dimensional compaction proposals are “NP-hard”, which means that they are computationally prohibitive and not practicable. The difficulty of two-dimensional compaction lies in determining how the two dimensions of the layout interact to minimize the area. To circumvent the intrinsic complexity of this problem, some heuristic methods have been proposed to relate both dimensions of the compaction. Such heuristic proposals are often referred to as “1.5-dimensional” compaction since, although they interrelate the two dimensions, they do not optimally solve the two-dimensional compaction problem.
Some 1.5-dimensional compaction methods have been proposed in which the layout is essentially compacted in a preferred direction, while changing the shear or orthogonal direction. In the process of achieving the primary goal of decreasing the extent of the layout in the preferred direction, these compaction techniques also make coordinate changes in the shear direction. Each local change is called a reorganization. One heuristic framework has been proposed, called “super compaction”, for carrying out feasible reorganization such that the length of the longest path in the layout graph for the preferred direction is decreased. This approach is known as “shearing” compaction. Another method to minimize the critical path in the constraint graph is referred to as “jog insertion”.
Unfortunately, the shearing and jog insertion methods have been applied in sequence and have not been applied simultaneously. As a result, the existing algorithms cannot compact most layouts very efficiently. Shearing and jog insertion techniques in sequence can optimize the layout, but only if a sequence of the shearing and jog insertion methods are applied sequentially where each particular step improves the objective. The existing compaction algorithms, however, cannot apply critical path reduction techniques of shearing and jog insertion simultaneously and therefore optimal solutions are not available for most designs.
REFERENCES:
patent: 4554625 (1985-11-01), Otten
patent: 6026223 (2000-02-01), Scepanovic et al.
patent: 6189132 (2001-02-01), Heng et al.
patent: 6301686 (2001-10-01), Kikuchi et al.
patent: 6353918 (2002-03-01), Carothers et al.
patent: 6385758 (2002-05-01), Kikuchi et al.
Barzaghi et al. (“Symbolic compaction of digital CMOS cells”, Proceedings of 6th Mediterranean Electrotechnical Conference, vol. 1, May 22, 1991, pp. 222-225).*
NN9010221 (“Floorplanning by Constraint Reduction”, IBM Technical Disclosure Bulletin, vol. 33, No. 5, Oct. 1990, pp. 221-226 (8 pages)).*
Maidee et al. (“Invisible edge and soft tied in compaction strategy”, The 1998 IEEE Asia-Pacific Conference on Circuits and Systems, Nov. 24, 1998, pp. 133-136).*
Martineau et al. (“Automatic jog insertion for 2D mask compaction: a global optimization perspective”, Proceedings of 3rd European Conference on Design Automation, Mar. 16, 1992, pp. 508-512).*
Awashima et al. (“An optimal chip compaction method based on shortest path algorithm with automatic job insertion”, 1992 IEEE/ACM International Conference on Computer-Aided Design, Nov. 8, 1992, pp. 162-165).*
Mehlhorn et al. (“A faster compaction algorithm with automatic jog insertion”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 9, No. 2, Feb. 1990, pp. 158-166).*
Xiong et al. (“Geometric compaction of building-block layout”, Proceedings on the IEEE 1989 Custom Integrated Circuits Conference, May 15, 1989, pp. 17.6/1-17.6/4).*
Yao et al. (“A new approach to the pin assignment problem”, Proceedings of 25th ACM/IEEE Design Automation Conference, Jun. 12, 1988, pp. 566-572).
Chiluvuri Venkata K. R.
Marchenko Alexander
Sotnikov Mikhail
Clingan, Jr. James L.
Kik Phallaka
Motorola Inc.
Smith Matthew
LandOfFree
Method and apparatus for constraint graph based layout... 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 and apparatus for constraint graph based layout..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for constraint graph based layout... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2885949