§
Luxuse
Patent Intelligence
Sign In
← Back to Patent Explorer
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
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

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:42
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

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag