Representing device layout using tree structure
View Patent ↗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.
1. 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.
2. The method of claim 1 wherein relating the faux cell leaf nodes to the non-uniform straddling layout unit comprises assigning the faux cell leaf nodes a pointer to a tree structure node representing the non-uniform straddling layout unit.
3. The method of claim 1 wherein the faux cell unit selected to return results of the search rectangle overlaps the lower left corner of the search rectangle.
4. The method of claim 1 wherein the programmable device is a FPGA, PAL, a PLA, a gate array ASIC, or a CPLD.
5. The method of claim 1 wherein the main portion comprises a core area of the device layout.
6. The method of claim 1 wherein the main portion comprises I/O areas of the device layout.
7. The method of claim 1 wherein the layout of the programmable device comprises pre-defined layout units with each layout unit being of a size that is a multiple of a basic layout unit of the device.
8. The method of claim 1 wherein a size of the sub-area represented by children nodes of one of the branch nodes of the tree structure is different than a size of the sub-area represented by children nodes of other of the branch nodes.
9. The method of claim 1 wherein a size of one of the faux cell units is a multiple of a size of the layout unit of the device layout.