Patent US6519751B2 successfully refreshed from Google Patents.
US6519751B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for accurate crosspoint allocation in VLSI area routing
Assignee: Intel Corp
•
Filing: 2000-03-31
•
Granted: 2003-02-11
•
Expires: 2020-03-31
Abstract
Abstract In one embodiment the invention is a method. The method includes finding costs to route a net to a set of crosspoints on a boundary. The method also includes propagating the costs to a succeeding set of nodes.
Inventors
- 👤 Mysore Sriram
- 👤 May Huang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 15:35
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
188 words
A method comprising: defining a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of successive boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal; selecting from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; repeating the selecting from a successive boundary for each successive boundary until a successive boundary of the last area is reached; for each preceding boundary having more than one lowest-cost node, changing, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from the lowest-cost node of the successive boundary to the preceding boundary; and identifying a signal route through the selected lowest-cost nodes.
Claim 2
Independent Claim
188 words
A method comprising: defining a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of successive boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal; selecting from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; repeating the selecting from a successive boundary for each successive boundary until a successive boundary of the last area is reached; for each preceding boundary having more than one lowest-cost node, changing, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from the lowest-cost node of the successive boundary to the preceding boundary; and identifying a signal route through the selected lowest-cost nodes.
Claim 3
Dependent Claim
19 words
The method of claim 1 , wherein the cost of a route depends on a distance the route covers.
Claim 4
Dependent Claim
25 words
The method of claim 1 , further comprising: defining valid crosspoints as crosspoints on either side of where a previously routed signal crosses a boundary.
Claim 5
Dependent Claim
46 words
The method of claim 3 , further comprising: further defining, on a boundary adjacent to a terminator node, valid crosspoints as crosspoints limited to an area one design-rule width less than the area of the terminator node, within an area leading directly to the terminator node.
Claim 6
Dependent Claim
22 words
The method of claim 1 , wherein the lowest-cost route is a route including a group of horizontal and vertical routing segments.
Claim 7
Dependent Claim
14 words
The method of claim 1 , wherein the lowest-cost node is a terminator node.
Claim 8
Dependent Claim
18 words
The method of claim 1 , further comprising: defining valid crosspoints as crosspoints free from shadows of obstructions.
Claim 9
Dependent Claim
27 words
The method of claim 1 , wherein the cost of a route between nodes of successive boundaries is increased if the route is routed around an obstruction.
Claim 10
Dependent Claim
34 words
The method of claim 1 , wherein the cost of a route through a particular area is dependent on the presence of pre-routed signals that have already been routed through the same particular area.
Claim 11
Dependent Claim
23 words
The method of claim 9 , wherein the cost of a route which creates a L-overlap configuration with the pre-routed signal is increased.
Claim 12
Dependent Claim
23 words
The method of claim 9 , wherein the cost of a route which creates an X-overlap configuration with the pre-routed signal is increased.
Claim 13
Dependent Claim
22 words
The method of claim 1 , wherein the cost of a route is dependent on the type of signal to be routed.
Claim 14
Dependent Claim
204 words
A machine-readable medium embodying instructions which, when executed by a machine, cause a processor to perform a method comprising: defining a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of successive boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal; selecting from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; repeating the selecting from a successive boundary for each successive boundary until a successive boundary of the last area is reached; for each preceding boundary having more than one lowest-cost node, changing, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from the lowest-cost node of the successive boundary to the preceding boundary; and identifying a signal route through the selected lowest-cost nodes.
Claim 15
Dependent Claim
204 words
A machine-readable medium embodying instructions which, when executed by a machine, cause a processor to perform a method comprising: defining a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of successive boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal; selecting from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; repeating the selecting from a successive boundary for each successive boundary until a successive boundary of the last area is reached; for each preceding boundary having more than one lowest-cost node, changing, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from the lowest-cost node of the successive boundary to the preceding boundary; and identifying a signal route through the selected lowest-cost nodes.
Claim 16
Dependent Claim
21 words
The machine-readable medium of claim 13 , wherein the cost of a route is dependent on a distance the route covers.
Claim 17
Dependent Claim
41 words
The machine-readable medium of claim 13 further embodying instructions which, when executed by a processor, cause the processor to perform the method further comprising: defining valid crosspoints as crosspoints on either side of where a previously routed signal crosses a boundary.
Claim 18
Dependent Claim
62 words
The machine-readable medium of claim 15 further embodying instructions which, when executed by a processor, cause the processor to perform the method further comprising: further defining, on a boundary adjacent to a terminator node, valid crosspoints as crosspoints limited to an area one design-rule width less than the area of the terminator node, within an area leading directly to the terminator node.
Claim 19
Dependent Claim
23 words
The machine-readable medium of claim 13 , wherein the lowest-cost route is a route including a group of horizontal and vertical routing segments.
Claim 20
Dependent Claim
15 words
The machine-readable medium of claim 13 , wherein the lowest-cost node is a terminator node.
Claim 21
Dependent Claim
34 words
The machine-readable medium of claim 13 further embodying instructions which, when executed by a processor, cause the processor to perform the method further comprising: defining valid crosspoints as crosspoints free from shadows of obstructions.
Claim 22
Dependent Claim
28 words
The machine-readable medium of claim 13 , wherein the cost of a route between nodes of successive boundaries is increased if the route is routed around an obstruction.
Claim 23
Dependent Claim
30 words
The machine-readable medium of claim 13 , wherein the cost of a route is dependent on the presence of pre-routed signals that have already been routed through a corresponding area.
Claim 24
Dependent Claim
24 words
The machine-readable medium of claim 21 , wherein the cost of a route which creates a L-overlap configuration with the pre-routed signal is increased.
Claim 25
Dependent Claim
24 words
The machine-readable medium of claim 21 , wherein the cost of a route which creates an X-overlap configuration with the pre-routed signal is increased.
Claim 26
Dependent Claim
23 words
The machine-readable medium of claim 13 , wherein the cost of a route is dependent on the type of signal to be routed.
Claim 27
Independent Claim
221 words
A system comprising: a processor; a memory coupled with the processor; an input device coupled with the processor; and wherein the processor to define a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of different boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal; the processor further to select from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; the processor further to select from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; the processor further to repeat the selection from a successive boundary for each successive boundary until a successive boundary of the last area is reached; the processor further to, for each preceding boundary having more than one lowest-cost node, change the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from a successive boundary to the preceding boundary; and the processor to identify a signal route through the selected lowest-cost nodes.
Claim 28
Independent Claim
221 words
A system comprising: a processor; a memory coupled with the processor; an input device coupled with the processor; and wherein the processor to define a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of different boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal; the processor further to select from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; the processor further to select from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; the processor further to repeat the selection from a successive boundary for each successive boundary until a successive boundary of the last area is reached; the processor further to, for each preceding boundary having more than one lowest-cost node, change the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from a successive boundary to the preceding boundary; and the processor to identify a signal route through the selected lowest-cost nodes.
Claim 29
Independent Claim
166 words
An apparatus comprising: means for defining a group of contiguous areas being separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of different boundaries having costs, a first area including a first terminator node of the signal and a last area including a second terminator node of the signal; means for selecting from a first boundary-a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; for each successive boundary, means for selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; means for changing, for each preceding boundary having more than one lowest-cost node, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from a successive boundary to the preceding boundary; and means for identifying a signal route through the selected lowest-cost nodes.
Claim 30
Independent Claim
166 words
An apparatus comprising: means for defining a group of contiguous areas being separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of different boundaries having costs, a first area including a first terminator node of the signal and a last area including a second terminator node of the signal; means for selecting from a first boundary-a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary; for each successive boundary, means for selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary; means for changing, for each preceding boundary having more than one lowest-cost node, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from a successive boundary to the preceding boundary; and means for identifying a signal route through the selected lowest-cost nodes.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-02-10 | 2006-08-12 | 2007-02-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-02-10 | 2010-08-12 | 2011-02-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-02-10 | 2014-08-12 | 2015-02-11 | $7700.00 | Window Closed / Lapsed |