System and method for constructing spanning trees

Patent metadata

Field	Value
Publication number	US-10102328-B1
Application number	US-201615060020-A
Country	US
Kind code	B1
Filing date	Mar 3, 2016
Priority date	Mar 3, 2016
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

The present disclosure relates to a system and method for constructing spanning trees. Embodiments may include receiving, using at least one processor, a plurality of nodes associated with the integrated circuit design. In some embodiments, the plurality of node may be configured to be intercoupled by one or more combinations of edges. Embodiments may further include receiving a user-defined value at a graphical user interface. Embodiments may also include generating a routing graph with a subset of the one or more combinations of edges based upon, at least in part, the user-defined value and the position of each of the plurality of nodes. Embodiments may further include generating a spanning tree based upon, at least in part, at least one of: one or more wirelengths of the routing graph and one or more source-sink detour costs associated with the routing graph.

First claim

What is claimed is:

1. A computer-implemented method for constructing a spanning tree in an integrated circuit design comprising:
receiving, using at least one processor, a plurality of nodes associated with the integrated circuit design, wherein the plurality of nodes are configured to be intercoupled by one or more combinations of edges;
receiving a user-specified floating parameter at a graphical user interface;
generating a routing graph with a subset of the one or more combinations of edges based upon, at least in part, the user-specified floating parameter and the position of each of the plurality of nodes;
generating a spanning tree based upon, at least in part, at least one of: one or more wirelengths of the routing graph and one or more source-sink detour costs associated with the routing graph; and
applying the spanning tree in the electronic design of an integrated circuit to be fabricated.

2. The computer-implemented method of claim 1 , wherein the routing graph is one or more of a minimum spanning tree graph, a convex-hull graph, a partial convex-hull graph, and a minimum wirelength shortest path tree (MW-SPT).

3. The computer-implemented method of claim 2 , wherein the routing graph is the convex-hull graph when the user-defined value is greater than the number of the plurality of nodes and is one or more of: the minimum spanning tree graph, the partial convex-hull graph and the MW-SPT when the user-defined value is less than or equal to the number of the plurality of nodes.

4. The computer-implemented method of claim 1 , wherein generating the spanning tree is further based upon, at least in part, the user-specified floating parameter.

5. The computer-implemented method of claim 1 , wherein the subset of the one or more combinations of edges has fewer edges than the number of the plurality of nodes squared.

6. The computer-implemented method of claim 1 , wherein the spanning tree has a time complexity of less than or equal to O(n log n), wherein n corresponds with a number of edges.

7. The computer-implemented method of claim 6 , wherein the spanning tree is a minimum wirelength shortest path tree.

8. A system for constructing a spanning tree in an integrated circuit design comprising:
a computing device having at least one processor configured to receive a plurality of nodes associated with the integrated circuit design, wherein the plurality of nodes are configured to be intercoupled by one or more combinations of edges, receive a user-specified floating parameter at a graphical user interface, generate a routing graph with a subset of the one or more combinations of edges based upon, at least in part, the user-specified floating parameter and the position of each of the plurality of nodes, and generate a spanning tree based upon, at least in part, at least one of: one or more wirelengths of the routing graph and one or more source-sink detour costs associated with the routing graph, the at least one processor further configured to apply the spanning tree in the electronic design of an integrated circuit to be fabricated.

9. The system of claim 8 , wherein the routing graph is one or more of a minimum spanning tree graph, a convex-hull graph, a partial convex-hull graph, and a MW-SPT.

10. The system of claim 8 , wherein the routing graph is a minimum wirelength shortest path tree (MW-SPT).

11. The system of claim 8 , wherein the routing graph is the convex-hull graph when the user-defined value is greater than the number of the plurality of nodes and is one or more of the partial convex-hull graph and the MW-SPT when the user-defined value is less than or equal to the number of the plurality of nodes.

12. The system of claim 8 , wherein generating the spanning tree is further based upon, at least in part, the user-specified floating parameter.

13. The system of claim 8 , wherein the subset of the one or more combinations of edges has fewer edges than the number of the plurality of nodes squared.

14. The system of claim 8 , wherein the spanning tree has a time complexity of less than or equal to O(n log n), wherein n corresponds with a number of edges.

15. The system of claim 14 , wherein the spanning tree is a minimum wirelength shortest path tree.

16. A computer-implemented method for constructing a spanning tree comprising:
receiving, using at least one processor, a plurality of nodes, wherein the plurality of nodes are configured to be intercoupled by one or more combinations of edges;
receiving a user-defined value;
generating a routing graph with a subset of the one or more combinations of edges based upon, at least in part, the user-defined value and the position of each of the plurality of nodes, wherein the routing graph is a convex-hull graph when the user-defined value is greater than a number of the plurality of nodes and is one or more of a partial convex-hull graph and a minimum wirelength shortest path tree MW-SPT when the user-defined value is less than or equal to the number of the plurality of nodes;
generating a spanning tree based upon, at least in part, the routing graph; and
applying the spanning tree in the electronic design of an integrated circuit to be fabricated.

17. The computer-implemented method of claim 16 , wherein generating the spanning tree is further based upon, at least in part, at least one of: one or more wirelengths of the routing graph and one or more source-sink detour costs associated with the routing graph.

Assignees

• Cadence Design Systems Inc

Inventors

• Liu Wen-Hao
• Li Zhuo
• Alpert Charles Jay
• Yildiz Mehmet Can

Classifications

• G06F30/394 Primary

  Routing (G06F30/396 takes precedence) · CPC title

• G06F17/5077 Primary

  Physics · mapped topic