US6324674B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for parallel simultaneous global and detail routing
Assignee: Bell Semiconductor LLC
•
Filing: 1998-04-17
•
Granted: 2001-11-27
•
Expires: 2018-04-17
Abstract
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.
Inventors
- 👤 Alexander E. Andreev
- 👤 Elyar E. Gasanov
- 👤 Ranko Scepanovic
- 👤 Pedja Raspopovic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:25
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
147 words
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.
Claim 2
Independent Claim
147 words
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.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein the lines in the first direction are evenly spaced apart.
Claim 4
Dependent Claim
18 words
The method of claim 1 wherein the lines in the first direction are 2 k predetermined units apart.
Claim 5
Dependent Claim
10 words
The method of claim 3 wherein the units are grids.
Claim 6
Dependent Claim
79 words
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 k−1 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.
Claim 7
Dependent Claim
32 words
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.
Claim 8
Dependent Claim
30 words
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.
Claim 9
Dependent Claim
27 words
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.
Claim 10
Dependent Claim
14 words
The method of claim 8 wherein penalty values are recomputed as nets are rerouted.
Claim 11
Dependent Claim
22 words
The method of claim 8 wherein an occupancy value for an edge is a function of the potential occupancy of an edge.
Claim 12
Independent Claim
127 words
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.
Claim 13
Independent Claim
127 words
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.
Claim 14
Dependent Claim
16 words
The apparatus of claim 11 wherein the lines in the first direction are evenly spaced apart.
Claim 15
Dependent Claim
18 words
The apparatus of claim 11 wherein the lines in the first direction are 2 k predetermined units apart.
Claim 16
Dependent Claim
10 words
The apparatus of claim 13 wherein the units are grids.
Claim 17
Dependent Claim
82 words
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 k−1 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.
Claim 18
Dependent Claim
32 words
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.
Claim 19
Dependent Claim
27 words
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.
Claim 20
Dependent Claim
27 words
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.
Claim 21
Dependent Claim
14 words
The apparatus of claim 18 wherein penalty values are recomputed as nets are rerouted.
Claim 22
Dependent Claim
22 words
The apparatus of claim 18 wherein an occupancy value for an edge is a function of the potential occupancy of an edge.
Claim 23
Dependent Claim
146 words
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.
Claim 24
Dependent Claim
146 words
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.
Claim 25
Independent Claim
157 words
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.
Claim 26
Independent Claim
157 words
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.
Claim 27
Dependent Claim
20 words
A method according to claim 22 , wherein steps c-e are repeated without adding additional lines to the second group.
Claim 28
Dependent Claim
17 words
A method according to claim 22 , wherein the first direction is perpendicular to the second direction.
Claim 29
Dependent Claim
17 words
A method according to claim 22 , further comprising a step of repeating steps f and g.
Claim 30
Dependent Claim
19 words
A method according to claim 25 , further comprising a step of performing detailed routing after said repeating step.
Claim 31
Dependent Claim
20 words
A method according to claim 22 , further comprising a step of repeating steps f and g three additional times.
Claim 32
Dependent Claim
19 words
A method according to claim 27 , further comprising a step of performing detailed routing after said repeating step.
Claim 33
Dependent Claim
33 words
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.
Claim 34
Dependent Claim
26 words
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.
Claim 35
Dependent Claim
24 words
A method according to claim 22 , wherein optimizing in step e includes identifying congested areas and rerouting nets passing through said congested areas.
Claim 36
Independent Claim
158 words
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.
Claim 37
Independent Claim
158 words
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.
Claim 38
Dependent Claim
149 words
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.
Claim 39
Dependent Claim
149 words
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.
Claim 40
Independent Claim
97 words
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.
Claim 41
Independent Claim
97 words
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.
Claim 42
Independent Claim
100 words
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.
Claim 43
Independent Claim
100 words
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.
Claim 44
Dependent Claim
102 words
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.
Claim 45
Dependent Claim
102 words
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.
References Cited (Backward Citations)
US5568322A
Cited
US5491641A
Cited
US5615128A
Cited
US5636125A
Cited
US5495419A
Cited
US5682322A
Cited
US5742510A
Cited
US5745363A
Cited
US5568636A
Cited
US5638293A
Cited
US5578840A
Cited
US5822214A
Cited
US5661663A
Cited
US5712793A
Cited
US5808899A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-11-26 | 2005-05-28 | 2005-11-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-11-26 | 2009-05-28 | 2009-11-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-11-26 | 2013-05-28 | 2013-11-27 | $7700.00 | Window Closed / Lapsed |