Patent US5784289A successfully refreshed from Google Patents.
US5784289A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for estimating routability and congestion in a cell placement fo integrated circuit chip
Assignee: Bell Semiconductor LLC
•
Filing: 1996-12-20
•
Granted: 1998-07-21
•
Expires: 2016-12-20
Abstract
Abstract A cell placement for a microelectronic integrated circuit includes a plurality of cells interconnected by nets of wiring. A method for estimating routing density in the placement includes superimposing a pattern of contiguous tiles over the placement, with each of the tiles having edges. Bounding boxes are constructed around the nets, and net probable densities are calculated within each bounding box for the wiring required by each net for each edge respectively. The net probable densities are summed to produce total probable densities of wiring required by all of the nets for each edge respectively. The net probable density for each edge is calculated as being equal to a wiring capacity of the edge divided by the sum of the wiring capacity of the edge and all other unobscured edges within the bounding box that are collinear with the edge respectively. A congestion map can be constructed from the total probable densities and the capacities of the edges, and/or these calculations can be used to predict the routability or unroutability of the placement. Provisions are made for edges that are obscured by large megacells or other obstacles, including providing routing detours around the obstacles.
Inventors
- 👤 Deborah Chao Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 09:20
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
106 words
A method for producing a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, comprising estimating routing density in said placement by performing the steps of: (a) superimposing a first set of spaced apart lines over said placement, wherein each of said lines is formed of a plurality of segments; (b) constructing bounding boxes around said nets; (c) calculating wiring densities required by each net for each segment respectively in accordance with a predetermined function; and (d) summing said wiring densities to produce total wiring densities required by all of said nets for each segment respectively.
Claim 2
Independent Claim
106 words
A method for producing a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, comprising estimating routing density in said placement by performing the steps of: (a) superimposing a first set of spaced apart lines over said placement, wherein each of said lines is formed of a plurality of segments; (b) constructing bounding boxes around said nets; (c) calculating wiring densities required by each net for each segment respectively in accordance with a predetermined function; and (d) summing said wiring densities to produce total wiring densities required by all of said nets for each segment respectively.
Claim 3
Dependent Claim
55 words
A method as in claim 1 wherein step (c) comprises calculating said wiring density for each segment as being equal to a wiring capacity of said each segment divided by the sum of said wiring capacity of said each segment and all other unobscured segments within said bounding box collinear with said each respective segment.
Claim 4
Dependent Claim
22 words
A method as in claim 2, wherein: said nets include pins interconnected by said wiring and said segments are of equal lengths.
Claim 5
Dependent Claim
58 words
A method as in claim 2, wherein: said first set of spaced apart lines extend parallel to a first axes; and step (c) comprises extending a first end of said bounding box in a direction orthogonal to said first axes such that said wiring can be rerouted around said extended first end when a bounding box is obscured.
Claim 6
Dependent Claim
19 words
A method as in claim 4, wherein extending the end of said bounding box minimizes a predetermined cost function.
Claim 7
Dependent Claim
36 words
A method as in claim 2, wherein step (c) comprises calculating said wiring capacity for each segment as being equal to a total wiring capacity of said each segment minus a wiring blockage of the segment.
Claim 8
Dependent Claim
43 words
A method as in claim 1, further comprising the steps of: (e) determining a threshold ratio; (f) calculating wiring capacities for each segment; and (g) calculating density ratios for each segment as a predetermined function of said total densities and said wiring capacities.
Claim 9
Dependent Claim
29 words
A method as in claim 7, wherein step (g) comprises calculating density ratios for each segment as being equal to said total densities divided by said wiring capacities respectively.
Claim 10
Dependent Claim
23 words
A method as in claim 7, further comprising the step of: (h) performing a comparison of said density ratios with said threshold ratio.
Claim 11
Dependent Claim
29 words
A method as in claim 9, further comprising the step of: (i) constructing a map of said placement indicating segments for which said density ratios exceed said threshold ratio.
Claim 12
Dependent Claim
64 words
A method as in claim 1, wherein: said placement initially comprises primary nets including pins interconnected by said wiring; the method further comprises the step, performed between steps (b) and (c), of: (e) converting said primary nets into secondary nets that each include only two pins; and step (c) comprises calculating said wiring density in accordance with a respective secondary net for each segment.
Claim 13
Dependent Claim
66 words
A method as in claim 11, wherein step (e) comprises the substeps of: (f) computing a minimum rectilinear Steiner tree for each 2-pin primary net and each 3-pin primary net; (g) computing a minimum spanning tree for each primary net having more than three pins; and (h) computing said secondary nets as comprising edges of said minimum rectilinear Steiner trees and said minimum spanning trees respectively.
Claim 14
Independent Claim
148 words
A method for predicting a routing suitability of a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, comprising the steps of: (a) superimposing a plurality of line segments over said placement; (b) constructing bounding boxes around said nets respectively; (c) calculating wiring capacities for said line segments; (d) calculating wiring densities for each net for each line segment within each bounding box in accordance with a predetermined function; (e) summing said wiring densities to produce a total wiring density of all nets for each line segment respectively; (f) calculating density ratios for said line segments based on said total wiring densities and said wiring capacities; (g) comparing said density ratios with a predetermined threshold ratio; and (h) predicting that said placement is unroutable if more than a predetermined number of said density ratios exceed said threshold ratio.
Claim 15
Independent Claim
148 words
A method for predicting a routing suitability of a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, comprising the steps of: (a) superimposing a plurality of line segments over said placement; (b) constructing bounding boxes around said nets respectively; (c) calculating wiring capacities for said line segments; (d) calculating wiring densities for each net for each line segment within each bounding box in accordance with a predetermined function; (e) summing said wiring densities to produce a total wiring density of all nets for each line segment respectively; (f) calculating density ratios for said line segments based on said total wiring densities and said wiring capacities; (g) comparing said density ratios with a predetermined threshold ratio; and (h) predicting that said placement is unroutable if more than a predetermined number of said density ratios exceed said threshold ratio.
Claim 16
Dependent Claim
13 words
A method as in claim 13, in which said predetermined number is one.
Claim 17
Dependent Claim
30 words
A method as in claim 13, wherein step (f) comprises calculating density ratios for each line segment as being equal to said total densities divided by said wiring capacities respectively.
Claim 18
Dependent Claim
62 words
A method as in claim 13, in which step (c) comprises calculating said wiring density for each line segment as being equal to a wiring capacity of each line segment divided by the sum of said wiring capacity of said each line segment and all other unobscured line segments within said bounding box that are collinear with said each line segment respectively.
Claim 19
Dependent Claim
25 words
A method as in claim 16, wherein: said nets include pins that are interconnected by said wiring and said line segments are of equal lengths.
Claim 20
Dependent Claim
52 words
A method as in claim 16, wherein: said line segments extend parallel to a first axes; and step (c) comprises extending a first end of said bounding box in a direction orthogonal to said first axes such that said wiring can bypass said extended first end when a bounding box is obscured.
Claim 21
Dependent Claim
16 words
A method as in claim 18, wherein extending said bounding box minimizes a predetermined cost function.
Claim 22
Dependent Claim
38 words
A method as in claim 16, wherein step (c) comprises calculating said wiring capacity for each line segment as being equal to a total wiring capacity of each line segment minus a wiring blockage of each line segment.
Claim 23
Dependent Claim
30 words
A method as in claim 20, further comprising the step of: (i) constructing a map of said placement indicating line segments for which said density ratios exceed said threshold ratio.
Claim 24
Dependent Claim
65 words
A method as in claim 13, wherein: said placement initially comprises primary nets having pins interconnected by said wiring; the method further comprises the step, performed between steps (b) and (c), of: (i) converting said primary nets into secondary nets that each include only two pins; and step (c) comprises calculating said wiring density as required by a respective secondary net for each line segment.
Claim 25
Dependent Claim
66 words
A method as in claim 22, wherein step (i) comprises the substeps of: (j) computing a minimum rectilinear Steiner tree for each 2-pin primary net and each 3-pin primary net; (k) computing a minimum spanning tree for each primary net having more than three pins; and (l) computing said secondary nets as comprising edges of said minimum rectilinear Steiner trees and said minimum spanning trees respectively.
Claim 26
Independent Claim
100 words
A method for predicting routing suitability for a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, comprising the steps of: (a) calculating wiring capacities; (b) calculating individual net wiring densities; (c) summing said individual net wiring densities to produce a total wiring density; (d) calculating density ratios based on said total wiring densities and said wiring capacities; (e) comparing said density ratios with a predetermined threshold ratio; and (f) predicting that said placement is unroutable if more than a predetermined number of said density ratios exceed said threshold ratio.
Claim 27
Independent Claim
100 words
A method for predicting routing suitability for a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, comprising the steps of: (a) calculating wiring capacities; (b) calculating individual net wiring densities; (c) summing said individual net wiring densities to produce a total wiring density; (d) calculating density ratios based on said total wiring densities and said wiring capacities; (e) comparing said density ratios with a predetermined threshold ratio; and (f) predicting that said placement is unroutable if more than a predetermined number of said density ratios exceed said threshold ratio.
References Cited (Backward Citations)
US4484292A
Cited
US4593363A
Cited
US4615011A
Cited
US4686629A
Cited
US4752887A
Cited
US4613941A
Cited
US4975854A
Cited
US4777606A
Cited
US4858143A
Cited
US4890238A
Cited
US4908772A
Cited
US4918614A
Cited
US4849904A
Cited
US4931946A
Cited
US5224057A
Cited
US5113352A
Cited
US5251147A
Cited
US5072402A
Cited
US5140402A
Cited
US5339252A
Cited
US5237514A
Cited
US5397749A
Cited
US5224056A
Cited
US5308798A
Cited
US5587923A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-20 | 2002-01-19 | 2002-07-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-20 | 2006-01-19 | 2006-07-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-20 | 2010-01-19 | 2010-07-21 | $7700.00 | Window Closed / Lapsed |