Method and apparatus for parallel simultaneous global and detail routing

• US 6,324,674 B2
• Filed: 04/17/1998
• Issued: 11/27/2001
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Andreev, Alexander E., Gasanov, Elyar E., Raspopovic, Pedja
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): DO, THUAN V
• Application Number:
  US09/062,309
• Publication Number:
  US 20010018759A1
• Time in Patent Office: 1,320 Days
• Field of Search: 395/500.08, 716/5, 716/7, 716/12, 716/13, 716/14
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method for routing nets in an integrated circuit design, said method comprising the steps of dividing the integrated circuit design with lines in a first direction and lines in a second direction, forming a routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction, routing nets as a function of said routing graph with parallel processors operating substantially simultaneously, determining the relative wire congestion among different areas in the integrated circuit design, and rerouting nets passing though areas with a relatively high wire congestion.

Claims

1. A method for routing nets in an integrated circuit design, said method comprising the following steps:

a. dividing the integrated circuit design with lines in a first direction and lines in a second direction;

b. partitioning at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

c. forming a routing graph having vertices and edges, wherein the vertices correspond to locations where lines in the first direction cross lines in the second direction, and wherein the edges correspond to said lines in the first and second directions; and

d. routing the nets, including the plural smaller nets, by routing interconnections comprising said nets on the edges of said routing graph, said routing being performed with parallel processors operating substantially simultaneously.

2. The method of claim 1 wherein the lines in the first direction are evenly spaced apart.

3. The method of claim 1 wherein the lines in the first direction are 2^k predetermined units apart.

4. The method of claim 3 wherein the units are grids.

5. The method of claim 3 comprising the following additional steps:

e. dividing the integrated circuit design with additional lines in the first direction such that lines in the first direction are spaced 2<sup>k−

1</sup> units apart;

f. forming a second routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction;

g. rerouting nets as a function of said routing graph with parallel processors operating substantially simultaneously.

6. The method of claim 5 comprising the further step of dividing the second routing graph into small segments and rerouting within a small segment portions of nets passing though the small segment.

7. The method of claim 6 wherein the rerouting of the nets in step g is accomplished as a function of penalties computed for each edge in the second routing graph.

8. The method of claim 7 wherein the penalty for an edge is a function of both an occupancy value and a capacity value associated with the edge.

9. The method of claim 8 wherein penalty values are recomputed as nets are rerouted.

10. The method of claim 8 wherein an occupancy value for an edge is a function of the potential occupancy of an edge.

11. A apparatus for routing nets in an integrated circuit design, said apparatus comprising:

a. means for dividing the integrated circuit design with lines in a first direction and lines in a second direction;

b. means for partitioning at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

c. means for forming a routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction; and

d. means for routing the nets, including the plural smaller nets, as a function of said routing graph with parallel processors operating substantially simultaneously.

12. The apparatus of claim 11 wherein the lines in the first direction are evenly spaced apart.

13. The apparatus of claim 11 wherein the lines in the first direction are 2^k predetermined units apart.

14. The apparatus of claim 13 wherein the units are grids.

15. The apparatus of claim 13 further comprising:

e. means for dividing the integrated circuit design with additional lines in the first direction such that lines in the first direction are spaced 2<sup>k−

1</sup> units apart;

f. means for forming a second routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction;

g. means for rerouting nets as a function of said routing graph with parallel processors operating substantially simultaneously.

16. The apparatus of claim 15 comprising the further step of dividing the second routing graph into small segments and rerouting within a small segment portions of nets passing though the small segment.

17. The apparatus of claim 16 wherein the rerouting of the nets is accomplished as a function of penalties computed for each edge in the second routing graph.

18. The apparatus of claim 17 wherein the penalty for an edge is a function of both an occupancy value and a capacity value associated with the edge.

19. The apparatus of claim 18 wherein penalty values are recomputed as nets are rerouted.

20. The apparatus of claim 18 wherein an occupancy value for an edge is a function of the potential occupancy of an edge.

