Representing device layout using tree structure

• US 20060085779A1
• Filed: 12/05/2005
• Published: 04/20/2006
• Est. Priority Date: 06/09/2003
• Status: Active Grant

• Current Assignee: Siemens Industry Software Limited (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Lin, Kuoching
• Granted Patent: US 7,607,117 B2
• Time in Patent Office: Days
• US Class Current: 716/124
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

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.

Claims

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 functional components within a selected portion of an area occupied by of the layout, the method comprising:

dividing the area occupied by the device layout into one or more main area portions;

representing each main area portion as a corresponding root node on the tree structure;

dividing each main area portion into equally sized sub-areas;

representing each sub-area as a branch node that is a child of the root node corresponding to the main portion comprising the sub-area;

continuing to divide each sub-area further into equally sized sub-areas and representing each sub-area as a branch node, until each of the sub-areas corresponds to a layout unit of the device layout; and

representing each of the sub-areas corresponding to the layout unit of the device layout as a leaf node on the tree structure.

2. The method of claim 1 wherein the layout the programmable device comprises pre-defined layout units with each layout unit occupying an area with a size that is a multiple of the area occupied by a basic layout unit of the device.

3. The method of claim 1 wherein the programmable device is an FPGA.

5. The method of claim 1 wherein one of the main area portions comprises a core area of the area occupied by the programmable device layout.

6. The method of claim 1 wherein the main area portions comprise I/O areas of the device layout.

8. The method of claim 1 further comprising:

representing a non-uniform layout unit straddling across multiple sub-areas as a separate root node;

assigning faux cell units to represent area of the device layout occupied by the non-uniform straddling layout unit;

representing the faux cell units as leaf nodes under the root node representing one of the main area portions of the area occupied by device layout; and

assigning pointers to each of the faux cell units to point to the root node representing the non-uniform straddling layout unit.

9. The method of claim 8, wherein a area size of one of the faux cell units is a multiple of a area size of a basic layout unit of the device layout.

15. The computer readable medium of claim 11 wherein the device being represented by the tree structure is an FPGA, PAL, CPLD, a gate array ASIC or a CPLD.

4. The method of claim I wherein the programmable device is a PAL, a PLA, a gate array ASIC, or a CPLD.

7. (canceled)

10. (canceled)

11. 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.

12. The computer readable medium of claim 11 wherein one of the main portions of the physical area occupied by the device corresponds to a core area of the device.

13. The computer readable medium of claim 11 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 the other branch nodes.

14. The computer readable medium of claim 11 wherein the device layout comprises pre-determined layout units with each layout unit occupying an area of a size that is a multiple of the area occupied by a basic layout unit of the device layout.

16. The computer readable medium of claim 11 further comprising faux leaf nodes for representing the physical area occupied a non-uniform layout unit that straddles across multiple sub-areas and a separate root node to represent the non-uniform straddling layout unit.

17. The computer readable medium of claim 16, wherein the faux leaf nodes have a pointer field for associating the faux leaf nodes with the root node representing the non-uniform straddling layout unit.

18. The computer readable medium of claim 16 wherein a size of a sub-area associated with the faux nodes is a multiple of a size of an area associated with a basic layout unit of the device.

19. The computer readable medium of claim 16 wherein the faux nodes are represented at multiple different levels of the tree structure.

20. 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.

21. 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.

22. (canceled)

23. (canceled)

24. (canceled)

25. 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.

26. 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,