Method and mechanism for performing 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.
Claims42
A method implemented with a processor for querying a layout data, comprising:
- using at least the processor to perform a process, the process comprising:
- receiving a database region query directed to a layout, the database region query comprising a search region, wherein
- the layout is represented using a set of hierarchical grids where a higher hierarchical grid has a larger grid size than a lower hierarchical grid, and
- a layout object is allocated to a specific hierarchical grid in the layout by sieving the layout object with the set of hierarchical grids based at least in part upon an layout object size and a grid size of the specific hierarchical grid in the set of hierarchical grids;
- computing a subset of the set of hierarchical grids corresponding to the search region;
- and
- searching the subset of hierarchical grids without traversing other hierarchical grids to identify one or more layout objects of an electronic design to satisfy the database region query.
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 querying a layout data, the method comprising:
- receiving a database region query directed to a layout, the database region query comprising a search region, wherein
- the layout is represented using a set of hierarchical grids where a higher hierarchical grid has a larger grid size than a lower hierarchical grid, and
- a layout object is allocated to a specific hierarchical grid in the layout by sieving the layout object with the set of hierarchical grids based at least in part upon an layout object size and a grid size of the specific hierarchical grid in the set of hierarchical grids;
- computing a subset of the set of hierarchical grids corresponding to the search region;
- and
- searching the subset of hierarchical grids without traversing other hierarchical grids to identify one or more layout objects of an electronic design to satisfy the database region query.
A system for querying hierarchical layout data, comprising:
- a processor;
- a memory for holding programmable code that includes instructions which, when executed by the processor, cause the processor to:
- receive a database region query directed to a layout, the database region query comprising a search region, wherein
- the layout is represented using a set of hierarchical grids where a higher hierarchical grid has a larger grid size than a lower hierarchical grid, and
- a layout object is allocated to a specific hierarchical grid in the layout by sieving the layout object with the set of hierarchical grids based at least in part upon an layout object size and a grid size of the specific hierarchical grid in the set of hierarchical grids;
- compute a subset of the set of hierarchical grids corresponding to the search region;
- and
- search the subset of hierarchical grids without traversing other hierarchical grids to identify one or more layout objects of an electronic design to satisfy the database region query.
Dependencies are inferred from the claim text.