Two dimensional compaction system and method

#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.

#FIG. 1(a) shows an example source layout with four layout objects.

#FIG. 1(b) shows the layout of FIG. 1(a) compacted horizontally only, then vertically only.

#FIG. 1(c) shows the layout of FIG. 1(a) compacted vertically only, then horizontally only.

#For the purposes of this disclosure, a layout includes a collection of polygons, lines or points, or other two dimensional objects with an assigned layer. A hierarchical layout includes two or more cell masters and one or more cell instances of each of the masters, except for the top of the hierarchy. A layout edge is the edge of a polygon or line and a layout point is the corner of a polygon, endpoint of a line, or a point. Layout edges form the boundary of layout objects such as transistors, vias, or wires. A text label is a layout point with associated formatted text. An array instance is a cell instance arrayed in one or two dimensions in a regular pattern, such as a row, column or matrix of cell instances of the same cell master.

#The position of a given vertical edge ei in Cartesian coordinates is represented by a position variable xi and the position of a given horizontal edge ej in Cartesian coordinates is represented by a position variable yj. Referring now to FIG. 2(a) for an example, the right and top edges of layout object E are represented by position variables x1 and y1, respectively, and the left and bottom edges of layout object F are represented by position variables x2 and y2, respectively. The layout object F is to remain above and/or right of layout object E by a distance d, which corresponds to a minimum spacing design rule distance between objects E and F. Keeping object F right of E is represented by the linear constraint x2−x1>d, keeping object F above E is represented by the linear constraint y2−y1>d, and keeping object F above and right of E is represented by the nonlinear constraints (x2−x1)2+(y2−y1)2>d2 as well as linear constraints x2>x1 and y2>y1. Since nonlinear constraints are more difficult to enforce in mathematical programming, a linear approximation to this constraint is used instead with a slight degradation in the closest possible spacing of E to F.

#Keeping F above and right of E is represented instead by the single linear constraint (y2−y1)+(x2−x1)>{square root over (2)} d. The choice of keeping F above E, right of E or diagonally opposed to E is made before constraints are generated and solved by a linear program method. If the wrong choice was made after solving, heuristics can be applied to change this choice. In practice, few changes are needed and a good result is obtained without employing Branch and Bound methods.