US5615128A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Towards optimal steiner tree routing in the presence of rectilinear obstacles
Assignee: LSI Corp
•
Filing: 1996-02-12
•
Granted: 1997-03-25
•
Expires: 2016-02-12
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. The lines are constructed until they 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-10-30 03:53
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
210 words
In a process for fabricating an integrated circuit chip, a series of operational steps for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, said steps comprising: (a) constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; (b) constructing Voronoi regions in said escape graph; (c) 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; (d) constructing a second graph as a minimum spanning tree of said first graph; (e) 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; (f) constructing a fourth graph as a minimum spanning tree of said third graph; and (g) constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 2
Dependent Claim
210 words
In a process for fabricating an integrated circuit chip, a series of operational steps for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, said steps comprising: (a) constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; (b) constructing Voronoi regions in said escape graph; (c) 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; (d) constructing a second graph as a minimum spanning tree of said first graph; (e) 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; (f) constructing a fourth graph as a minimum spanning tree of said third graph; and (g) constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 3
Dependent Claim
40 words
A process as in claim 1, in which: step (c) further comprises computing weights for said edges in accordance with lengths thereof in said escape graph; and step (d) further comprises constructing said second graph in accordance with said weights.
Claim 4
Dependent Claim
54 words
A process as in claim 1, in which step (a) comprises the substeps of: (a1) constructing first rectilinear lines parallel to said edges of said components and second rectilinear lines passing through said pins; and (a2) constructing said escape graph as including said pins, and first and second rectilinear lines which interconnect said pins.
Claim 5
Dependent Claim
28 words
A process as in claim 3, in which step (a1) comprises constructing said first and second rectilinear lines as being spaced from said components by a predetermined distance.
Claim 6
Dependent Claim
201 words
A computer implemented method for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, comprising the steps of: (a) constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; (b) constructing Voronoi regions in said escape graph; (c) 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; (d) constructing a second graph as a minimum spanning tree of said first graph; (e) 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; (f) constructing a fourth graph as a minimum spanning tree of said third graph; and (g) constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 7
Dependent Claim
201 words
A computer implemented method for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, comprising the steps of: (a) constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; (b) constructing Voronoi regions in said escape graph; (c) 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; (d) constructing a second graph as a minimum spanning tree of said first graph; (e) 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; (f) constructing a fourth graph as a minimum spanning tree of said third graph; and (g) constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 8
Dependent Claim
40 words
A method as in claim 5, in which: step (c) further comprises computing weights for said edges in accordance with lengths thereof in said escape graph; and step (d) further comprises constructing said second graph in accordance with said weights.
Claim 9
Dependent Claim
54 words
A method as in claim 5, in which step (a) comprises the substeps of: (a1) constructing first rectilinear lines parallel to said edges of said components and second rectilinear lines passing through said pins; and (a2) constructing said escape graph as including said pins, and first and second rectilinear lines which interconnect said pins.
Claim 10
Dependent Claim
28 words
A method as in claim 7, in which step (a1) comprises constructing said first and second rectilinear lines as being spaced from said components by a predetermined distance.
Claim 11
Dependent Claim
210 words
In a process for routing an integrated circuit chip, a series of operational steps for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, said steps comprising: (a) constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; (b) constructing Voronoi regions in said escape graph; (c) 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; (d) constructing a second graph as a minimum spanning tree of said first graph; (e) 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; (f) constructing a fourth graph as a minimum spanning tree of said third graph; and (g) constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 12
Dependent Claim
210 words
In a process for routing an integrated circuit chip, a series of operational steps for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, said steps comprising: (a) constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; (b) constructing Voronoi regions in said escape graph; (c) 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; (d) constructing a second graph as a minimum spanning tree of said first graph; (e) 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; (f) constructing a fourth graph as a minimum spanning tree of said third graph; and (g) constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 13
Dependent Claim
40 words
A process as in claim 9, in which: step (c) further comprises computing weights for said edges in accordance with lengths thereof in said escape graph; and step (d) further comprises constructing said second graph in accordance with said weights.
Claim 14
Dependent Claim
54 words
A process as in claim 9, in which step (a) comprises the substeps of: (a1) constructing first rectilinear lines parallel to said edges of said components and second rectilinear lines passing through said pins; and (a2) constructing said escape graph as including said pins, and first and second rectilinear lines which interconnect said pins.
Claim 15
Dependent Claim
28 words
A process as in claim 11, in which step (a1) comprises constructing said first and second rectilinear lines as being spaced from said components by a predetermined distance.
Claim 16
Independent Claim
242 words
A system for fabricating an integrated circuit having a net of pins on edges of rectilinear components located thereon, comprising: means for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for said net of pins such that said routing path extends between said components, said constructing means comprising: first processing means for constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; and second processing means for constructing said approximate MRST, the second processing means comprising: third processing means for constructing Voronoi regions in said escape graph; and for 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; fourth processing means for constructing a second graph as a minimum spanning tree of said first graph; fifth processing means for 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; sixth processing means for constructing a fourth graph as a minimum spanning tree of said third graph; and seventh processing means for constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 17
Independent Claim
242 words
A system for fabricating an integrated circuit having a net of pins on edges of rectilinear components located thereon, comprising: means for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for said net of pins such that said routing path extends between said components, said constructing means comprising: first processing means for constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; and second processing means for constructing said approximate MRST, the second processing means comprising: third processing means for constructing Voronoi regions in said escape graph; and for 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; fourth processing means for constructing a second graph as a minimum spanning tree of said first graph; fifth processing means for 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; sixth processing means for constructing a fourth graph as a minimum spanning tree of said third graph; and seventh processing means for constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 18
Dependent Claim
42 words
A system as in claim 13, in which: the third processing means further computes weights for said edges in accordance with lengths thereof in said escape graph; and the fourth processing means further constructs said second graph in accordance with said weights.
Claim 19
Dependent Claim
59 words
A system as in claim 13, in which the first processing means comprises: eighth processing means for constructing first rectilinear lines parallel to said edges of said components and second rectilinear lines passing through said pins; and ninth processing means for constructing said escape graph as including said pins, and first and second rectilinear lines which interconnect said pins.
Claim 20
Dependent Claim
29 words
A system as in claim 15, in which the eighth processing means constructs said first and second rectilinear lines as being spaced from said components by a predetermined distance.
Claim 21
Independent Claim
242 words
A system for routing an integrated circuit having a net of pins on edges of rectilinear components located thereon, comprising: means for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for said net of pins such that said routing path extends between said components, said constructing means comprising: first processing means for constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; and second processing means for constructing said approximate MRST, the second processing means comprising: third processing means for constructing Voronoi regions in said escape graph; and for 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; fourth processing means for constructing a second graph as a minimum spanning tree of said first graph; fifth processing means for 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; sixth processing means for constructing a fourth graph as a minimum spanning tree of said third graph; and seventh processing means for constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 22
Independent Claim
242 words
A system for routing an integrated circuit having a net of pins on edges of rectilinear components located thereon, comprising: means for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for said net of pins such that said routing path extends between said components, said constructing means comprising: first processing means for constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components; and second processing means for constructing said approximate MRST, the second processing means comprising: third processing means for constructing Voronoi regions in said escape graph; and for 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; fourth processing means for constructing a second graph as a minimum spanning tree of said first graph; fifth processing means for 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; sixth processing means for constructing a fourth graph as a minimum spanning tree of said third graph; and seventh processing means for constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.
Claim 23
Dependent Claim
42 words
A system as in claim 17, in which: the third processing means further computes weights for said edges in accordance with lengths thereof in said escape graph; and the fourth processing means further constructs said second graph in accordance with said weights.
Claim 24
Dependent Claim
59 words
A system as in claim 17, in which the first processing means comprises: eighth processing means for constructing first rectilinear lines parallel to said edges of said components and second rectilinear lines passing through said pins; and ninth processing means for constructing said escape graph as including said pins, and first and second rectilinear lines which interconnect said pins.
Claim 25
Dependent Claim
29 words
A system as in claim 19, in which the eighth processing means constructs said first and second rectilinear lines as being spaced from said components by a predetermined distance.
References Cited (Backward Citations)
US4858143A
Cited
US4855929A
Cited
US4918614A
Cited
US5295082A
Cited
US5309370A
Cited
US5491641A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-24 | 2000-09-23 | 2001-03-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-24 | 2004-09-23 | 2005-03-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-24 | 2008-09-23 | 2009-03-25 | $7700.00 | Window Closed / Lapsed |