Method and mechanism for implementing region query using hierarchical grids
AssigneeCadence Design Systems, Inc.
InventorsGuruprasad G. Rao, Mark Hahn, Laurent Volpe
Life of this patent
Estimating the term…
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.
Claims30
A computer implemented method for managing hierarchical layout data, comprising:
- using at least one processor to perform a process, the process comprising:
- configuring a set of hierarchical grids, wherein
- the set of hierarchical grids comprise different sizes of grid-cells at different levels of the hierarchy, and
- the set of hierarchical grids corresponds to equal-sized physical partitions at each level;
- assigning a set of layout objects to at least some of the grid-cells within the set of hierarchical grids based at least in part upon one or more sizes or locations of the set of layout objects by using one or more canonical assignments, wherein the set of grid-cells comprises multiple levels of granularity including a finest level of granularity that is greater than a smallest feature size in the hierarchical layout data;
- and
- dividing at least some of the set of layout objects assigned to a grid-cell into multiple logical partitions to achieve balanced performance in processing the grid-cells, wherein the logical partitions act as a stack of sieves and do not correspond to equal-sized physical partitions.
A computer program product comprising a non-transitory computer accessible medium having stored thereupon a sequence of instructions which, when executed by at least one processor, causes the at least one processor to execute a method for managing hierarchical layout data, the method comprising:
- using at least one processor to perform a process, the process comprising:
- configuring a set of hierarchical grids, wherein
- the set of hierarchical grids comprise different sizes of grid-cells at different levels of the hierarchy, and
- the set of hierarchical grids corresponds to equal-sized physical partitions at each level;
- assigning a set of layout objects to at least some of the grid-cells within the set of hierarchical grids based at least in part upon one or more sizes or locations of the set of layout objects by using one or more canonical assignments, wherein the set of grid-cells comprises multiple levels of granularity including a finest level of granularity that is greater than a smallest feature size in the hierarchical layout data;
- and
- dividing at least some of the set of layout objects assigned to a grid-cell into multiple logical partitions to achieve balanced performance in processing the grid-cells, wherein the logical partitions act as a stack of sieves and do not correspond to equal-sized physical partitions.
A system for managing hierarchical layout data, the method comprising:
- at least one processor that is to:
- configure a set of hierarchical grids, wherein
- the set of hierarchical grids comprise different sizes of grid-cells at different levels of the hierarchy, and
- the set of hierarchical grids corresponds to equal-sized physical partitions at each level;
- assign a set of layout objects to at least some of the grid-cells within the set of hierarchical grids based at least in part upon one or more sizes or locations of the set of layout objects by using one or more canonical assignments, wherein the set of grid-cells comprises multiple levels of granularity including a finest level of granularity that is greater than a smallest feature size in the hierarchical layout data;
- and
- divide at least some of the set of layout objects assigned to a grid-cell into multiple logical partitions to achieve balanced performance in processing the grid-cells, wherein the logical partitions act as a stack of sieves and do not correspond to equal-sized physical partitions.
Dependencies are inferred from the claim text.