System and method for determining density maps in hierarchical designs

• US 6,189,130 B1
• Filed: 04/30/1998
• Issued: 02/13/2001
• Est. Priority Date: 04/30/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gracer, Franklin, Ramm, Dov, Lavin, Mark A., Karnin, Ehud Dov, Gofman, Emanuel
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Do, Thuan
• Application Number:
  US09/070,482
• Time in Patent Office: 1,020 Days
• Field of Search: 716/7, 716/14
• US Class Current: 716/55
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36

Abstract

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. A system is also includes for implementing the method.

Claims

1. A method for calculating density maps in hierarchical designs comprising 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.

2. The method as recited in claim 1, further comprising 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.

3. The method as recited in claim 1, wherein the step of deoverlapping includes altering shapes of objects to be disjoint while maintaining the local properties of the objects.

4. The method as recited in claim 1, wherein the step of providing the area of interest includes the step of enclosing the area of interest by a least enclosing rectangle (LER).

5. The method as recited in claim 1, wherein the step of generating a grid includes the step of generating a grid of polygons.

6. The method as recited in claim 1, wherein the local properties include areas of objects.

7. The method as recited in claim 1, further comprising 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.

8. The method as recited in claim 1, wherein the objects include shapes and cells.

9. The method as recited in claim 8, further comprising 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.

10. The method as recited in claim 1, further comprising the step of calculating density maps for one of user specified areas and automatically specified areas within the area of interest.

11. The method as recited in claim 10, further comprising the steps of:

providing a mini-grid including mini-grid elements for each specified area and;

apportioning areas of shapes determined to be in the mini-grid elements of each specified area among the grid elements of the area of interest.

12. A method for calculating density maps in hierarchical designs comprising 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 object is further divisible according to predetermined criteria;

dividing the cells according to the predetermined criteria;

apportioning the areas of the cells to associated grid elements;

determining whether areas for each object in the grid elements have been previously calculated; and

if previously calculated, adding the previously calculated value for the areas to a corresponding grid element.

13. The method as recited in claim 12, further comprising 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.

14. The method as recited in claim 12, wherein the step of deoverlapping includes altering shapes of the objects to be disjoint while maintaining the area of the objects.

15. The method as recited in claim 12, wherein the step of providing the area of interest includes the step of enclosing the area of interest by a least enclosing rectangle (LER).

16. The method as recited in claim 12, wherein the step of generating a grid includes the step of generating a grid of polygons.

17. The method as recited in claim 12, further comprising 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.

18. The method as recited in claim 12, further comprising the step of calculating density maps for mini-maps.

19. A system for calculating density maps in hierarchical designs comprising:

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;

means for determining whether the local properties of each object within the grid elements have been previously calculated;

means for calculating the local properties for newly encountered objects; and

if previously calculated, means for adding the previously calculated value for the local properties to a corresponding grid element such that the local properties are calculated only once for a given object throughout the design and the density map is determined when the local properties of the objects are summed in each grid element and divided by an associated grid element area.

20. The system as recited in claim 19, further comprises a memory for storing calculated local properties for objects in an associated grid element.

21. The system as recited in claim 19, wherein the objects include semiconductor devices.

22. The system as recited in claim 19, wherein the objects include mini-maps.

23. The system as recited in claim 19, further comprises means for apportioning for dividing local properties of objects existing in more than one grid element.

24. The system as recited in claim 19, further comprises a processor for summing local properties of the objects in each grid element and dividing by the associated grid element area.

25. The system as recited in claim 19, wherein the local properties include areas of the objects.

26. The system as recited in claim 19, wherein the objects include shapes and cells.

27. The system as recited in claim 19, wherein the hierarchical designs are included on integrated circuit chips.