Patent US6829757B1 successfully refreshed from Google Patents.
US6829757B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for generating multi-layer routes
Assignee: Cadence Design Systems Inc
•
Filing: 2002-02-12
•
Granted: 2004-12-07
•
Expires: 2022-02-12
Abstract
Abstract Some embodiments of the invention provide a method of generating a multi-layer topological path for a layout that has multiple layers. This method specifies a set of path expansions from a first topological item to a second topological item on a first layer of the layout. For a potential via expansion from the second topological item to a third topological item on a second layer of the layout, the method (1) identifies a first region on the first layer for the second topological item, (2) identifies a second region on the second layer the third topological item, (3) determines whether an intersection of the first and second regions is sufficiently large to contain a via, and (4) if the intersection is sufficiently large, adds the potential via expansion to the specified set of path expansions.
Inventors
- 👤 Steven Teig
- 👤 Andrew Caldwell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:52
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
134 words
For a layout that has multiple layers, a method of generating a multi-layer topological path comprising: a) specifying a set of path expansions from a first topological item to a second topological item, wherein the second topological item is on a first layer of the layout; and b) for a potential via expansion from the second topological item to a third topological item on a second layer of the layout, identifying a first region on the first layer for the second topological item; identifying a second region on the second layer for the third topological item; determining whether an intersection of the first and second regions is larger than a threshold area; and if the intersection is larger than the threshold area, adding the potential via expansion to the specified set of path expansions.
Claim 2
Dependent Claim
134 words
For a layout that has multiple layers, a method of generating a multi-layer topological path comprising: a) specifying a set of path expansions from a first topological item to a second topological item, wherein the second topological item is on a first layer of the layout; and b) for a potential via expansion from the second topological item to a third topological item on a second layer of the layout, identifying a first region on the first layer for the second topological item; identifying a second region on the second layer for the third topological item; determining whether an intersection of the first and second regions is larger than a threshold area; and if the intersection is larger than the threshold area, adding the potential via expansion to the specified set of path expansions.
Claim 3
Dependent Claim
22 words
The method of claim 1 , wherein if the intersection is not larger than the threshold area, discarding the potential via expansion.
Claim 4
Dependent Claim
55 words
The method of claim 1 further comprising: before specifying the set of path expansions, decomposing the layout into a plurality of faces, wherein each face has a set of edges and an interior space between the edges; wherein at least one of the second and third topological items represents an interior space of a face.
Claim 5
Dependent Claim
40 words
The method of claim 3 , wherein the second topological item represents an interior space of a first face on the first layer, and the third topological item represents an interior space of a second face on the second layer.
Claim 6
Dependent Claim
13 words
The method of claim 3 , wherein the layout is an IC layout.
Claim 7
Dependent Claim
38 words
The method of claim 5 , wherein the IC layout includes a plurality of routable elements, wherein decomposing the layout comprises: specifying a plurality of nodes along boundaries of the routable elements; and defining edges between the nodes.
Claim 8
Dependent Claim
23 words
The method of claim 1 , wherein each path expansion starts at a source topological item and ends with a destination topological item.
Claim 9
Dependent Claim
176 words
A computer program stored on a computer readable medium, wherein the computer program generates, for a layout that has multiple layers, a multi-layer topological path, the computer program comprising: a) a first set of instructions for specifying a set of path expansions from a first topological item to a second topological item, wherein the second topological item is on a first layer of the layout; b) for a potential via expansion from the second topological item to a third topological item on a second layer of the layout, a second set of instructions for identifying a first region on the first layer for the second topological item; a third set of instructions for identifying a second region on the second layer for the third topological item; a fourth set of instructions for determining whether an intersection of the first and second regions is larger than a threshold area; and a fifth set of instructions for adding the potential via expansion to the specified set of path expansions, when the intersection is larger than the threshold area.
Claim 10
Dependent Claim
176 words
A computer program stored on a computer readable medium, wherein the computer program generates, for a layout that has multiple layers, a multi-layer topological path, the computer program comprising: a) a first set of instructions for specifying a set of path expansions from a first topological item to a second topological item, wherein the second topological item is on a first layer of the layout; b) for a potential via expansion from the second topological item to a third topological item on a second layer of the layout, a second set of instructions for identifying a first region on the first layer for the second topological item; a third set of instructions for identifying a second region on the second layer for the third topological item; a fourth set of instructions for determining whether an intersection of the first and second regions is larger than a threshold area; and a fifth set of instructions for adding the potential via expansion to the specified set of path expansions, when the intersection is larger than the threshold area.
Claim 11
Dependent Claim
33 words
The computer program of claim 8 further comprising a sixth set of instructions for identifying another potential expansion from the second topological item when the intersection is not larger than the threshold area.
Claim 12
Dependent Claim
62 words
The computer program of claim 8 further comprising: a sixth set of instruction for decomposing, before specifying the set of path expansions, the layout into a plurality of faces, wherein each face has a set of edges and an interior space between the edges; wherein at least one of the second and third topological items represents an interior space of a face.
Claim 13
Dependent Claim
40 words
The computer program of claim 10 , wherein the second topological item represents an interior space of first face on the first layer, and the third topological item represents an interior space of a second face on the second layer.
Claim 14
Dependent Claim
14 words
The computer program of claim 10 , wherein the layout is an IC layout.
Claim 15
Dependent Claim
53 words
The computer program of claim 12 , wherein the IC layout includes a plurality of routable elements, wherein the sixth set of instructions comprises: a seventh set of instructions for specifying a plurality of nodes along boundaries of the routable elements; and an eight set of instructions for defining edges between the nodes.
Claim 16
Dependent Claim
24 words
The computer program of claim 13 , wherein each path expansion starts at a source topological item and ends with a destination topological item.
Claim 17
Dependent Claim
121 words
For an integrated circuit layout that has multiple layers, a method of generating a multi-layer topological path comprising: a) identifying a set of path expansions from a first topological item to a second topological item on a first layer of the layout; b) identifying a first region on the first layer for the second topological item, and a second region on the second layer for a third topological item that is reachable from the second topological item through a via expansion; c) determining whether an intersection of the first and second regions is larger than a threshold area; and d) adding the potential via expansion to the specified set of path expansions when the intersection is larger than the threshold area.
Claim 18
Dependent Claim
121 words
For an integrated circuit layout that has multiple layers, a method of generating a multi-layer topological path comprising: a) identifying a set of path expansions from a first topological item to a second topological item on a first layer of the layout; b) identifying a first region on the first layer for the second topological item, and a second region on the second layer for a third topological item that is reachable from the second topological item through a via expansion; c) determining whether an intersection of the first and second regions is larger than a threshold area; and d) adding the potential via expansion to the specified set of path expansions when the intersection is larger than the threshold area.
Claim 19
Dependent Claim
22 words
The method of claim 15 further comprising discarding the potential via expansion when the intersection is not larger than the threshold area.
Claim 20
Dependent Claim
55 words
The method of claim 15 further comprising: before specifying the set of path expansions, decomposing the layout into a plurality of faces, wherein each face has a set of edges and an interior space between the edges; wherein at least one of the second and third topological items represents an interior space of a face.
Claim 21
Dependent Claim
40 words
The method of claim 17 , wherein the second topological item represents an interior space of a first face on the first layer, and the third topological item represents an interior space of a second face on the second layer.
Claim 22
Dependent Claim
38 words
The method of claim 17 , wherein the IC layout includes a plurality of routable elements, wherein decomposing the layout comprises: specifying a plurality of nodes along boundaries of the routable elements; and defining edges between the nodes.
Claim 23
Dependent Claim
138 words
A computer program stored on a computer readable medium, wherein the computer program generates, for an integrated circuit layout that has multiple layers, a multi-layer topological path, the computer program comprising sets of instructions for: a) identifying a set of path expansions from a first topological item to a second topological item on a first layer of the layout; b) identifying a first region on the first layer for the second topological item, and a second region on the second layer for a third topological item that is reachable from the second topological item through a via expansion; c) determining whether an intersection of the first and second regions is larger than a threshold area; and d) adding the potential via expansion to the specified set of path expansions when the intersection is larger than the threshold area.
Claim 24
Dependent Claim
138 words
A computer program stored on a computer readable medium, wherein the computer program generates, for an integrated circuit layout that has multiple layers, a multi-layer topological path, the computer program comprising sets of instructions for: a) identifying a set of path expansions from a first topological item to a second topological item on a first layer of the layout; b) identifying a first region on the first layer for the second topological item, and a second region on the second layer for a third topological item that is reachable from the second topological item through a via expansion; c) determining whether an intersection of the first and second regions is larger than a threshold area; and d) adding the potential via expansion to the specified set of path expansions when the intersection is larger than the threshold area.
Claim 25
Dependent Claim
28 words
The computer program of claim 20 further comprising a set of instructions for discarding the potential via expansion when the intersection is not larger than the threshold area.
Claim 26
Dependent Claim
61 words
The computer program of claim 20 further comprising a set of instructions for decomposing the layout into a plurality of faces, before specifying the set of path expansions, wherein each face has a set of edges and an interior space between the edges; wherein at least one of the second and third topological items represents an interior space of a face.
Claim 27
Dependent Claim
41 words
The computer program of claim 22 , wherein the second topological item represents an interior space of a first face on the first layer, and the third topological item represents an interior space of a second face on the second layer.
Claim 28
Dependent Claim
49 words
The computer program of claim 22 , wherein the IC layout includes a plurality of routable elements, wherein the set of instructions for decomposing the layout comprises a set of instructions for: specifying a plurality of nodes along boundaries of the routable elements; and defining edges between the nodes.
References Cited (Backward Citations)
US4673966A
Cited
US4615011A
Cited
US4785193A
Cited
US4700016A
Cited
US4855929A
Cited
US5375069A
Cited
US6216252B1
Cited
US5634093A
Cited
US5657242A
Cited
US5532934A
Cited
US5360948A
Cited
US5618744A
Cited
US5723908A
Cited
US5659484A
Cited
US5717600A
Cited
US6155725A
Cited
US5914887A
Cited
US5636125A
Cited
US5757089A
Cited
US5633479A
Cited
US5859449A
Cited
US6088519A
Cited
US5635736A
Cited
US6407434B1
Cited
US5973376A
Cited
US5811863A
Cited
US5822214A
Cited
US5578840A
Cited
US5777360A
Cited
US5889329A
Cited
US5742086A
Cited
US5889677A
Cited
US5650653A
Cited
US5877091A
Cited
US5637920A
Cited
US5757656A
Cited
US6342682B1
Cited
US6226560B1
Cited
US5663891A
Cited
US5838583A
Cited
US20010003843A1
Cited
US6067409A
Cited
US6219832B1
Cited
US6035108A
Cited
US6209123B1
Cited
US6219823B1
Cited
US5980093A
Cited
US5898597A
Cited
US6378121B2
Cited
US6068662A
Cited
US6058254A
Cited
US6123736A
Cited
US6330707B1
Cited
US6038383A
Cited
US6260179B1
Cited
US6128767A
Cited
US6365958B1
Cited
US6557145B2
Cited
US6385758B1
Cited
US6301686B1
Cited
US6289495B1
Cited
US6253363B1
Cited
US6230306B1
Cited
US6324674B2
Cited
US6175950B1
Cited
US6247167B1
Cited
US6320391B1
Cited
US20020016901A1
Cited
US6327694B1
Cited
US6436804B2
Cited
US20020182844A1
Cited
US6262487B1
Cited
JP2000082743A
Cited
US6645842B2
Cited
US6412102B1
Cited
US6111756A
Cited
US6166441A
Cited
US6324675B1
Cited
US6412097B1
Cited
US6295634B1
Cited
US6327693B1
Cited
US6463575B1
Cited
US6405358B1
Cited
US6546540B1
Cited
US6401234B1
Cited
US6490713B2
Cited
US6519751B2
Cited
US6473891B1
Cited
US6543043B1
Cited
US6567967B2
Cited
US6512292B1
Cited
US6586281B1
Cited
US20020107711A1
Cited
US20020104061A1
Cited
US20020100009A1
Cited
US6615400B1
Cited
US20030005399A1
Cited
US20030025205A1
Cited
US20020174413A1
Cited
US6526555B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-12-07 | 2008-06-07 | 2008-12-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-12-07 | 2012-06-07 | 2012-12-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-12-07 | 2016-06-07 | 2016-12-07 | $7700.00 | Window Closed / Lapsed |