Method and mechanism for managing hierarchical data for implementing region query

• US 8,453,091 B1
• Filed: 12/23/2010
• Issued: 05/28/2013
• Est. Priority Date: 03/26/2010
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Rao, Guruprasad G., Hahn, Mark, Volpe, Laurent
• Primary Examiner(s): Parihar, Suchin
• Application Number:
  US12/978,216
• Time in Patent Office: 887 Days
• Field of Search: 716/100, 716/118
• US Class Current: 716/118
• CPC Class Codes: G06F 2119/06 Power analysis or power optimisation
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

Disclosed is an improved approach for managing, tracking, and querying hierarchical data in layouts. According to some aspects, hierarchical grids are employed utilizing a scheme that organizes physical objects into a set of gradually refined grids that avoids the need to maintain duplicates while enhancing the desirable characteristics of existing schemes, including fast query times, fast data structure initialization and reduced memory footprint. Each grid-cell may be further partitioned into sub-containers to more efficiently provide space pruning during query operations. According to one approach, structures maintained to track existence of objects in a descendent hierarchy.

Claims

1. A method implemented with a processor for managing hierarchical layout data, comprising:

using at least the processor to performing a process, the process comprising;

configuring a set of hierarchical grids for the hierarchical layout of an electronic design, wherein

the set of hierarchical grids comprises of grid-cells having a larger grid size at a higher hierarchical level of a hierarchy than grid-cells at a lower hierarchical level to represent layout objects; and

assigning a layout object canonically to a specific hierarchical grid cell level based at least in part upon a size of the layout object and a grid size of the specific hierarchical grid cell level in the electronic design by using a canonical assignment.

2. The method of claim 1 wherein a higher level hierarchical grid-cell comprises a larger size than a lower level hierarchical grid-cell.

3. The method of claim 2 in which an object is sieved by the hierarchical grids, such that the object is assigned to the grid-cell at a hierarchical level based upon object size corresponding to a grid-cell size for the hierarchical level.

4. The method of claim 1 in which a criterion for the logical partitioning corresponds to location of the layout objects or size of the layout objects in the grid-cell.

5. The method of claim 1 in which a vector is utilized to track the layout objects in logical partitions, where an object is associated with a slot in the vector.

6. The method of claim 1 in which search criteria information is tracked for a logical partition, where the search criteria information comprises a maximum dimension, a minimum dimension, or a merged box.

7. The method of claim 1 in which the set of hierarchical grids is controllably implemented using a heuristic or optimization algorithm to optimize the characteristics of the hierarchical grid structure for a particular objective or set of objectives.

8. The method of claim 7 in which the heuristic or optimization algorithm controls the depth and granularity of partitioning in the set of hierarchical grids.

9. The method of claim 8 in which a histogram of object sizes is employed to determine incremental expansion parameters, a termination criterion, and/or sizes of grid-cells.

10. The method of claim 1 in which, after a change is made to the layout of a design or design hierarchy, maintenance of structures that is needed to address the change for the set of hierarchical grids is deferred until a later point in time.

11. The method of claim 10 in which the maintenance of the structures comprises re-building of grid and partition structures and re-computing tracked query information.

12. The method of claim 1 in which addition of a new layout object is addressed by marking a container to indicate that the container includes the new object.

13. The method of claim 1 in which deletion of an existing layout object is addressed by updating a container to indicate that the existing object has been removed from the container.

14. The method of claim 1 in which deletion of an existing layout object is addressed by invalidating structures that maintain the set of hierarchical grids.

15. The method of claim 14 in which a maximum dimension, minimum dimension, or a merged box is invalidated by the deletion of the existing object.

16. The method of claim 15 in which individual objects corresponding to the maximum dimension, minimum dimension, or the edges of the merged box are tracked so that removal of an existing object corresponding to the maximum dimension, minimum dimension, or to an edge of the merged box will not cause invalidation if there are other existing objects that still validly correspond to the maximum dimension, minimum dimension, or that edge of the merged box.

17. The method of claim 15 in which the numbers of objects corresponding to the maximum dimension, minimum dimension, or the edges of the merged box are tracked so that removal of an existing object corresponding to the maximum dimension, minimum dimension, or to an edge of the merged box will not cause invalidation if there are other existing objects that still validly correspond to the maximum dimension, minimum dimension, or that edge of the merged box.

