US5587923A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for estimating routability and congestion in a cell placement for integrated circuit chip
Assignee: Bell Semiconductor LLC
•
Filing: 1994-09-07
•
Granted: 1996-12-24
•
Expires: 2014-09-07
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 C. Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 03:19
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
113 words
A computer implemented method for producing a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, the method comprising estimating routing density in said placement by performing the steps, of: (a) superimposing a pattern of contiguous tiles over said placement, each of said tiles having edges; (b) constructing bounding boxes around said nets respectively; (c) calculating, within each bounding box in accordance with a predetermined function, net probable densities of wiring required by said net for each edge respectively; and (d) summing said net probable densities to produce total probable densities of wiring required by all of said nets for each edge respectively.
Claim 2
Dependent Claim
113 words
A computer implemented method for producing a cell placement for a microelectronic integrated circuit, said placement including a plurality of cells interconnected by nets of wiring, the method comprising estimating routing density in said placement by performing the steps, of: (a) superimposing a pattern of contiguous tiles over said placement, each of said tiles having edges; (b) constructing bounding boxes around said nets respectively; (c) calculating, within each bounding box in accordance with a predetermined function, net probable densities of wiring required by said net for each edge respectively; and (d) summing said net probable densities to produce total probable densities of wiring required by all of said nets for each edge respectively.
Claim 3
Dependent Claim
166 words
A computer implemented method for producing a cell placement for a microelectronic integrated circuit, said element including a plurality of cells interconnected by nets of wiring, the method comprising estimating routing density in said placement by performing the steps, of: (a) superimposing a pattern of contiguous tiles over said placement, each of said tiles having edges; (b) constructing bounding boxes around said nets respectively; (c) calculating, within each bounding box in accordance with a predetermined function, net probable densities of wiring required by said net for each edge respectively; and (d) summing said net probable densities to produce total probable densities of wiring required by all of said nets for each edge respectively; in which step (c) comprises calculating said net probable density for each edge as being equal to a wiring capacity of said each edge divided by the sum of said wiring capacity of said each edge and all other unobscured edges within said bounding box that are collinear with said each edge respectively.
Claim 4
Dependent Claim
166 words
A computer implemented method for producing a cell placement for a microelectronic integrated circuit, said element including a plurality of cells interconnected by nets of wiring, the method comprising estimating routing density in said placement by performing the steps, of: (a) superimposing a pattern of contiguous tiles over said placement, each of said tiles having edges; (b) constructing bounding boxes around said nets respectively; (c) calculating, within each bounding box in accordance with a predetermined function, net probable densities of wiring required by said net for each edge respectively; and (d) summing said net probable densities to produce total probable densities of wiring required by all of said nets for each edge respectively; in which step (c) comprises calculating said net probable density for each edge as being equal to a wiring capacity of said each edge divided by the sum of said wiring capacity of said each edge and all other unobscured edges within said bounding box that are collinear with said each edge respectively.
Claim 5
Dependent Claim
71 words
A method as in claim 2, in which: said nets include pins that are interconnected by said wiring; and step (c) comprises, when a tile that lies on a boundary of a bounding box is obscured and all tiles between said tile and an orthogonal boundary of said bounding box do not enclose pins of said net respectively, designating all edges of said tile and said all tiles as being obscured.
Claim 6
Dependent Claim
64 words
A method as in claim 2, in which: said edges extend parallel to one or the other of two orthogonal axes; and step (c) comprises, when a bounding box is completely obscured parallel to one of said orthogonal axes, extending an end of said bounding box parallel to said one of said orthogonal axes such that said wiring can detour around said extended end.
Claim 7
Dependent Claim
23 words
A method as in claim 4, in which step (c) comprises extending said bounding box such that a predetermined cost function is minimized.
Claim 8
Dependent Claim
38 words
A method as in claim 2, in which step (c) comprises calculating said wiring capacity for each edge as being equal to a total wiring capacity of said each edge minus a wiring blockage of said each edge.
Claim 9
Dependent Claim
55 words
A method as in claim 1, further comprising the step of: (e) predetermining a threshold ratio; (f) calculating wiring capacities for said edges respectively; (g) calculating density ratios for said edges as being equal to said total probable densities divided by said wiring capacities respectively; and (h) comparing said density ratios with said threshold ratio.
Claim 10
Dependent Claim
29 words
A method as in claim 7, further comprising the step of: (i) constructing a map of said placement indicating edges for which said density ratios exceed said threshold ratio.
Claim 11
Dependent Claim
79 words
A method as in claim 1, in which: said placement initially comprises primary nets including pins that are interconnected by said wiring; said primary nets can include more than two pins; 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 net probable density of wiring as required by a respective secondary net for each edge.
Claim 12
Dependent Claim
67 words
A method as in claim 9, in which 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 13
Independent Claim
168 words
A method for predicting if a cell placement for a microelectronic integrated circuit is unroutable, said placement including a plurality of cells interconnected by nets of wiring, comprising the steps of: (a) superimposing a pattern of contiguous tiles over said placement, each of said tiles having edges; (b) constructing bounding boxes around said nets respectively; (c) calculating wiring capacities for said edges respectively; (d) calculating, within each bounding box in accordance with a predetermined function, net probable densities of wiring required by said net for each edge respectively; (e) summing said net probable densities to produce total probable densities of wiring required by all of said nets for each edge respectively; (f) predetermining a threshold ratio; (g) calculating density ratios for said edges as being equal to said total probable densities divided by said wiring capacities respectively; (h) comparing said density ratios with said threshold ratio; and (i) predicting that said placement is unroutable if more than a predetermined number of said density ratios exceed said threshold ratio.
Claim 14
Independent Claim
168 words
A method for predicting if a cell placement for a microelectronic integrated circuit is unroutable, said placement including a plurality of cells interconnected by nets of wiring, comprising the steps of: (a) superimposing a pattern of contiguous tiles over said placement, each of said tiles having edges; (b) constructing bounding boxes around said nets respectively; (c) calculating wiring capacities for said edges respectively; (d) calculating, within each bounding box in accordance with a predetermined function, net probable densities of wiring required by said net for each edge respectively; (e) summing said net probable densities to produce total probable densities of wiring required by all of said nets for each edge respectively; (f) predetermining a threshold ratio; (g) calculating density ratios for said edges as being equal to said total probable densities divided by said wiring capacities respectively; (h) comparing said density ratios with said threshold ratio; and (i) predicting that said placement is unroutable if more than a predetermined number of said density ratios exceed said threshold ratio.
Claim 15
Dependent Claim
13 words
A method as in claim 11, in which said predetermined number is one.
Claim 16
Dependent Claim
59 words
A method as in claim 11, in which step (c) comprises calculating said net probable density for each edge as being equal to a wiring capacity of said each edge divided by the sum of said wiring capacity of said each edge and all other unobscured edges within said bounding box that are collinear with said each edge respectively.
Claim 17
Dependent Claim
71 words
A method as in claim 13, in which: said nets include pins that are interconnected by said wiring; and step (c) comprises, when a tile that lies on a boundary of a bounding box is obscured and all tiles between said tile and an orthogonal boundary of said bounding box do not enclose pins of said net respectively, designating all edges of said tile and said all tiles as being obscured.
Claim 18
Dependent Claim
64 words
A method as in claim 13, in which: said edges extend parallel to one or the other of two orthogonal axes; and step (c) comprises, when a bounding box is completely obscured parallel to one of said orthogonal axes, extending an end of said bounding box parallel to said one of said orthogonal axes such that said wiring can detour around said extended end.
Claim 19
Dependent Claim
23 words
A method as in claim 15, in which step (c) comprises extending said bounding box such that a predetermined cost function is minimized.
Claim 20
Dependent Claim
38 words
A method as in claim 13, in which step (c) comprises calculating said wiring capacity for each edge as being equal to a total wiring capacity of said each edge minus a wiring blockage of said each edge.
Claim 21
Dependent Claim
29 words
A method as in claim 17, further comprising the step of: (j) constructing a map of said placement indicating edges for which said density ratios exceed said threshold ratio.
Claim 22
Dependent Claim
79 words
A method as in claim 11, in which: said placement initially comprises primary nets including pins that are interconnected by said wiring; said primary nets can include more than two pins; the method further comprises the step, performed between steps (b) and (c), of: (j) converting said primary nets into secondary nets that each include only two pins; and step (c) comprises calculating said net probable density of wiring as required by a respective secondary net for each edge.
Claim 23
Dependent Claim
67 words
A method as in claim 19, in which step (j) comprises the substeps of: (k) computing a minimum rectilinear Steiner tree for each 2-pin primary net and each 3-pin primary net; (l) computing a minimum spanning tree for each primary net having more than three pins; and (m) computing said secondary nets as comprising edges of said minimum rectilinear Steiner trees and said minimum spanning trees respectively.
References Cited (Backward Citations)
US4484292A
Cited
US4593363A
Cited
US4615011A
Cited
US4686629A
Cited
US4752887A
Cited
US4613941A
Cited
US4823276A
Cited
US4975854A
Cited
US4777606A
Cited
US4858143A
Cited
US4890238A
Cited
US4908772A
Cited
US4918614A
Cited
US4849904A
Cited
US4852015A
Cited
US4931946A
Cited
US5452231A
Cited
US5475611A
Cited
US5224057A
Cited
US5113352A
Cited
US5251147A
Cited
US5448493A
Cited
US5140402A
Cited
US5187671A
Cited
US5237514A
Cited
US5245550A
Cited
US5339253A
Cited
US5397749A
Cited
US5394337A
Cited
US5224056A
Cited
US5308798A
Cited
US5457410A
Cited
US5500804A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-24 | 2000-06-24 | 2000-12-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-24 | 2004-06-24 | 2004-12-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-24 | 2008-06-24 | 2008-12-24 | $7700.00 | Window Closed / Lapsed |