Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-04-30
2001-02-13
Lintz, Paul R. (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06189130
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to semiconductor chips and, more particularly, to a system and method for calculating density maps for hierarchical chip designs.
2. Description of the Related Art
Density maps are used in the semiconductor industry as a metric for determining manufactured chip quality. Calculating a density map for various levels of the chip design is often required in the manufacturing process; such levels correspond to different processing steps or material layers, such as diffusion, metal interconnect, etc. The density map is computed to check layout ground rules dictated by process considerations. The density map is used to condition “fill shapes” to be added to a design for the purpose of making pattern density more even across the design. The density map may also be used to condition compensation algorithms (e.g., which modify the local widths of critical features) to compensate for process variations due to variations in pattern density.
The density map is also useful for determining other important scalar properties, for example, defect susceptibility, power dissipation, etc. for purposes of modeling and/or correction for these properties. The density map also is used to estimate yield loss due to densities that are too low or too high in metal layers of the design. The density map is further used to evaluate non-uniformities in height across the chip, due to variations in density, and its effect on CMP (chemical mechanical planarization). Density map is generally about 10% to about 50% for standard designs.
A density map is determined by computing a fraction of occupied area in a given area as described in Kahng et al., Int. Smp. of Phys. Des. 1998. The occupied area is the area occupied by a shape or shapes of, for example, a device such as a transistor or a diffusion region of the transistor. This problem is closely related to a measure problem. The measure problem seeks to find the area of a collection of rectangles, where overlapping regions are only counted once. An algorithm with complexity of O (N log N), where N is the number of rectangles, has been developed in the prior art to address the measure problem.
For real designs, the calculation of density maps is often more complex than the solutions described above. Chip designs include shapes that cannot always be represented by a set of rectangles without losing accuracy. Also, the measure for real designs must be found within many grid squares. Further, the prior art approach requires flattening the design which precludes its usage for very large designs, for example in memory chips. This also precludes usage of the prior approach in devices other than memory chips, for example in processors having on-chip cache, register files, repetitive usage of large standard cells, etc.
Therefore, a need exists for a system and method for determining density maps in a highly nested (hierarchical) form. A further need exists for providing a more efficient system and method for reducing running time and memory requirements for calculating density maps.
SUMMARY OF THE INVENTION
According to the present invention, a method for calculating density maps in hierarchical designs includes the steps of deoverlapping objects in the design, providing an area of interest in the design, generating a grid in the area of interest to partition the area of interest into grid elements, determining whether the local properties of each object within the grid elements have been previously calculated, if previously calculated, adding the previously calculated value for the local properties to a corresponding grid element, otherwise, calculating the local properties of the object and summing the local properties of the objects for each associated grid element such that the local properties are calculated only once for a given object throughout the design.
In alternate methods of the present invention, the step of calculating a density map by dividing the local properties for objects in a grid element by an area of the grid element may be included. The step of deoverlapping may include altering shapes of objects to be disjoint while maintaining the local properties of the objects. The step of providing the area of interest may include the step of enclosing the area of interest by a least enclosing rectangle (LER). The step of generating a grid may include the step of generating a grid of polygons. The local properties may include areas of objects. The step of apportioning local properties of objects existing in more than one grid element to the associated grid element for each apportioned local property may be included. The objects preferably include shapes and cells. The step of apportioning areas of shapes and cells existing in more than one grid element to the associated grid element for each apportioned area may also be included. The step of calculating density maps for user specified areas within the area of interest may also be included. The steps of providing a mini-grid including mini-grid elements for each user specified area and apportioning areas of shapes determined to be in the mini-grid elements of each user specified area among the grid elements of the area of interest are preferably included.
Another method for calculating density maps in hierarchical designs includes the steps of deoverlapping objects in the design, providing an area of interest in the design, generating a grid in the area of interest to partition the area of interest into grid elements, initializing a calculated area associated with each grid element to zero, moving through objects in the hierarchy to determine if the objects are a shape or a cell, if the object is a shape, apportioning the area of the shape to associated grids elements, if the object is a cell, determining if the cell includes mini-maps, if mini-maps are included, apportioning areas of cells and shapes in the mini-map to the associated grid elements of the area of interest, if the object is a cell, determining if the instance can be further divided into smaller cells, if dividing the cells into smaller cells is possible, dividing the cells, apportioning the areas of the cells to associated grid elements.
In alternate methods of the present invention, the step of calculating a density maps by dividing the areas for shapes and cells in a grid element by an area of the grid element may be included. The step of deoverlapping may include altering shapes of the objects while maintaining the area of the objects. The step of providing the area of interest may include the step of enclosing the area of interest by a least enclosing rectangle (LER). The step of generating a grid may include the step of generating a grid of squares. The steps of bypassing a computation previously performed to determine an area for one of a same cell and a same shape and employing an area determined by a previously performed computation for shapes and cells such that the area is calculated only once for a given shape or cell throughout the design may be included. The step of selecting cells and creating density maps (mini-maps) for the selected cells and subsequent usage of these mini-maps in calculating density maps density maps for mini-maps may also be included.
A system for calculating density maps in hierarchical designs includes means for deoverlapping objects in an area of interest in the design. A grid generated in the area of interest to partition the area of interest into grid elements, each grid element including objects having local properties associated therewith is also included. Means for determining whether the local properties of each object within the grid elements have been previously calculated is included. If previously calculated, the previously calculated value is added for the local properties to a corresponding grid element. Means for calculating the local properties for the objects for newly encountered objects is included such that the local properties are calculated only once for a given object throughout the design, and the den
Gofman Emanuel
Gracer Franklin
Karnin Ehud Dov
Lavin Mark A.
Ramm Dov
Do Thuan
F. Chau & Associates LLP
International Business Machines - Corporation
Lintz Paul R.
LandOfFree
System and method for determining density maps in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for determining density maps in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for determining density maps in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2611222