Two dimensional compaction system and method

Details Two dimensional compaction system and method Two dimensional compaction system and method

2002-06-20

2003-07-01

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06587992

ABSTRACT:

BACKGROUND OF INVENTION
The present invention relates to layouts composed of geometrical objects, such as polygons, lines and points, and more specifically to a system and method for enforcing design rules and optimizing geometrical objectives for layouts in integrated circuits.
Prior to producing masks needed for the manufacture of integrated circuits (ICs), every IC layout must satisfy complex design rules specific to the IC manufacture technology. These design rules are usually geometric in nature, and may include, for example, minimum area, width, spacing, overlap and/or enclosure requirements on the IC layout. The rules generally apply to all regions of an IC layout and apply over a two dimensional space involving one or more layers. By obeying all design rules for a given IC technology and all circuit requirements of the IC design, such as connectivity, wire widths and device sizes, the IC layout will yield functional and manufacturable chips.
IC layouts are generally partitioned into a hierarchical structure involving cell masters, whereby cell masters are referenced by one or more cell instances, and each cell master in turn may contain layout objects and/or other cell instances. A hierarchical organization of an IC layout is needed to efficiently represent repeated structures and to manage large complex ICs or IC components. For highly regular layouts, array structures are used to represent rows and/or columns of repeated cell instances.
For most IC layouts, layout designers manually produce the cells composing a layout with the aid of graphical layout editors. Once drawn, the cells must be verified with design rule and circuit verification programs and altered to fix violations. This is a tedious and costly process and often must be repeated for every IC technology that will be used to manufacture chips containing the cells. The process of transforming an existing layout obeying design rules of some IC technology to a new layout obeying design rules of a different IC technology is called layout migration. Though layout migration is easier than the initial creation of a IC layout, it is usually done manually with layout designers since automation of layout migration is very difficult.
To date, the primary automation method applied to the problem of transforming an existing IC layout to a new layout obeying design rules of a target IC technology is compaction. Compaction is a method used to optimize a given IC layout subject to a set of design rule constraints. The layout is optimized by minimizing the total layout area as well as the length of wires and area of other layout objects. The layout objects are constrained by design rule interactions and circuit connectivity and parameter requirements and must be positioned without violating any such constraint. Almost all compaction methods are performed in one dimension at a time and often on one cell at time. This is done to simplify the compaction problem to the point that the problem can be solved by efficient solving algorithms. To completely compact a layout in two dimensions, compaction must be performed in the vertical direction, or Y direction in Cartesian coordinates, then the horizontal direction, or X direction in Cartesian coordinates. A layout could also be compacted first in the horizontal direction followed by compaction in the vertical direction.
Each time compaction is performed, four steps must be conducted. The first step is to model layout objects or layout object edges with position variables and define an objective function that is a weighted sum of position variables. The next step is to create constraints between layout objects or edges based on the design rules of the target IC technology and circuit requirements of the target IC design. The constraints are modeled as linear mathematical relations involving a two or more position variables. The third step is to solve the mathematical problem of minimizing the objective function subject to the linear constraint relations using a known linear program solving algorithm. The last step is to update the layout objects with the solution from the solving algorithm.
When compaction is performed in one dimension on a single cell, the compaction model defaults to a constraint graph problem, where nodes in the graph represent position variables and arcs in the graph represent linear constraints. The resulting problem can be solved with a Network Flow Simplex algorithm, which is very efficient in practice. Further details on compaction modeled with constraint graphs can be found in “An Efficient Compactor for 45° Layout”, 25th Design Automation Conference, Anaheim, Calif., June 1988, pp. 396-402. When compaction is performed in one dimension on a hierarchical layout and the hierarchy is to be preserved, the compaction model is a general linear program, which can be solved by sparse implementations of the Revised Simplex algorithm. Further details on compaction modeled with linear programs can be found in “A Hierarchy Preserving Hierarchical Compactor”, 27th Design Automation Conference, Orlando, Fla., June 1990, pp. 375-381. Additional details on compaction can be found in “Leaf Cell and Hierarchical Compaction Techniques”, by Cyrus Bamji and Ravi Varadarajan, Kluwer Academic Publishers, Norwell Mass., 1997.
Compacting a layout in one dimension at a time does not always produce the best result. Moreover, the result varies depending on which direction the first compaction is performed. Consider the example layout shown in FIG.
1
(
a
). This layout contains four layout objects A, B, C and D which are all assigned the same layer and must be spaced apart by a minimum spacing design rule. If this layout is compacted in the vertical direction only, then in the horizontal direction only, the layout shown in FIG.
1
(
c
) results. If the layout in FIG.
1
(
a
) is compacted in the horizontal direction only, then in the vertical direction only, the layout shown in FIG.
1
(
b
) results. The best result that is possible is shown in FIG.
1
(
d
), which can not be easily produced by compacting in one dimension at a time. The layouts in FIGS.
1
(
b
),
1
(
c
) and
1
(
d
) all obey the minimum spacing design rules of the target IC technology, but only the layout in FIG.
1
(
d
) occupies the smallest area, which would be the lowest cost to manufacture.
Compacting a layout in both dimensions simultaneously usually produces better results than compacting in one dimension at a time. By compacting in two dimensions at once, the layout in FIG.
1
(
a
) can be transformed to the layout in FIG.
1
(
d
). However, one of the difficulties of two dimensional compaction methods is with corner to corner interactions. Examples of such interactions can be found in FIG.
1
(
a
), namely the bottom right corner of layout object A to the top left corner of layout object B, the top right corner of layout object C to the bottom right corner of layout object B, and the bottom right corner of layout object B to the top left corner of layout object D. To date, two dimensional compaction methods handle corner to corner interactions with Branch and Bound or other expensive algorithms, which have execution times that grow exponentially with the size of the layout. Though these methods produce good results, these methods can only be applied to small layouts such as a single cell. Further details on two dimensional compaction methods can be found in “Efficient Generation of Diagonal Constraints for 2-D Mask Compaction”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, No. 9, September 1996, pp. 1119-1126 and “Two-Dimensional Layout Compaction by Simulated Annealing”, IEEE International Symposium on Circuits and Systems, August 1988, pp. 2439-2443.
Therefore, a need exists for a two dimensional compaction method that can handle large IC layouts efficiently and still yield quality results. Moreover, to handle even larger layouts with some regularity or repeated cell instances, a need exists for a two dimensional compaction method that operates on hierarchical

Affiliated with

Also associated with

Rating

Two dimensional compaction system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Two dimensional compaction system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two dimensional compaction system and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3084191