Representing device layout using tree structure
OwnerKuoching Lininventor
Life of this patent
Estimating the term…
Abstract
Methods are described herein for using a tree structure representation for searching selected areas of a programmable device layout in order to determine the existing component configuration of a device. The tree structure may be generated by assigning root nodes, branch nodes and leaf nodes to portions of a tree structure. A search algorithm may walk the tree structure representation of the device layout to determine the existing component configuration of the device of a selected portion of the device layout. The tree structure is simplified by each node of a set of sister nodes on the tree representing equally sized sub-area of the device layout. The tree structure is capable of representing units of layout of multiple different sizes and non-uniform layout units that may straddle more than one sub-area.
Claims9
A computer implemented method for representing a layout of a programmable device as a tree structure to be searched by a computer program for determining a configuration of components within a selected area of the layout, the method comprising:
- representing a main portion of the device layout as a root node on the tree structure;
- assigning faux cell units to represent an area of the main portion occupied by a non-uniform layout unit straddling across multiple sub-areas of the main portion;
- representing each sub-area of the main portion as a branch node of the main portion root;
- dividing each sub-area further into equally sized lower level sub-areas until each of the lower level sub-areas corresponds to a layout unit of the device layout or a faux cell unit;
- representing each of the sub-areas corresponding to a layout unit or a faux cell unit as a leaf node on the tree structure;
- relating leaf nodes related to the faux cell units to the non-uniform straddling layout unit;
- and
- selecting one of the faux cell units to return results of a search rectangle overlapping the one or more of the faux cell units.
Dependencies are inferred from the claim text.