Method for estimating routability and congestion in a cell placement fo integrated circuit chip
First Claim
1. 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.
6 Assignments
0 Petitions
Accused Products
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.
204 Citations
24 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. 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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. 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.
-
Specification