21. A computer encoded storage medium with instructions thereon for routing nets in an integrated circuit design, said storage medium comprising:

a. a computer encoded instruction for dividing the integrated circuit design with lines in a first direction and lines in a second direction;

b. a computer encoded instruction for partitioning at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

c. a computer encoded instruction for forming a routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction; and

d. a computer encoded instruction for routing the nets, including the plural smaller nets, as a function of said routing graph with parallel processors operating substantially simultaneously.

22. A method for routing nets in an integrated circuit design, said method comprising:

a. dividing an integrated circuit design using a first group of lines oriented in a first direction and a second group of lines oriented in a second direction;

b. partitioning at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

c. defining a routing graph, having edges, such that the edges correspond to the first group of lines and the second group of lines;

d. routing the nets in the integrated circuit design, including the plural smaller nets, by routing interconnections comprising said nets on the edges of said routing graph;

e. optimizing the routing performed in step d;

f. adding more lines oriented in the first direction to the first group; and

g. repeating steps c-e.

23. A method according to claim 22, wherein steps c-e are repeated without adding additional lines to the second group.

24. A method according to claim 22, wherein the first direction is perpendicular to the second direction.

25. A method according to claim 22, further comprising a step of repeating steps f and g.

26. A method according to claim 25, further comprising a step of performing detailed routing after said repeating step.

27. A method according to claim 22, further comprising a step of repeating steps f and g three additional times.

28. A method according to claim 27, further comprising a step of performing detailed routing after said repeating step.

29. A method according to claim 22, wherein a number of lines is added at each repetition of step f so as to double a total number of lines in the first group.

30. A method according to claim 22, wherein an effect of each repetition of step f is to reduce spacing between lines in the first group.

31. A method according to claim 22, wherein optimizing in step e includes identifying congested areas and rerouting nets passing through said congested areas.

32. An apparatus for routing nets in an integrated circuit design, said apparatus comprising:

a. means for dividing an integrated circuit design using a first group of lines oriented in a first direction and a second group of lines oriented in a second direction;

b. means for partitioning at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

c. means for defining a routing graph by the first group of lines and the second group of lines;

d. means for routing the nets in the integrated circuit design, including the plural smaller nets, using the routing graph;

e. means for optimizing the routing performed by means d;

f. means for adding more lines oriented in the first direction to the first group; and

g. means for repeating steps performed by means c-e.

33. A computer-readable medium storing computer-executable process steps for routing nets in an integrated circuit design, said process steps comprising steps to:

a. divide an integrated circuit design using a first group of lines oriented in a first direction and a second group of lines oriented in a second direction;

b. partition at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

c. define a routing graph by the first group of lines and the second group of lines;

d. route the nets in the integrated circuit design, including the plural smaller nets, using the routing graph;

e. optimize the routing performed in step d;

f. add more lines oriented in the first direction to the first group; and

g. repeat steps c-e.

34. A method for routing nets in an integrated circuit design, said method comprising the following steps:

a. partitioning at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

b. forming a routing graph having vertices and edges; and

c. routing the nets, including the plural smaller nets, by routing interconnections comprising said nets on the edges of said routing graph, said routing being performed with parallel processors operating substantially simultaneously.

35. An apparatus for routing nets in an integrated circuit design, said apparatus comprising:

a. means for partitioning at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

b. means for forming a routing graph having vertices and edges; and

c. means for routing the nets, including the plural smaller nets, by routing interconnections comprising said nets on the edges of said routing graph, said routing being performed with parallel processors operating substantially simultaneously.

36. A computer-readable medium storing computer-executable process steps for routing nets in an integrated circuit design, said process steps comprising steps to:

a. partition at least one of the nets into plural smaller nets, said partitioning being performed by connecting pins of said at least one net with edges and then removing plural of the edges to form a spanning tree;

b. form a routing graph having vertices and edges; and

c. route the nets, including the plural smaller nets, by routing interconnections comprising said nets on the edges of said routing graph, said routing being performed with parallel processors operating substantially simultaneously.