US6289495B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for local optimization of the global routing
Assignee: Bell Semiconductor LLC
•
Filing: 1998-04-17
•
Granted: 2001-09-11
•
Expires: 2018-04-17
Abstract
Abstract A method for routing nets in an integrated circuit design, said method comprising the steps of forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction, globally routing said integrated circuit design in accordance with said routing graph, dividing the routing graph into strips, for each strip in the routing graph, generating a general task for optimizing the routing in the strip, solving general tasks in parallel by assigning different processors different strips to process.
Inventors
- 👤 Pedja Raspopovic
- 👤 Ranko Scepanovic
- 👤 Alexander E. Andreev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 06:09
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
94 words
A method for routing nets in an integrated circuit design, said method comprising the following steps: a. Forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. globally routing said integrated circuit design in accordance with said routing graph; c. dividing the routing graph into strips; d. for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. solving general tasks in parallel by assigning different processors different strips to process.
Claim 2
Independent Claim
94 words
A method for routing nets in an integrated circuit design, said method comprising the following steps: a. Forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. globally routing said integrated circuit design in accordance with said routing graph; c. dividing the routing graph into strips; d. for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. solving general tasks in parallel by assigning different processors different strips to process.
Claim 3
Dependent Claim
21 words
The method of claim 1 wherein general tasks are generated with respect to each net fragment which passes in a strip.
Claim 4
Dependent Claim
25 words
The method of claim 2 wherein the solving of general tasks is repeated for a predetermined number of times with respect to a particular strip.
Claim 5
Dependent Claim
29 words
The method of claim 1 wherein an edge in the routing graph has an associated penalty and the solution of a general task is a function of the penalty.
Claim 6
Dependent Claim
23 words
The method of claim 4 wherein the penalty is a function of an occupancy value and a capacity value associated with the edge.
Claim 7
Dependent Claim
19 words
The method of claim 4 wherein the solving of a general task involves determining a vector of minimal penalty.
Claim 8
Dependent Claim
37 words
The method of claim 1 wherein a second routing graph is formed, nets are rerouted in accordance with the second routing graph, and steps c, d and e are repeated with respect to said second routing graph.
Claim 9
Dependent Claim
29 words
The method of claim 1 wherein a strip comprises a small number of lines comprising edges in the first direction and edges in the second direction connecting said lines.
Claim 10
Dependent Claim
21 words
The method of claim 1 , wherein at least one of said strips includes more than one pin from a net.
Claim 11
Independent Claim
101 words
A apparatus for routing nets in an integrated circuit design, said apparatus comprising: a. means for forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. means for globally routing said integrated circuit design in accordance with said routing graph; c. means for dividing the routing graph into strips; d. means for, for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. means for solving general tasks in parallel by assigning different processors different strips to process.
Claim 12
Independent Claim
101 words
A apparatus for routing nets in an integrated circuit design, said apparatus comprising: a. means for forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. means for globally routing said integrated circuit design in accordance with said routing graph; c. means for dividing the routing graph into strips; d. means for, for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. means for solving general tasks in parallel by assigning different processors different strips to process.
Claim 13
Dependent Claim
21 words
The apparatus of claim 10 wherein general tasks are generated with respect to each net fragment which passes in a strip.
Claim 14
Dependent Claim
25 words
The apparatus of claim 11 wherein the solving of general tasks is repeated for a predetermined number of times with respect to a particular strip.
Claim 15
Dependent Claim
29 words
The apparatus of claim 10 wherein an edge in the routing graph has an associated penalty and the solution of a general task is a function of the penalty.
Claim 16
Dependent Claim
23 words
The apparatus of claim 13 wherein the penalty is a function of an occupancy value and a capacity value associated with the edge.
Claim 17
Dependent Claim
19 words
The apparatus of claim 13 wherein the solving of a general task involves determining a vector of minimal penalty.
Claim 18
Dependent Claim
41 words
The apparatus of claim 10 further comprising means for forming a second routing graph, means for rerouting nets in accordance with the second routing graph, and means for reutilizing elements c, d and e with respect to said second routing graph.
Claim 19
Dependent Claim
29 words
The apparatus of claim 10 wherein a strip comprises a small number of lines comprising edges in the first direction and edges in the second direction connecting said lines.
Claim 20
Dependent Claim
21 words
The apparatus of claim 10 , wherein at least one of said strips includes more than one pin from a net.
Claim 21
Dependent Claim
123 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 forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. a computer encoded instruction for globally routing said integrated circuit design in accordance with said routing graph; c. a computer encoded instruction for dividing the routing graph into strips; d. a computer encoded instruction for for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. a computer encoded instruction for solving general tasks in parallel by assigning different processors different strips to process.
Claim 22
Dependent Claim
123 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 forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. a computer encoded instruction for globally routing said integrated circuit design in accordance with said routing graph; c. a computer encoded instruction for dividing the routing graph into strips; d. a computer encoded instruction for for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. a computer encoded instruction for solving general tasks in parallel by assigning different processors different strips to process.
Claim 23
Dependent Claim
22 words
The storage medium of claim 19 , wherein at least one of said strips includes more than one pin from a net.
References Cited (Backward Citations)
US5568322A
Cited
US5615128A
Cited
US5880970A
Cited
US5491641A
Cited
US5636125A
Cited
US5682322A
Cited
US5742510A
Cited
US5745363A
Cited
US5495419A
Cited
US5568636A
Cited
US5638293A
Cited
US5578840A
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-09-10 | 2005-03-12 | 2005-09-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-09-10 | 2009-03-12 | 2009-09-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-09-10 | 2013-03-12 | 2013-09-11 | $7700.00 | Window Closed / Lapsed |