Patent US5880970A successfully refreshed from Google Patents.
US5880970A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Towards optimal Steiner tree routing in the presence of rectilinear obstacles
Assignee: LSI Corp
•
Filing: 1997-03-24
•
Granted: 1999-03-09
•
Expires: 2017-03-24
Abstract
Abstract An apparatus and method for locating a good approximation of optimal Steiner tree routing in the presence of rectilinear obstacles, including finding a Steiner tree on an escape graph. The escape graph is constructed by forming lines from given points (pins) and obstacles. Obstacles and the segments of obstacles are provided with lines parallel to that segment at a given minimum distance S min from the obstacle is constructed until it reaches either a boundary of an obstacle or a boundary of the core. For pins which do belong to a boundary of an obstacle, a ray, perpendicular to the segment of the boundary on which the pin is located is constructed from the pin and out from the obstacle until it reaches another obstacle or a boundary of the core. For pins which do not belong to an obstacle, vertical and horizontal lines are constructed. A Steiner tree may then be found on the escape graph by using any number of algorithms such as algorithm S and algorithm M. The solution to the problem of finding a Steiner tree for the escape graph also provides a suitable approximation of a Steiner tree for the original problem. This apparatus or method may be used to optimize the routing of conductive paths on integrated circuits.
Inventors
- 👤 Ranko Scepanovic
- 👤 Cheng-Liang Ding
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 23:14
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
158 words
A method of forming a graph for use in routing interconnections on an integrated circuit layout, wherein said integrated circuit layout is bounded by a core and includes obstacles and pins, said method comprising: forming a first set of lines parallel and in proximity to corresponding segments of boundaries of said obstacles, wherein the corresponding segments of the boundaries include at least one segment that is not an extreme top, extreme bottom, extreme right or extreme left edge of its corresponding obstacle, and wherein the lines of said first set of lines extend until either a boundary of one of said obstacles or a boundary of said core is reached; and forming a second set of lines that extend from pins residing on the boundaries of said obstacles in a direction perpendicular to and out from respective boundaries of said obstacles until either a boundary of one of said obstacles or a boundary of said core is reached.
Claim 2
Independent Claim
158 words
A method of forming a graph for use in routing interconnections on an integrated circuit layout, wherein said integrated circuit layout is bounded by a core and includes obstacles and pins, said method comprising: forming a first set of lines parallel and in proximity to corresponding segments of boundaries of said obstacles, wherein the corresponding segments of the boundaries include at least one segment that is not an extreme top, extreme bottom, extreme right or extreme left edge of its corresponding obstacle, and wherein the lines of said first set of lines extend until either a boundary of one of said obstacles or a boundary of said core is reached; and forming a second set of lines that extend from pins residing on the boundaries of said obstacles in a direction perpendicular to and out from respective boundaries of said obstacles until either a boundary of one of said obstacles or a boundary of said core is reached.
Claim 3
Dependent Claim
28 words
A method according to claim 1, wherein the first set of lines includes a line parallel and in proximity to each segment of the boundaries of said obstacles.
Claim 4
Dependent Claim
29 words
A method according to claim 1, wherein the second set of lines includes a line that extends from each pin residing on the boundary of each of said obstacles.
Claim 5
Dependent Claim
45 words
The method of claim 1, further comprising: forming a third set of mutually orthogonal lines through pins that do not reside on any of said obstacles and extending until either a boundary of one of said obstacles or a boundary of said core is reached.
Claim 6
Dependent Claim
25 words
A method according to claim 4, wherein two mutually orthogonal lines are formed through each pin that does not reside on any of said obstacles.
Claim 7
Dependent Claim
11 words
The method of claim 4, wherein said obstacles are rectilinear obstacles.
Claim 8
Dependent Claim
22 words
The method of claim 6, wherein said segments of the boundaries of said rectilinear obstacles are parallel to a Cartesian coordinate system.
Claim 9
Dependent Claim
19 words
The method of claim 7, wherein the segments of the core boundary are parallel to a Cartesian coordinate system.
Claim 10
Dependent Claim
45 words
The method of claim 4, wherein the step of forming said first set of lines includes the step of forming said first set of lines in a manner that the distance between said first set of lines and corresponding segments of said obstacles is zero.
Claim 11
Dependent Claim
50 words
The method of claim 4, wherein the step of forming said first set of lines includes the step of forming said first set of lines in a manner that the distance between said first set of lines and corresponding segments of said obstacles is given by a minimum allowable spacing.
Claim 12
Independent Claim
135 words
A method of routing interconnects for an integrated circuit layout that is bounded by a core includes obstacles and pins, said method comprising: forming an escape graph that includes the steps of: forming a first set of lines parallel and in proximity to corresponding segments of the boundaries of said obstacles, wherein the lines of said first set of lines extend until either a boundary of one of said obstacles or a boundary of said core is reached, and forming a second set of lines that extend from pins residing on the boundaries of said obstacles in a direction perpendicular to and out from respective boundaries of said obstacles until either a boundary of one of said obstacles or a boundary of said core is reached; and finding a Steiner tree in said escape graph.
Claim 13
Independent Claim
135 words
A method of routing interconnects for an integrated circuit layout that is bounded by a core includes obstacles and pins, said method comprising: forming an escape graph that includes the steps of: forming a first set of lines parallel and in proximity to corresponding segments of the boundaries of said obstacles, wherein the lines of said first set of lines extend until either a boundary of one of said obstacles or a boundary of said core is reached, and forming a second set of lines that extend from pins residing on the boundaries of said obstacles in a direction perpendicular to and out from respective boundaries of said obstacles until either a boundary of one of said obstacles or a boundary of said core is reached; and finding a Steiner tree in said escape graph.
Claim 14
Dependent Claim
56 words
The method of claim 11, wherein the step of forming said escape graph further includes the step of forming a third set of mutually orthogonal lines through pins that do not reside on any of said obstacles and extending until either a boundary of one of said obstacles or a boundary of said core is reached.
Claim 15
Dependent Claim
11 words
The method of claim 12, wherein said obstacles are rectilinear obstacles.
Claim 16
Dependent Claim
22 words
The method of claim 13, wherein said segments of the boundaries of said rectilinear obstacles are parallel to a Cartesian coordinate system.
Claim 17
Dependent Claim
19 words
The method of claim 14, wherein the segments of the core boundary are parallel to a Cartesian coordinate system.
Claim 18
Dependent Claim
45 words
The method of claim 12, wherein the step of forming said first set of lines includes the step of forming said first set of lines in a manner that the distance between said first set of lines and corresponding segments of said obstacles is zero.
Claim 19
Dependent Claim
50 words
The method of claim 12, wherein the step of forming said first set of lines includes the step of forming said first set of lines in a manner that the distance between said first set of lines and corresponding segments of said obstacles is given by a minimum allowable spacing.
Claim 20
Independent Claim
32 words
The method of either of claims 11 or 12, wherein said step of finding a Steiner tree includes the step of finding a Steiner tree using a spanning tree algorithm ("algorithm S").
Claim 21
Dependent Claim
132 words
The method of claim 18, wherein said spanning tree algorithm includes the steps of: (a) constructing Voronoi regions in said escape graph; (b) constructing a first graph including said pins, and edges connecting two of said pins respectively in said escape graph which extend between adjacent Voronoi regions; (c) constructing a second graph as a minimum spanning tree of said first graph; (d) constructing a third graph as a subgraph of said second graph including shortest paths in said escape graph corresponding to edges in said second graph; (e) constructing a fourth graph as a minimum spanning tree of said third graph; and (f) constructing said approximate Steiner tree from said fourth graph by deleting said point which constitute end points in said fourth graph and do not correspond to said pins.
Claim 22
Dependent Claim
38 words
The method of claim 19, wherein: step (b) further comprises computing weights for said edges in accordance with lengths thereof in said escape graph; and step (c) further comprises constructing said second graph in accordance with said weights.
Claim 23
Independent Claim
31 words
The method of either of claims 11 or 12, wherein said step of finding of Steiner tree includes the step of finding a Steiner tree using an maze-based algorithm ("algorithm M").
Claim 24
Dependent Claim
96 words
The method of claim 21, wherein said maze-based algorithm includes the steps of: (a) constructing a bounding box enclosing said pins; (b) selecting a source pin among said pins in a manner that said source pin is closest to the center of said bounding box, said source pin forming said initial point of said Steiner tree; (c) performing a maze expansion from said Steiner tree to include another pin that is not in said Steiner tree; and (d) performing step c until all of said pins in said circuit layout is included in said Steiner tree.
Claim 25
Dependent Claim
26 words
The method of claim 22, wherein said step of performing said maze expansion includes the step of performing a maze expansion in accordance with Lee's algorithm.
Claim 26
Dependent Claim
26 words
The method of claim 22, wherein said step of performing said maze expansion includes the step of performing a maze expansion in accordance with Soukup's algorithm.
Claim 27
Dependent Claim
26 words
The method of claim 22, wherein said step of performing a maze expansion includes the step of performing a maze expansion in accordance with Hadlock's algorithm.
References Cited (Backward Citations)
US4858143A
Cited
US4855929A
Cited
US4918614A
Cited
US5295082A
Cited
US5309370A
Cited
US5491641A
Cited
US5615128A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-08 | 2002-09-07 | 2003-03-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-08 | 2006-09-07 | 2007-03-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-08 | 2010-09-07 | 2011-03-09 | $7700.00 | Window Closed / Lapsed |