Representing device layout using tree structure

A tangible computer readable storage medium containing a tree structure for representing physical area occupied by a layout of a programmable device to be used by a computer program for searching selected areas of the device layout to identify functional units of the device layout comprised therein, the tree structure comprising:

• one or more root nodes representing one or more main portions of the physical area occupied by the device layout;
• one or more branch nodes representing equally sized sub-areas within one or more main portions of the physical area occupied by the device layout;
• and
• one or more leaf nodes for representing the physical area occupied the units of a device layout.

A computer implemented method for searching a layout of a programmable device for determining information related to components of the device wherein the device comprises pre-defined layout units with each unit being of a size that is a multiple of a size of a basic layout unit of the device layout, the method comprising:

• receiving data related to selection of a physical area of the device layout to be searched;
• retrieving a tree structure representative of the device layout, wherein the tree structure represents main portions of the device as roots of the tree structure, equally sized sub-areas of the main portions are represented as branches of the tree structure and layout units within the device layout are represented as leaf nodes of the tree structure;
• and
• searching the tree structure starting with the root node and ending with the leaf nodes and recording data related to components associated with the leaf nodes.

A tangible computer readable medium useful in conjunction with a computer and having stored thereon computer executable instructions operable for performing a method of 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;
• and
• relating leaf nodes related to the faux cell units to the non-uniform straddling layout unit.

A method of representing the layout of a programmable device as a tree structure, the method comprising:

• designating at least a first portion of an area occupied by the programmable device layout containing a plurality of layout units as a first root portion of a tree structure;
• dividing the first root portion into a plurality of equally sized branch portions;
• determining whether the area occupied by any of the branch portions correspond to one of the layout units, and if so, designating any such branch portions which correspond with a layout units as a separate leaf portion of the tree structure;
• further dividing any of the remaining branch portions which do not correspond to one of the layout units into a plurality of equally sized sub-branch portions;
• determining whether any of the sub-branch portions correspond to one of the layout units, and if so, designating any such sub-branch portions which correspond with a layout units as a separate leaf portion of the tree structure;
• repeating the further dividing and determining acts until all layout units of the first portion of the programmable device have been represented as separate leaf portions of the tree structure.

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 device components within a selected area of the layout, the method comprising:

• designating at least one area of the device as a first root node of a tree structure;
• dividing the first root node into equally sized sub-areas and further dividing at least some of said sub-areas into equally sized sub-sub-areas;
• designating each sub-area which corresponds to a layout unit of the the device as a leaf node of the tree structure originating from the first root node;
• and designating each sub-sub-area which corresponds to the layout unit of the device as a leaf node of the tree structure originating from the first root node,