Patent US5856927A successfully refreshed from Google Patents.
US5856927A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for automatically routing circuits of very large scale integration (VLSI)
Assignee: Philips Semiconductors Inc
•
Filing: 1995-05-01
•
Granted: 1999-01-05
•
Expires: 2015-05-01
Abstract
Abstract An automated routing tool for routing interconnections between circuit elements, standard cells and/or cell blocks of cell-based designs which incorporates the best features of both currently known gate array routing techniques with currently known cell-based routing techniques. The invention eliminates the disadvantages of permitting the detailed router to adjust the relative positions of the circuit elements, standard cells and/or cell blocks during the detailed routing process. The method employs a topology manager which iteratively compacts the circuit topology while at the same time optimizing the routing of the interconnections among the circuit elements, standard cells and/or cell blocks of the circuit design. The method employs bin-based global routing, which identifies expandable boundaries and which provides input to a compaction routine which expands or contracts the expandable areas in accordance with the result of the global routing process. The detailed routing step is not performed until after the relative positions of the circuit elements, cells and/or cell blocks have been already fixed.
Inventors
- 👤 Jacob Greidinger
- 👤 Mark R. Hartoog
- 👤 Ara Markosian
- 👤 Christine Fawcett
- 👤 Eugenia Gelfund
- 👤 Prasad Sakhamuri
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 19:04
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394; H; H10; H10D; H10D89/00; H10D89/10
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
149 words
A method of automatically routing interconnections among a plurality of circuit elements comprising a circuit, the circuit elements having one or more connectors, the interconnections defined by a netlist, the method comprising the steps of: determining initial placement of the circuit elements; globally routing all nets of the netlist losing expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; moving the circuit elements in accordance with the results of said step of globally routing; if the moving of the circuit elements by said step of moving is greater than a predetermined amount: reputing said steps of globally routing and moving; otherwise, globally routing all nets of the netlist using no expandable boundaries; routing all nets of the netlist using a detailed router; and generating an output representative of the process layers for manufacturing the circuit.
Claim 2
Independent Claim
149 words
A method of automatically routing interconnections among a plurality of circuit elements comprising a circuit, the circuit elements having one or more connectors, the interconnections defined by a netlist, the method comprising the steps of: determining initial placement of the circuit elements; globally routing all nets of the netlist losing expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; moving the circuit elements in accordance with the results of said step of globally routing; if the moving of the circuit elements by said step of moving is greater than a predetermined amount: reputing said steps of globally routing and moving; otherwise, globally routing all nets of the netlist using no expandable boundaries; routing all nets of the netlist using a detailed router; and generating an output representative of the process layers for manufacturing the circuit.
Claim 3
Dependent Claim
19 words
The method of claim 1 further comprising the step of setting constraints on the movement of the circuit elements.
Claim 4
Dependent Claim
17 words
The method of claim 1 further comprising the step of prerouting one or more of the nets.
Claim 5
Dependent Claim
19 words
The method of claim 3, further comprising the step of setting constraints on the movement of the circuit elements.
Claim 6
Independent Claim
108 words
A method of automatically routing interconnections among a plurality of elements on an integrated circuit comprising the steps of: obtaining the initial element placement; globally routing a plurality of said interconnections using expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; moving said elements in accordance with the results of said step of globally routing; repeating said steps of globally routing and moving until the movement of said elements pursuant to said step of moving is not greater than a predetermined amount; and globally routing a plurality of said interconnections using no expandable boundaries.
Claim 7
Independent Claim
108 words
A method of automatically routing interconnections among a plurality of elements on an integrated circuit comprising the steps of: obtaining the initial element placement; globally routing a plurality of said interconnections using expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; moving said elements in accordance with the results of said step of globally routing; repeating said steps of globally routing and moving until the movement of said elements pursuant to said step of moving is not greater than a predetermined amount; and globally routing a plurality of said interconnections using no expandable boundaries.
Claim 8
Dependent Claim
31 words
The method of claim 5, further comprising the step of using a detailed router to route said interconnections subsequent to the step of globally routing said interconnections using no expandable boundaries.
Claim 9
Dependent Claim
34 words
The method of claim 6, further comprising the step of generating an output representative of the process layers for manufacturing the circuit, said step performed subsequent to said step of using a detailed router.
Claim 10
Dependent Claim
24 words
The method of claim 5, wherein the step of moving moves said elements in accordance with the minimum capacities specified for the expandable boundaries.
Claim 11
Dependent Claim
38 words
The method of claim 8, wherein said step of moving further moves said elements in accordance with any constraints input by the user of said method, said constraints entered by said user prior to said step of moving.
Claim 12
Dependent Claim
42 words
The method of claim 5, further comprising the step of prerouting at least one interconnection prior to the step of globally routing using expandable boundaries, so that said prerouted interconnections are not re-routed during said step of global routing using expandable boundaries.
Claim 13
Dependent Claim
44 words
The method of claim 10, further comprising the step of prerouting at least one interconnection prior to the step of globally routing using no expandable boundaries, so that said prerouted interconnections are not re-routed during said step of global routing using no expandable boundaries.
Claim 14
Dependent Claim
29 words
The method of claim 5, wherein the step of obtaining the initial element placement comprises obtaining the initial element placement from a netlist generated by an element placement method.
Claim 15
Dependent Claim
62 words
The method of claim 5, further comprising, between the step of globally routing using expandable boundaries and the step of moving, the steps of: generating a grid of bin boundaries over the element placement of the present iteration; identifying all expandable bin boundaries and areas; and logically routing said interconnections through expandable and non-expandable boundaries while optimizing the cost of said routing.
Claim 16
Dependent Claim
59 words
The method of claim 13, further comprising between the step of logically routing said interconnections and the step of moving, the steps of: adding sufficient tracks to said expandable areas on which overflows in capacity exist; and reducing the number of tracks in each expandable area to minimum capacity without creating overflows on any other expandable or non-expandable area.
Claim 17
Dependent Claim
47 words
The method of claim 14, further comprising between the step of reducing the number of tracks in each expandable area and the step of moving, the step of determining the minimum tracks necessary for each expandable area, said determination useable by said method during step of moving.
Claim 18
Independent Claim
116 words
An apparatus for automatically routing interconnections among a plurality of elements on an integrated circuit, said apparatus comprising: means for obtaining the initial element placement; means for globally routing a plurality of said interconnections using expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; means for moving said elements in accordance with the results of said step of globally routing; means for repeating said global routing and moving until the movement of said elements during a single iteration of said moving is not greater than a predetermined amount; and means for globally routing a plurality of said interconnections using no expandable boundaries.
Claim 19
Independent Claim
116 words
An apparatus for automatically routing interconnections among a plurality of elements on an integrated circuit, said apparatus comprising: means for obtaining the initial element placement; means for globally routing a plurality of said interconnections using expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; means for moving said elements in accordance with the results of said step of globally routing; means for repeating said global routing and moving until the movement of said elements during a single iteration of said moving is not greater than a predetermined amount; and means for globally routing a plurality of said interconnections using no expandable boundaries.
Claim 20
Dependent Claim
112 words
The apparatus of claim 16, further comprising: means for generating a grid of bin boundaries over the element placement of the present iteration; means for identifying all expandable bin boundaries and areas; means for logically routing said interconnections through expandable and non-expandable boundaries while optimizing the cost of said routing; means for adding sufficient tracks to said expandable areas on which overflows in capacity exist, thereby eliminating overflows; means for reducing the number of tracks in each expandable area to minimum capacity without creating overflows on any other expandable or non-expandable area; and means for determining the minimum tracks necessary for each expandable area, said determination useable by said step of moving.
Claim 21
Dependent Claim
172 words
A computer program product comprising a computer-usable medium having computer-readable code embodied therein for automatically routing interconnections among a plurality of elements on an integrated circuit, the computer-readable code comprising: an initial placement module, which is configured to obtain the initial element placement; a first global routing module, which is configured to globally route a plurality of said interconnections using expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; a movement module, which is configured to move said elements in accordance with the results from said first global routing module; an iteration module, which is configured to repeat the procedures dictated by said first global routing module and said movement module until the involvement of said components during an iteration of said first global routing module and said movement module is not greater than a predetermined amount; and a second global routing module, which is configured to globally route a plurality of said interconnections using no expandable boundaries.
Claim 22
Dependent Claim
172 words
A computer program product comprising a computer-usable medium having computer-readable code embodied therein for automatically routing interconnections among a plurality of elements on an integrated circuit, the computer-readable code comprising: an initial placement module, which is configured to obtain the initial element placement; a first global routing module, which is configured to globally route a plurality of said interconnections using expandable boundaries, wherein said expandable boundaries comprise expandable physical regions including bin boundaries coextensive with channel spaces through which nets may be routed; a movement module, which is configured to move said elements in accordance with the results from said first global routing module; an iteration module, which is configured to repeat the procedures dictated by said first global routing module and said movement module until the involvement of said components during an iteration of said first global routing module and said movement module is not greater than a predetermined amount; and a second global routing module, which is configured to globally route a plurality of said interconnections using no expandable boundaries.
Claim 23
Dependent Claim
53 words
The computer program product of claim 18, further comprising: a detailed router module, which is configured to route said interconnections subsequent to the global routing of said interconnections using no expandable boundaries; and an output generation module, which is configured to generate an output representative of the process layers for manufacturing the circuit.
Claim 24
Dependent Claim
48 words
The computer program product of claim 19, further comprising a prerouting module, which is configured to permit the prerouting at least one interconnection prior to the step of globally routing using expandable boundaries, so that said prerouted interconnections are not re-routed during the remainder of the routing process.
References Cited (Backward Citations)
US3629843A
Cited
US4580228A
Cited
US4593363A
Cited
US4754408A
Cited
US5144563A
Cited
US5361214A
Cited
US5307286A
Cited
US5309370A
Cited
US5349536A
Cited
US5359538A
Cited
US5224056A
Cited
US5521837A
Cited
US5465218A
Cited
US5483461A
Cited
US5550748A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-04 | 2002-07-06 | 2003-01-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-04 | 2006-07-06 | 2007-01-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-04 | 2010-07-06 | 2011-01-05 | $7700.00 | Window Closed / Lapsed |