18. A method implemented with a processor for managing hierarchical layout data, comprising:

using at least the processor to performing a process, the process comprising;

configuring a set of hierarchical grids for an electronic design, wherein

the set of hierarchical grids comprises grid-cells having a larger grid size at a higher hierarchical level at of a hierarchy than other grid-cells at a lower hierarchical level to represent layout objects; and

assigning a layout object canonically to a specific hierarchical grid cell level by using at least a canonical assignment with consideration of a size of the layout object and a grid size of the specific hierarchical grid cell level but without consideration of any other object in the electronic design.

19. The method of claim 18 wherein a higher level hierarchical grid-cell comprises a larger size than a lower level hierarchical grid-cell.

20. The method of claim 19 in which an object is sieved by the hierarchical grids, such that the object is assigned to the grid-cell at a hierarchical level based upon object size corresponding to a grid-cell size for the hierarchical level.

21. The method of claim 18 in which a criterion for the logical partitioning corresponds to location of the layout objects or size of the layout objects in the grid-cell.

22. The method of claim 18 in which a vector is utilized to track the layout objects in logical partitions, where an object is associated with a slot in the vector.

23. The method of claim 18 in which search criteria information is tracked for a logical partition, where the search criteria information comprises a maximum dimension, a minimum dimension, or a merged box.

24. The method of claim 18 in which the set of hierarchical grids is controllably implemented using a heuristic or optimization algorithm to optimize the characteristics of the hierarchical grid structure for a particular objective or set of objectives.

25. The method of claim 24 in which the heuristic or optimization algorithm controls the depth and granularity of partitioning in the set of hierarchical grids.

26. The method of claim 25 in which a histogram of object sizes is employed to determine incremental expansion parameters, a termination criterion, and/or sizes of grid-cells.

27. The method of claim 18 in which, after a change is made to the layout of a design or design hierarchy, maintenance of structures that is needed to address the change for the set of hierarchical grids is deferred until a later point in time.

28. The method of claim 27 in which the maintenance of the structures comprises re-building of grid and partition structures and re-computing tracked query information.

29. The method of claim 18 in which addition of a new layout object is addressed by marking a container to indicate that the container includes the new object.

30. The method of claim 18 in which deletion of an existing layout object is addressed by updating a container to indicate that the existing object has been removed from the container.

31. The method of claim 18 in which deletion of an existing layout object is addressed by invalidating structures that maintain the set of hierarchical grids.

32. The method of claim 31 in which a maximum dimension, minimum dimension, or a merged box is invalidated by the deletion of the existing object.

33. The method of claim 32 in which individual objects corresponding to the maximum dimension, minimum dimension, or the edges of the merged box are tracked so that removal of an existing object corresponding to the maximum dimension, minimum dimension, or to an edge of the merged box will not cause invalidation if there are other existing objects that still validly correspond to the maximum dimension, minimum dimension, or that edge of the merged box.

34. The method of claim 32 in which the numbers of objects corresponding to the maximum dimension, minimum dimension, or the edges of the merged box are tracked so that removal of an existing object corresponding to the maximum dimension, minimum dimension, or to an edge of the merged box will not cause invalidation if there are other existing objects that still validly correspond to the maximum dimension, minimum dimension, or that edge of the merged box.

35. A computer program product embodied on a non-transitory computer usable medium, the non-transitory computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for managing hierarchical layout data, the method comprising:

configuring a set of hierarchical grids for the hierarchical layout of an electronic design, wherein

the set of hierarchical grids comprises grid-cells having a larger grid size at different levels a higher hierarchical level of a hierarchy than grid-cells at a lower hierarchical level to represent layout objects; and

assigning a layout object canonically to a specific hierarchical grid cell level based at least in part upon a size of the layout object and a grid size of the specific hierarchical grid cell level in the electronic design by using a canonical assignment.

36. The computer program product of claim 35 wherein a higher level hierarchical grid-cell comprises a larger size than a lower level hierarchical grid-cell.

37. The computer program product of claim 35 in which a criterion for the logical partitioning corresponds to location of the layout objects or size of the layout objects in the grid-cell.

38. The computer program product of claim 35 in which search criteria information is tracked for a logical partition, where the search criteria information comprises a maximum dimension, a minimum dimension, or a merged box.

