Patent US6952815B2 successfully refreshed from Google Patents.
US6952815B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Probabilistic routing method and apparatus
Assignee: Cadence Design Systems Inc
•
Filing: 2002-01-13
•
Granted: 2005-10-04
•
Expires: 2022-01-13
Abstract
Abstract Some embodiments of the invention provide a method of routing several nets in a region of a design layout. Each net includes a set of pins in the region. In some embodiments, the method partitions the region into several sub-regions that have a number of edges between them. The method (1) for each particular net and each particular edge, identifies an edge-intersect probability that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, and (2) uses the identified edge-intersect probabilities to identify routes for the nets. A potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins. In other embodiments, the method partitions the region into several sub-regions that have a number of paths between them. The method (1) for each particular net and each particular path, identifies a path-use probability that specifies the probability that a set of potential routes for the particular net will use the particular path, and (2) uses the identified path-use probabilities to identify routes for the nets.
Inventors
- 👤 Steven Teig
- 👤 Oscar Buset
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:24
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392; G06F30/394; G06F30/3953; G11; G11B; G11B7/00; G11B7/08; G11B7/085; G11B7/0857; G11B7/08582
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
112 words
A method of routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the method comprising: a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions, b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified edge-intersect probabilities to identify routes for the nets.
Claim 2
Independent Claim
112 words
A method of routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the method comprising: a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions, b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified edge-intersect probabilities to identify routes for the nets.
Claim 3
Dependent Claim
44 words
The method of claim 1 , wherein, for each particular net, the edge-intersect probability for each particular edge equals the number of potential routes of the particular net that intersect the particular edge divided by the number of potential routes of the particular net.
Claim 4
Dependent Claim
48 words
The method of claim 2 , wherein identifying the edge-intersect probabilities for each particular net comprises: a) identifying the set of sub-regions that contain each particular net's pins; b) based on each particular net's identified set of sub-regions, retrieving the particular net's edge-intersect probabilities from a storage structure.
Claim 5
Dependent Claim
59 words
The computer readable medium of claim 2 , wherein the set of instructions for identifying the edge-intersect probabilities for each particular net comprises sets of instructions for: a) identifying the set of sub-regions that contain each particular net's pins; b) based on each particular net's identified set of sub-regions, retrieving the particular net's edge-intersect probabilities from a storage structure.
Claim 6
Dependent Claim
66 words
The method of claim 1 , wherein identifying the edge-intersect probabilities comprises: for each particular net: a) identifying the set of potential routes for the particular net; b) for each particular edge, computing the number of potential routes of the particular net that intersect the particular edge; c) dividing the computed number of each particular edge by the number of potential routes of the particular net.
Claim 7
Dependent Claim
27 words
The method of claim 5 , wherein identifying the set of potential routes for each particular net comprises retrieving the set of routes from a storage structure.
Claim 8
Dependent Claim
28 words
The method of claim 5 , wherein identifying the set of potential routes for each particular net comprises generating the set of routes after partitioning the IC region.
Claim 9
Dependent Claim
50 words
The method of claim 1 further comprising: for each particular edge, computing a sum of the probabilities identified for the particular edge for all the nets; using the summed probabilities for the edges to predict congestion of the edges; routing the nets based on the predicted congestion of the edges.
Claim 10
Dependent Claim
39 words
The method of claim 1 , wherein using the identified probabilities to identify routes for the nets comprises: a) using the edge-intersect probabilities to predict congestion of the edges; b) based on the predicted congestion, identifying routes for nets.
Claim 11
Dependent Claim
58 words
The method of claim 1 , wherein using the identified probabilities to identify routes for the nets comprises: a) using the edge-intersect probabilities to derive an edge-intersect cost for each edge; b) using the potential routes and the edge-intersect costs to formulate a linear-programming (“LP”) problem: c) solving the LP problem to identify one route for each net.
Claim 12
Dependent Claim
34 words
The method of claim 10 , wherein the LP problem is an integer linear programming (“ILP”) problem, and solving the ILP problem results in an ILP solution that specifies one route for each net.
Claim 13
Dependent Claim
47 words
The method of claim 10 , wherein solving the LP problem results in a real-number solution for each net, wherein using the identified probabilities to identify routes for the nets further comprises converting the real-numbered solutions to integer solutions that specify only one route for each net.
Claim 14
Independent Claim
112 words
A method of routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the method comprising: a) partitioning the region into several sub-regions, wherein a plurality of paths exist between said sub-regions, b) for each particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will use the particular path, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified path-use probabilities to identify routes for the nets.
Claim 15
Independent Claim
112 words
A method of routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the method comprising: a) partitioning the region into several sub-regions, wherein a plurality of paths exist between said sub-regions, b) for each particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will use the particular path, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified path-use probabilities to identify routes for the nets.
Claim 16
Dependent Claim
43 words
The method of claim 13 , for each particular net, the path-use probability for each particular path equals the number of potential routes of the particular net that use the particular path divided by the number of potential routes of the particular net.
Claim 17
Dependent Claim
48 words
The method of claim 14 , wherein identifying the path-use probabilities for each particular net comprises: a) identifying the set of sub-regions that contain each particular net's pins; b) based on each particular net's identified set of sub-regions, retrieving the particular net's path-use probabilities from a storage structure.
Claim 18
Dependent Claim
66 words
The method of claim 13 , wherein identifying the path-use probabilities comprises: for each particular net: a) identifying the set of potential routes for the particular net; b) for each particular path, computing the number of potential routes of the particular net that use the particular path; c) dividing the computed number of each particular path by the number of potential routes of the particular net.
Claim 19
Dependent Claim
27 words
The method of claim 16 , wherein identifying the set of potential routes for each particular net comprises retrieving the set of routes from a storage structure.
Claim 20
Dependent Claim
28 words
The method of claim 16 , wherein identifying the set of potential routes for each particular net comprises generating the set of routes after partitioning the IC region.
Claim 21
Dependent Claim
50 words
The method of claim 13 further comprising: for each particular path, computing a sum of the probabilities identified for the particular path for all the nets; using the summed probabilities for the paths to predict congestion of the paths; routing the nets based on the predicted congestion of the paths.
Claim 22
Dependent Claim
39 words
The method of claim 13 , wherein using the identified probabilities to identify routes for the nets comprises: a) using the path-use probabilities to predict congestion of the paths; b) based on the predicted congestion, identifying routes for nets.
Claim 23
Dependent Claim
58 words
The method of claim 13 , wherein using the identified probabilities to identify routes for the nets comprises: a) using the path-use probabilities to derive an path-use cost for each path; b) using the potential routes and the path-use costs to formulate a linear-programming (“LP”) problem; c) solving the LP problem to identify one route for each net.
Claim 24
Dependent Claim
124 words
A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for: a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions, b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified edge-intersect probabilities to identify routes for the nets.
Claim 25
Dependent Claim
124 words
A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for: a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions, b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified edge-intersect probabilities to identify routes for the nets.
Claim 26
Dependent Claim
46 words
The computer readable medium of claim 22 , wherein, for each particular net, the edge-intersect probability for each particular edge equals the number of potential routes of the particular net that intersect the particular edge divided by the number of potential routes of the particular net.
Claim 27
Dependent Claim
124 words
A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for: a) partitioning the region into several sub-regions, wherein a plurality of paths exist between said sub-regions, b) for each particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will use the particular path, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified path-use probabilities to identify routes for the nets.
Claim 28
Dependent Claim
124 words
A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“IC”) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for: a) partitioning the region into several sub-regions, wherein a plurality of paths exist between said sub-regions, b) for each particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will use the particular path, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins; and c) using the identified path-use probabilities to identify routes for the nets.
Claim 29
Dependent Claim
46 words
The computer readable medium of claim 24 , wherein, for each particular net, the path-use probability for each particular path equals the number of potential routes of the particular net that use the particular path divided by the number of potential routes of the particular net.
Claim 30
Dependent Claim
59 words
The computer readable medium of claim 25 , wherein the set of instructions for identifying the path-use probabilities for each particular net comprises sets of instructions for: a) identifying the set of sub-regions that contain each particular net's pins; b) based on each particular net's identified set of sub-regions, retrieving the particular net's path-use probabilities from a storage structure.
References Cited (Backward Citations)
US4673966A
Cited
US4593363A
Cited
US4615011A
Cited
US4855929A
Cited
US5097422A
Cited
JPS6415947A
Cited
US4782193A
Cited
US5267176A
Cited
JPH04677B2
Cited
US5251147A
Cited
JPH03173471A
Cited
US5375069A
Cited
US6216252B1
Cited
US5634093A
Cited
US5281151A
Cited
JPH05102305A
Cited
US5657242A
Cited
JPH05243379A
Cited
US5532934A
Cited
US5360948A
Cited
US5618744A
Cited
US5723908A
Cited
US5566078A
Cited
JPH0786407A
Cited
US5640327A
Cited
US5636125A
Cited
US6155725A
Cited
US5914887A
Cited
US5757089A
Cited
US5633479A
Cited
US5859449A
Cited
US5587923A
Cited
US5784289A
Cited
US6088519A
Cited
US5635736A
Cited
US5742086A
Cited
US5578840A
Cited
US5973376A
Cited
US6407434B1
Cited
US5811863A
Cited
US5822214A
Cited
US5777360A
Cited
US5889677A
Cited
US5650653A
Cited
US6448591B1
Cited
US5637920A
Cited
JPH09162279A
Cited
US5757656A
Cited
US6226560B1
Cited
US5663891A
Cited
US5838583A
Cited
US5798936A
Cited
US6067409A
Cited
US20010003843A1
Cited
US6219832B1
Cited
US6035108A
Cited
US6150193A
Cited
US6209123B1
Cited
US5980093A
Cited
US5898597A
Cited
US6378121B2
Cited
US6123736A
Cited
US6070108A
Cited
US6068662A
Cited
US6058254A
Cited
US6330707B1
Cited
US6260179B1
Cited
US6128767A
Cited
US6134702A
Cited
US6249902B1
Cited
US6557145B2
Cited
US6385758B1
Cited
US6301686B1
Cited
US6253363B1
Cited
US6260183B1
Cited
US6289495B1
Cited
US6175950B1
Cited
US6230306B1
Cited
US6247167B1
Cited
US6324674B2
Cited
US6327694B1
Cited
US6442743B1
Cited
JP2000082743A
Cited
US6436804B2
Cited
US6262487B1
Cited
US20020182844A1
Cited
US6412102B1
Cited
US6307256B1
Cited
US6324675B1
Cited
US20010009031A1
Cited
US6412097B1
Cited
US6295634B1
Cited
US6327693B1
Cited
US6463575B1
Cited
US6415422B1
Cited
US6405358B1
Cited
US6316838B1
Cited
US6546540B1
Cited
US6401234B1
Cited
US6446245B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-10-03 | 2009-04-04 | 2009-10-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-10-03 | 2013-04-04 | 2013-10-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-10-03 | 2017-04-04 | 2017-10-04 | $7700.00 | Window Closed / Lapsed |