US6175950B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for hierarchical global routing descend
Assignee: Bell Semiconductor LLC
•
Filing: 1998-04-17
•
Granted: 2001-01-16
•
Expires: 2018-04-17
Abstract
Abstract Net routing is optimized in an integrated circuit device by dividing an integrated circuit design with a first group of substantially parallel lines in a first direction and with a group of substantially parallel lines in a second direction, with the second direction being substantially perpendicular to the first direction. A first routing graph is formed with vertices corresponding to locations where lines in the first direction and lines in the second direction cross, and nets are globally routed as a function of the first routing graph. The integrated circuit design is further subdivided with a second group of substantially parallel lines in the first direction, and a second routing graph is formed with vertices corresponding to locations where lines in the first and second groups of substantially parallel lines in the first direction cross lines in the group of substantially parallel lines in the second direction. For a net globally routed using the first routing graph, a first local net is formed in a first fragment of the second routing graph, and the first local net is rerouted within the first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of the edge penalty values.
Inventors
- 👤 Ranko Scepanovic
- 👤 Alexander E. Andreev
- 👤 Elyar E. Gasanov
- 👤 Pedja Raspopovic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 06:08
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
219 words
A method for optimizing the routing of nets in an integrated circuit device, said method comprising the following steps: a. dividing an integrated circuit design with a first plurality of substantially parallel lines in a first direction; b. dividing said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction; c. forming a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross; d. globally routing nets as a function of said first routing graph; e. further dividing said integrated circuit design with a second plurality of substantially parallel lines in said first direction; f. forming a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; g. for a net globally routed in step d, forming a first local net in a first fragment of said second routing graph; and h. rerouting said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
Claim 2
Independent Claim
219 words
A method for optimizing the routing of nets in an integrated circuit device, said method comprising the following steps: a. dividing an integrated circuit design with a first plurality of substantially parallel lines in a first direction; b. dividing said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction; c. forming a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross; d. globally routing nets as a function of said first routing graph; e. further dividing said integrated circuit design with a second plurality of substantially parallel lines in said first direction; f. forming a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; g. for a net globally routed in step d, forming a first local net in a first fragment of said second routing graph; and h. rerouting said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein some lines of said plurality of substantially parallel lines in a second direction correspond to routing channels.
Claim 4
Dependent Claim
24 words
The method of claim 2 wherein the other lines in said plurality of substantially parallel lines in a second direction correspond to cell columns.
Claim 5
Dependent Claim
35 words
The method of claim 2 wherein the first and second routing graphs each cover the same area and the second routing graph has approximately twice the number of vertices as does the first routing graph.
Claim 6
Dependent Claim
104 words
The method of claim 1 wherein the following additional steps are taken: i. further dividing said integrated circuit design with a third plurality of substantially parallel lines in said first direction; j. forming a third routing graph with vertices corresponding to locations where lines in said first, second and third pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; k. for a second net previously routed, forming a second local net in a second fragment of said third routing graph; and l. rerouting said second local net within said second fragment.
Claim 7
Dependent Claim
39 words
The method of claim 5 wherein said first routing graph, second routing graph and third routing graph each cover the same area and the respective number of vertices of said routing graphs are in the approximate ratio of 1:2:4.
Claim 8
Dependent Claim
32 words
The method of claim 1 wherein said local net comprises at least one pin from the net globally routed in step d and an edge that was previously in the net's routing.
Claim 9
Dependent Claim
27 words
The method of claim 1 wherein step h comprises calculating penalty function values corresponding to all possible reroutings of said first local net within said first fragment.
Claim 10
Dependent Claim
29 words
The method of claim 8 wherein the first local net is rerouted so as to have the minimum total of edge penalty values corresponding to edges in the rerouting.
Claim 11
Independent Claim
233 words
An apparatus for optimizing the routing of nets in an integrated circuit device, said apparatus comprising: a. means for dividing an integrated circuit design with a first plurality of substantially parallel lines in a first direction; b. means for dividing said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction; c. means for forming a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross; d. means for globally routing nets as a function of said first routing graph; e. means for further dividing said integrated circuit design with a second plurality of substantially parallel lines in said first direction; f. means for forming a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; g. means for a net globally routed by said globally routing means, forming a first local net in a first fragment of said second routing graph; and h. means for rerouting said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
Claim 12
Independent Claim
233 words
An apparatus for optimizing the routing of nets in an integrated circuit device, said apparatus comprising: a. means for dividing an integrated circuit design with a first plurality of substantially parallel lines in a first direction; b. means for dividing said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction; c. means for forming a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross; d. means for globally routing nets as a function of said first routing graph; e. means for further dividing said integrated circuit design with a second plurality of substantially parallel lines in said first direction; f. means for forming a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; g. means for a net globally routed by said globally routing means, forming a first local net in a first fragment of said second routing graph; and h. means for rerouting said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
Claim 13
Dependent Claim
23 words
The apparatus of claim 10 wherein some lines of said plurality of substantially parallel lines in a second direction correspond to routing channels.
Claim 14
Dependent Claim
24 words
The apparatus of claim 11 wherein the other lines in said plurality of substantially parallel lines in a second direction correspond to cell columns.
Claim 15
Dependent Claim
35 words
The apparatus of claim 11 wherein the first and second routing graphs each cover the same area and the second routing graph has approximately twice the number of vertices as does the first routing graph.
Claim 16
Dependent Claim
107 words
The apparatus of claim 10 , further comprising: i. means for further dividing said integrated circuit design with a third plurality of substantially parallel lines in said first direction; j. means for forming a third routing graph with vertices corresponding to locations where lines in said first, second and third pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; k. means for a second net previously routed, forming a second local net in a second fragment of said third routing graph; and l. means for rerouting said second local net within said second fragment.
Claim 17
Dependent Claim
39 words
The apparatus of claim 14 wherein said first routing graph, second routing graph and third routing graph each cover the same area and the respective number of vertices of said routing graphs are in the approximate ratio of 1:2:4.
Claim 18
Dependent Claim
33 words
The apparatus of claim 10 wherein said local net comprises at least one pin from the net globally routed by said means d and an edge that was previously in the net's routing.
Claim 19
Dependent Claim
31 words
The apparatus of claim 10 wherein rerouting performed by said means h comprises calculating penalty function values corresponding to all possible reroutings of said first local net within said first fragment.
Claim 20
Dependent Claim
29 words
The apparatus of claim 17 wherein the first local net is rerouted so as to have the minimum total of edge penalty values corresponding to edges in the rerouting.
Claim 21
Dependent Claim
240 words
A computer storage medium for optimizing the routing of nets in an integrated circuit device, comprising: a computer storage medium readable by a computer; and means recorded on said storage medium for directing the computer to: a. divide an integrated circuit design with a first plurality of substantially parallel lines in a first direction; b. divide said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction; c. form a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross; d. globally route nets as a function of said first routing graph; e. further divide said integrated circuit design with a second plurality of substantially parallel lines in said first direction; f. form a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; g. form, for a net globally routed according to the instruction in element d, a first local net in a first fragment of said second routing graph; and h. reroute said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
Claim 22
Dependent Claim
240 words
A computer storage medium for optimizing the routing of nets in an integrated circuit device, comprising: a computer storage medium readable by a computer; and means recorded on said storage medium for directing the computer to: a. divide an integrated circuit design with a first plurality of substantially parallel lines in a first direction; b. divide said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction; c. form a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross; d. globally route nets as a function of said first routing graph; e. further divide said integrated circuit design with a second plurality of substantially parallel lines in said first direction; f. form a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction; g. form, for a net globally routed according to the instruction in element d, a first local net in a first fragment of said second routing graph; and h. reroute said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
References Cited (Backward Citations)
US5583788A
Cited
US5568322A
Cited
US5615128A
Cited
US5491641A
Cited
US5682322A
Cited
US5495419A
Cited
US5745363A
Cited
US5742510A
Cited
US5636125A
Cited
US5638293A
Cited
US5568636A
Cited
US5578840A
Cited
US5661663A
Cited
US5838585A
Cited
US5712793A
Cited
US5909376A
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-01-16 | 2004-07-17 | 2005-01-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-16 | 2008-07-17 | 2009-01-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-16 | 2012-07-17 | 2013-01-16 | $7700.00 | Window Closed / Lapsed |