39. The computer program product of claim 35 in which the set of hierarchical grids is controllably implemented using a heuristic or optimization algorithm to optimize the characteristics of the hierarchical grid structure for a particular objective or set of objectives.

40. The computer program product of claim 35 in which, after a change is made to the layout of a design or design hierarchy, maintenance of structures that is needed to address the change for the set of hierarchical grids is deferred until a later point in time.

41. A computer program product embodied on a non-transitory computer usable medium, the non-transitory computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for managing hierarchical layout data, the method comprising:

configuring a set of hierarchical grids for an electronic design, wherein

the set of hierarchical grids comprise grid-cells having a larger grid size at a higher hierarchical level of a hierarchy than other grid-cells at a lower hierarchical level to represent layout objects; and

assigning a layout object canonically assigned to a specific hierarchical grid cell level by using at least a canonical assignment with consideration of a size of the layout object and a grid size of the specific hierarchical grid cell level but without consideration of any other object in the electronic design.

42. The computer program product of claim 41 in which a vector is utilized to track the layout objects in logical partitions, where an object is associated with a slot in the vector.

43. The computer program product of claim 41 in which search criteria information is tracked for a logical partition, where the search criteria information comprises a maximum dimension, a minimum dimension, or a merged box.

44. The computer program product of claim 41 in which the set of hierarchical grids is controllably implemented using a heuristic or optimization algorithm to optimize the characteristics of the hierarchical grid structure for a particular objective or set of objectives.

45. The computer program product of claim 41 in which, after a change is made to the layout of a design or design hierarchy, maintenance of structures that is needed to address the change for the set of hierarchical grids is deferred until a later point in time.

46. A system for managing hierarchical layout data, comprising:

a processor;

a memory for holding programmable code, wherein the programmable code includes instructions which, when executed by the processor, cause the processor to;

configure a set of hierarchical grids for the hierarchical layout of an electronic design, wherein

the hierarchical grids comprise grid-cells having a larger grid size at a higher hierarchical level of a hierarchy than grid-cells at a lower hierarchical level to represent layout objects; and

assign a layout object canonically to a specific hierarchical grid cell level based at least in part upon size of the layout object and a grid size of the specific hierarchical grid cell level in the electronic design by using a canonical assignment.

47. The system of claim 46 wherein a higher level hierarchical grid-cell comprises a larger size than a lower level hierarchical grid-cell.

48. The system of claim 46 in which a criterion for the logical partitioning corresponds to location of the layout objects or size of the layout objects in the grid-cell.

49. The system of claim 46 in which search criteria information is tracked for a logical partition, where the search criteria information comprises a maximum dimension, a minimum dimension, or a merged box.

50. The system of claim 46 in which the set of hierarchical grids is controllably implemented using a heuristic or optimization algorithm to optimize the characteristics of the hierarchical grid structure for a particular objective or set of objectives.

51. The system of claim 46 in which, after a change is made to the layout of a design or design hierarchy, maintenance of structures that is needed to address the change for the set of hierarchical grids is deferred until a later point in time.

52. A system for managing hierarchical layout data, comprising:

a processor;

a memory for holding programmable code, wherein the programmable code includes instructions which, when executed by the processor, cause the processor to;

configure a set of hierarchical grids for an electronic design, wherein

the hierarchical grids comprise grid-cells having a larger grid size at a higher hierarchical level of a hierarchy than other grid-cells at a lower hierarchical level to represent layout objects, and

assign a layout object canonically to a specific hierarchical grid cell level by using at least a canonical assignment with consideration of a size of the layout object and a grid size of the specific hierarchical grid cell level but without consideration of any other object in the electronic design.

53. The system of claim 52 in which a vector is utilized to track the layout objects in logical partitions, where an object is associated with a slot in the vector.

54. The system of claim 52 in which search criteria information is tracked for a logical partition, where the search criteria information comprises a maximum dimension, a minimum dimension, or a merged box.

55. The system of claim 52 in which the set of hierarchical grids is controllably implemented using a heuristic or optimization algorithm to optimize the characteristics of the hierarchical grid structure for a particular objective or set of objectives.

56. The system of claim 52 in which, after a change is made to the layout of a design or design hierarchy, maintenance of structures that is needed to address the change for the set of hierarchical grids is deferred until a later point in time.