Patent US6324675B1 successfully refreshed from Google Patents.
US6324675B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient iterative, gridless, cost-based fine router for computer controlled integrated circuit design
Assignee: Synopsys Inc
•
Filing: 1998-12-18
•
Granted: 2001-11-27
•
Expires: 2018-12-18
Abstract
Abstract An efficient iterative, gridless, cost-based router for a computer controlled integrated circuit design. The fine routing process is used during the wire routing phase of an integrated circuit design and fabrication process. During the wire routing process, wires are routed between pins of nets. The routing process of the present invention is gridless and utilizes lanes that are defined based on the boundaries of objects. The cost-based router computes a cost for each wire path, and the cost is based on: (1) the manhattan wire distance: (2) the layers in which the wire runs; and (3) any overlap the wire has with soft obstacles (e.g., other wires, etc.); and (4) an estimated cost to the target. Cost computation is reduced by considering only obstacles within the layer in which a lane is run. The number of paths determined for a wire route is reduced by pruning possible paths based on the placement of obstacles within the integrated circuit. Further pruning is performed by picking the lowest cost child lane in cases when several lanes select the same lane. Paths are also pruned by stopping along any path whose work-in-progress cost estimation exceeds the final cost of a path already discovered. In multi-pin nets, the routing process selects that path (of equal cost paths) between a source pin and a target pin that also runs closer to another unconnected pin of the multi-pin net. When a source-target wire route is performed for a multi-pin net, the unconnected pin is treated as the target and the source is considered as the source-target wire route.
Inventors
- 👤 Robi Dutta
- 👤 Ravi Rao
- 👤 Ashok Vittal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:42
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
260 words
A computer controlled routing method comprising the steps of: a) producing a wire solution for an integrated circuit layout having a plurality of objects by traversing a plurality of source pin and target pin pairs and performing a gridless routing procedure to model a wire connection between each traversed source pin and target pin pair, said step a) comprising the steps of: a1) determining a first plurality of paths between a given source pin and a given target pin wherein each path comprises lanes, wherein said lanes reside in at least one of a plurality of layers of said integrated circuit layout; a2) pruning said first plurality of paths to produce a path subset, wherein said pruning is based on the location of a path of said plurality relative to an object of said plurality; a3) determining the lowest cost path of said path subset by applying a cost function to each path of said path subset wherein said cost function considers only objects within the same layer as each lane; and a4) modeling a wire connection between said source pin and said target pin based on said lowest cost path determined at step a3) wherein said wire connection is allowed to overlap with other wire connections and with selected objects; a5) repeating said step a1) through said step a4) for additional source pins and target pins; b) repeating step a) provided said wire solution contains less number of overlaps as a prior iteration of step a; and c) reporting the last computed wire solution as a final wire solution.
Claim 2
Dependent Claim
260 words
A computer controlled routing method comprising the steps of: a) producing a wire solution for an integrated circuit layout having a plurality of objects by traversing a plurality of source pin and target pin pairs and performing a gridless routing procedure to model a wire connection between each traversed source pin and target pin pair, said step a) comprising the steps of: a1) determining a first plurality of paths between a given source pin and a given target pin wherein each path comprises lanes, wherein said lanes reside in at least one of a plurality of layers of said integrated circuit layout; a2) pruning said first plurality of paths to produce a path subset, wherein said pruning is based on the location of a path of said plurality relative to an object of said plurality; a3) determining the lowest cost path of said path subset by applying a cost function to each path of said path subset wherein said cost function considers only objects within the same layer as each lane; and a4) modeling a wire connection between said source pin and said target pin based on said lowest cost path determined at step a3) wherein said wire connection is allowed to overlap with other wire connections and with selected objects; a5) repeating said step a1) through said step a4) for additional source pins and target pins; b) repeating step a) provided said wire solution contains less number of overlaps as a prior iteration of step a; and c) reporting the last computed wire solution as a final wire solution.
Claim 3
Dependent Claim
68 words
A method as described in claim 1 wherein said step a2) comprises the steps of: determining an object of said plurality that defines a self lane having a parent lane; determining an intersection between said self lane and said parent lane; determining at least one child lane; and retaining only those child lanes that lie on a side of said object as defined with respect to said intersection.
Claim 4
Dependent Claim
34 words
A method as described in claim 2 wherein said side of said object as defined with respect to said intersection is the opposite side of said object as defined with respect to said intersection.
Claim 5
Dependent Claim
42 words
A method as described in claim 3 wherein said step a2) further comprises the step of retaining as a valid child lane that lane that is defined by said object and lies on the same side of said object as said intersection.
Claim 6
Dependent Claim
99 words
A method as described in claim 1 wherein said given source pin and said given target pin are part of a multi-pin net and wherein said step a3) comprises the steps of: determining a first path from said given source pin to said given target pin; determining a second path from said given source pin to said given target pin, said first and second paths having equal costs; and selecting as said lowest cost path, as between said first and second path, the path that comes closer to a next pin that is also part of said multi-pin net.
Claim 7
Dependent Claim
95 words
A method as described in claim 1 wherein said given source pin and said given target pin are part of a multi-pin net and further comprising the steps of: d) using steps a1) through a4) to model a wire connection between said given target pin and said given source pin; e) defining, as a target pin, an unconnected pin that is also part of said multi-pin net; f) defining said wire connection of said step d) as a source pin to said target pin of said step e); and g) repeating steps a1) through a4).
Claim 8
Dependent Claim
146 words
A method as described in claim 1 wherein step a1) comprises determining self lanes and parent lanes and wherein a self lane is selected by several parent lanes, and wherein step a1) further comprises the steps of: for each parent lane selecting said self lane, computing a cost from said given source pin to an intersection of said parent lane to said self lane; for each parent lane selecting said self lane, estimating a cost from its intersection to said given target pin; for each parent lane selecting said self lane, determining its total cost by adding together its respective computed cost and its respective estimated cost; selecting the lowest total cost and based thereon, inserting a single backpointer data structure on said self lane, said backpointer data structure containing said lowest total cost and a pointer to the parent lane having said lowest total cost.
Claim 9
Dependent Claim
65 words
A method as described in claim 1 wherein said paths are represented by backpointer data structures inserted on lanes, said backpointer data structures comprising: a cost of reaching a lane from said given source pin; and a pointer to the ancestor of said lane and further comprising the step of determining a unique path by tracing through said backpointers starting from aid respective target pin.
Claim 10
Dependent Claim
47 words
A method as described in claim 8 wherein a first lane comprises several soft objects thereon that define a set of lane segments of said first lane and further comprising the step of defining a respective backpointer data structure for each lane segment of said first lane.
Claim 11
Dependent Claim
237 words
In a computer system comprising a processor coupled to a bus, a computer readable medium coupled to said bus and having stored thereon instructions that when executed implement a computer controlled routing method, said method comprising the steps of: a1) determining a first plurality of paths between a given source pin and a given target pin wherein each path comprises lanes, wherein said lanes reside in at least one of a plurality of layers of said integrated circuit layout; a2) pruning said first plurality of paths to produce a path subset, wherein said pruning is based on the location of a path of said plurality relative to an object of said plurality; a3) determining the lowest cost path of said path subset by applying a cost function to each path of said path subset wherein said cost function considers only objects within the same layer as each lane; and a4) modeling a wire connection between said source pin and said target pin based on said lowest cost path determined at step a3) wherein said wire connection is allowed to overlap with other wire connections and with selected objects; a5) repeating said step a1) through said step a4) for additional source pins and target pins; b) repeating step a) provided said wire solution contains less number of overlaps as a prior iteration of step a; and c) reporting the last computed wire solution as a final wire solution.
Claim 12
Dependent Claim
237 words
In a computer system comprising a processor coupled to a bus, a computer readable medium coupled to said bus and having stored thereon instructions that when executed implement a computer controlled routing method, said method comprising the steps of: a1) determining a first plurality of paths between a given source pin and a given target pin wherein each path comprises lanes, wherein said lanes reside in at least one of a plurality of layers of said integrated circuit layout; a2) pruning said first plurality of paths to produce a path subset, wherein said pruning is based on the location of a path of said plurality relative to an object of said plurality; a3) determining the lowest cost path of said path subset by applying a cost function to each path of said path subset wherein said cost function considers only objects within the same layer as each lane; and a4) modeling a wire connection between said source pin and said target pin based on said lowest cost path determined at step a3) wherein said wire connection is allowed to overlap with other wire connections and with selected objects; a5) repeating said step a1) through said step a4) for additional source pins and target pins; b) repeating step a) provided said wire solution contains less number of overlaps as a prior iteration of step a; and c) reporting the last computed wire solution as a final wire solution.
Claim 13
Dependent Claim
72 words
The computer readable medium of claim 10 , wherein said step a2) of said method comprises the steps of: determining an object of said plurality that defines a self lane having a parent lane; determining an intersection between said self lane and said parent lane; determining at least one child lane; and retaining only those child lanes that lie on a side of said object as defined with respect to said intersection.
Claim 14
Dependent Claim
36 words
The computer readable medium as described in claim 11 wherein said side of said object as defined with respect to said intersection is the opposite side of said object as defined with respect to said intersection.
Claim 15
Dependent Claim
47 words
The computer readable medium as described in claim 12 wherein said step a2) of said method further comprises the step of retaining as a valid child lane that lane that is defined by said object and lies on the same side of said object as said intersection.
Claim 16
Dependent Claim
104 words
The computer readable medium as described in claim 10 wherein said given source pin and said given target pin are part of a multi-pin net and wherein said step a3) of said method comprises the steps of: determining a first path from said given source pin to said given target pin; determining a second path from said given source pin to said given target pin, said first and second paths having equal costs; and selecting as said lowest cost path, as between said first and second path, the path that comes closer to an unconnected pin that is also part of said multi-pin net.
Claim 17
Dependent Claim
100 words
The computer readable medium as described in claim 10 wherein said given source pin and said given target pin are part of a multi-pin net and wherein said method further comprises the steps of: d) using steps a1) through a4) to model a wire connection between said given target pin and said given source pin; e) defining, as a target pin, an unconnected pin that is also part of said multi-pin net; f) defining said wire connection of said step d) as a source pin to said target pin of said step e); and g) repeating steps a1) through a4).
Claim 18
Dependent Claim
151 words
The computer readable medium as described in claim 10 wherein step a1) of said method comprises determining self lanes and parent lanes and wherein a self lane is selected by several parent lanes and wherein said method further comprises the steps of: for each parent lane selecting said self lane, computing a cost from said given source pin to an intersection of said parent lane to said self lane; for each parent lane selecting said self lane, estimating a cost from its intersection to said given target pin; for each parent lane selecting said self lane, determining its total cost by adding together its respective computed cost and its respective estimated cost; selecting the lowest total cost and based thereon, inserting a single backpointer data structure on said self lane, said backpointer data structure containing said lowest total cost and a pointer to the parent lane having said lowest total cost.
Claim 19
Dependent Claim
70 words
The computer readable medium as described in claim 10 wherein said paths are represented by backpointer data structures inserted on lanes, said backpointer data structures comprising: a cost of reaching a lane from said given source pin; and a pointer to the ancestor of said lane and wherein said method further comprises the step of determining a unique path by tracing through said backpointers starting from said respective target pin.
Claim 20
Dependent Claim
51 words
The memory unit as described in claim 17 wherein a first lane comprises several soft objects thereon that define a set of lane segments of said first lane and wherein said method further comprises the step of defining a respective backpointer data structure for each lane segment of said first lane.
Claim 21
Dependent Claim
288 words
A computer controlled routing method comprising the steps of: a) producing a wire solution for an integrated circuit layout having a plurality of objects by traversing a plurality of source pin and target pin pairs and performing a gridless routing procedure to model a wire connection between each traversed source pin and target pin pair, said step a) comprising the steps of: a1) determining a first plurality of paths between a given source pin and a given target pin wherein each path comprises lanes, wherein said lanes reside in at least one of a plurality of layers of said integrated circuit layout; a2) pruning said first plurality of paths to produce a path subset, wherein said pruning is based on the location of a path of said plurality relative to an object of said plurality; a3) determining the lowest cost path of said path subset by applying a cost function to each path of said path subset wherein said cost function considers only objects within the same layer as each lane, said cost function having the cost components comprising: a manhattan wire length cost; a per layer length cost; an overlap cost; and an estimated cost to the target; and a4) modeling a wire connection between said source pin and said target pin based on said lowest cost path determined at step a3) wherein said wire connection is allowed to overlap with other wire connections and with selected objects; a5) repeating said step a1) through said step a4) for additional source pins and target pins; b) repeating step a) provided said wire solution contains less number of overlaps as a prior iteration of step a; and c) reporting the last computed wire solution as a final wire solution.
Claim 22
Dependent Claim
288 words
A computer controlled routing method comprising the steps of: a) producing a wire solution for an integrated circuit layout having a plurality of objects by traversing a plurality of source pin and target pin pairs and performing a gridless routing procedure to model a wire connection between each traversed source pin and target pin pair, said step a) comprising the steps of: a1) determining a first plurality of paths between a given source pin and a given target pin wherein each path comprises lanes, wherein said lanes reside in at least one of a plurality of layers of said integrated circuit layout; a2) pruning said first plurality of paths to produce a path subset, wherein said pruning is based on the location of a path of said plurality relative to an object of said plurality; a3) determining the lowest cost path of said path subset by applying a cost function to each path of said path subset wherein said cost function considers only objects within the same layer as each lane, said cost function having the cost components comprising: a manhattan wire length cost; a per layer length cost; an overlap cost; and an estimated cost to the target; and a4) modeling a wire connection between said source pin and said target pin based on said lowest cost path determined at step a3) wherein said wire connection is allowed to overlap with other wire connections and with selected objects; a5) repeating said step a1) through said step a4) for additional source pins and target pins; b) repeating step a) provided said wire solution contains less number of overlaps as a prior iteration of step a; and c) reporting the last computed wire solution as a final wire solution.
Claim 23
Dependent Claim
68 words
A method as described in claim 19 wherein said step a2) comprises the steps of: determining an object of said plurality that defines a self lane having a parent lane; determining an intersection between said self lane and said parent lane; determining at least one child lane; and retaining only those child lanes that lie on a side of said object as defined with respect to said intersection.
Claim 24
Dependent Claim
65 words
A method as described in claim 19 wherein said paths are represented by backpointer data structures inserted on lanes, said backpointer data structures comprising: a cost of reaching a lane from said given source pin; and a pointer to the ancestor of said lane and further comprising the step of determining a unique path by tracing through said backpointers starting from said respective target pin.
References Cited (Backward Citations)
US5375069A
Cited
US5160855A
Cited
US5550748A
Cited
US5757089A
Cited
US5671432A
Cited
US5729466A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-11-26 | 2005-05-28 | 2005-11-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-11-26 | 2009-05-28 | 2009-11-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-11-26 | 2013-05-28 | 2013-11-27 | $7700.00 | Window Closed / Lapsed |