Patent US5835378A successfully refreshed from Google Patents.
US5835378A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer implemented method for leveling interconnect wiring density in a cell placement for an integrated circuit chip
Assignee: Bell Semiconductor LLC
•
Filing: 1995-11-20
•
Granted: 1998-11-10
•
Expires: 2015-11-20
Abstract
Abstract A digital computer includes a processor, a memory and a program which operate in combination for inputting a placement of cells for an integrated circuit chip, and a netlist of wiring nets interconnecting the cells. The placement is divided into a plurality of contiguous regions, and cell densities in the regions are computed in accordance with locations of the cells in the placement. Wiring densities in the regions are computed in accordance with the locations of the cells and the netlist. The shapes of the regions are altered to produce altered regions such that cell densities and wiring densities in the altered regions are more level or uniform. The placement is then altered such that the cells occupy locations in the altered regions which are relative to their locations in the original regions. The porosities of the cells can also be computed and used in the computation of the region shapes. The wiring densities are computed by constructing bounding boxes around the wiring nets, and computing horizontal and vertical total heights and widths of bounding boxes that overlap the regions. The altered shapes are generated by computing optimal sizes for the regions for containing the cells and required interconnect wiring, computing new lengths for edges of the regions, and iteratively recomputing new positions for corners of the regions using a mechanical mass-spring model until the system reaches equilibrium.
Inventors
- 👤 Ranko Scepanovic
- 👤 James S. Koford
- 👤 Valeriy B. Kudryavtsev
- 👤 Alexander E. Andreev
- 👤 Stanislav V. Aleshin
- 👤 Alexander S. Podkolzin
- 👤 Douglas B. Boyle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:35
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
143 words
A computer implemented method for leveling interconnect wiring density in a cell placement for an integrated circuit chip, comprising the steps of: (a) providing a placement of cells on the chip, and a netlist of wiring nets interconnecting the cells; (b) dividing the placement into a plurality of contiguous regions; (c) computing cell densities in the regions in accordance with locations of the cells in the placement; (d) computing wiring densities in the regions in accordance with the locations of the cells and the netlist; (e) altering shapes of the regions to produce altered regions such that cell densities and wiring densities in the altered regions are more level than in the regions of step (c); and (f) altering the placement such that the cells occupy locations in the altered regions which are relative to their locations in the regions of step (c).
Claim 2
Dependent Claim
143 words
A computer implemented method for leveling interconnect wiring density in a cell placement for an integrated circuit chip, comprising the steps of: (a) providing a placement of cells on the chip, and a netlist of wiring nets interconnecting the cells; (b) dividing the placement into a plurality of contiguous regions; (c) computing cell densities in the regions in accordance with locations of the cells in the placement; (d) computing wiring densities in the regions in accordance with the locations of the cells and the netlist; (e) altering shapes of the regions to produce altered regions such that cell densities and wiring densities in the altered regions are more level than in the regions of step (c); and (f) altering the placement such that the cells occupy locations in the altered regions which are relative to their locations in the regions of step (c).
Claim 3
Dependent Claim
79 words
A method as in claim 1, in which: step (a) further comprises specifying porosities of the cells; the method further comprises the step, performed between steps (c) and (f), of: (g) computing porosities of the regions in accordance with the porosities of the cells; and step (e) further comprises computing shapes for the altered regions in accordance with the cell densities of step (c), the wiring densities of step (d) and the porosities of the regions of step (g).
Claim 4
Dependent Claim
25 words
A method as in claim 2, in which step (g) comprises computing the porosities of the regions as total porosities of cells in the regions.
Claim 5
Dependent Claim
22 words
A method as in claim 1, in which step (c) comprises computing the cell densities as areas of cells in the regions.
Claim 6
Dependent Claim
44 words
A method as in claim 1, in which step (d) comprises the substeps of: (g) constructing bounding boxes around the wiring nets respectively; and (h) computing the wiring densities as horizontal and vertical total heights and widths of bounding boxes that overlap the regions.
Claim 7
Dependent Claim
69 words
A method as in claim 1, in which step (e) comprises the substeps of: (g) computing optimal region widths and heights in accordance with the cell densities and the wiring densities; (h) computing horizontal and vertical region altered edge lengths in accordance with the optimal region widths and heights; and (i) computing said shapes for the altered regions in accordance with the horizontal and vertical region altered edge lengths.
Claim 8
Dependent Claim
51 words
A method as in claim 6, in which step (h) comprises the substeps of: (j) computing the vertical region altered edge lengths as averages of optimal region heights of two contiguous regions; and (k) computing the horizontal region altered edge lengths as averages of optimal region widths of two contiguous regions.
Claim 9
Dependent Claim
18 words
A method as in claim 6, in which step (i) comprises computing said shapes using force directed placement.
Claim 10
Dependent Claim
24 words
A method as in claim 8, further comprising the step of: (l) iteratively repeating steps (g) to (i) until an end criterion is reached.
Claim 11
Dependent Claim
30 words
A method as in claim 9, in which the end criterion is such that a change in a predetermined cost function between two iterations is less than a predetermined value.
Claim 12
Dependent Claim
15 words
A method as in claim 1, in which the regions in step (b) are squares.
Claim 13
Dependent Claim
16 words
A method as in claim 1, in which the altered regions in step (e) are quadrilaterals.
Claim 14
Dependent Claim
39 words
A method as in claim 1, in which: step (a) comprises providing the placement such that the cells are arranged in columns; and step (b) comprises dividing the placement such that each region contains a same number of columns.
Claim 15
Dependent Claim
41 words
A method as in claim 1, in which step (e) comprises computing shapes for the altered regions such that the altered regions have a substantially minimum size for containing the cells and wiring having the wiring densities computed in step (d).
Claim 16
Dependent Claim
24 words
A method as in claim 1, further comprising the step of: (g) iteratively performing steps (c) to (f) until an end criterion is reached.
Claim 17
Dependent Claim
166 words
A programmed digital computer for designing an integrated circuit chip, comprising: memory means for storing a program including instructions and data; and processing means for executing the program; the processing means, memory means and program operating in combination for performing the steps of: (a) inputting a placement of cells for an integrated circuit chip, and a netlist of wiring nets interconnecting the cells; (b) dividing the placement into a plurality of contiguous regions; (c) computing cell densities in the regions in accordance with locations of the cells in the placement; (d) computing wiring densities in the regions in accordance with the locations of the cells and the netlist; (e) altering shapes of the regions to produce altered regions such that cell densities and wiring densities in the altered regions are more level than in the regions of step (c); and (f) altering the placement such that the cells occupy locations in the altered regions which are relative to their locations in the regions of step (c).
Claim 18
Dependent Claim
166 words
A programmed digital computer for designing an integrated circuit chip, comprising: memory means for storing a program including instructions and data; and processing means for executing the program; the processing means, memory means and program operating in combination for performing the steps of: (a) inputting a placement of cells for an integrated circuit chip, and a netlist of wiring nets interconnecting the cells; (b) dividing the placement into a plurality of contiguous regions; (c) computing cell densities in the regions in accordance with locations of the cells in the placement; (d) computing wiring densities in the regions in accordance with the locations of the cells and the netlist; (e) altering shapes of the regions to produce altered regions such that cell densities and wiring densities in the altered regions are more level than in the regions of step (c); and (f) altering the placement such that the cells occupy locations in the altered regions which are relative to their locations in the regions of step (c).
Claim 19
Dependent Claim
89 words
A programmed digital computer as in claim 16, in which: step (a) further comprises specifying porosities of the cells; the processing means, memory means and program further operate in combination for performing the step, between steps (c) and (f), of: (g) computing porosities of the regions in accordance with the porosities of the cells; and step (e) further comprises computing shapes for the altered regions in accordance with the cell densities of step (c), the wiring densities of step (d) and the porosities of the regions of step (g).
Claim 20
Dependent Claim
27 words
A programmed digital computer as in claim 17, in which step (g) comprises computing the porosities of the regions as total porosities of cells in the regions.
Claim 21
Dependent Claim
24 words
A programmed digital computer as in claim 16, in which step (c) comprises computing the cell densities as areas of cells in the regions.
Claim 22
Dependent Claim
46 words
A programmed digital computer as in claim 16, in which step (d) comprises the substeps of: (g) constructing bounding boxes around the wiring nets respectively; and (h) computing the wiring densities as horizontal and vertical total heights and widths of bounding boxes that overlap the regions.
Claim 23
Dependent Claim
71 words
A programmed digital computer as in claim 16, in which step (e) comprises the substeps of: (g) computing optimal region widths and heights in accordance with the cell densities and the wiring densities; (h) computing horizontal and vertical region altered edge lengths in accordance with the optimal region widths and heights; and (i) computing said shapes for the altered regions in accordance with the horizontal and vertical region altered edge lengths.
Claim 24
Dependent Claim
53 words
A programmed digital computer as in claim 21, in which step (h) comprises the substeps of: (j) computing the vertical region altered edge lengths as averages of optimal region heights of two contiguous regions; and (k) computing the horizontal region altered edge lengths as averages of optimal region widths of two contiguous regions.
Claim 25
Dependent Claim
20 words
A programmed digital computer as in claim 21, in which step (i) comprises computing said shapes using force directed placement.
Claim 26
Dependent Claim
39 words
A programmed digital computer as in claim 22, in which the processing means, memory means and program further operate in combination for performing the step of: (l) iteratively repeating steps (g) to (i) until an end criterion is reached.
Claim 27
Dependent Claim
32 words
A programmed digital computer as in claim 24, in which the end criterion is such that a change in a predetermined cost function between two iterations is less than a predetermined value.
Claim 28
Dependent Claim
17 words
A programmed digital computer as in claim 16, in which the regions in step (b) are squares.
Claim 29
Dependent Claim
18 words
A programmed digital computer as in claim 16, in which the altered regions in step (e) are quadrilaterals.
Claim 30
Dependent Claim
41 words
A programmed digital computer as in claim 16, in which: step (a) comprises providing the placement such that the cells are arranged in columns; and step (b) comprises dividing the placement such that each region contains a same number of columns.
Claim 31
Dependent Claim
43 words
A programmed digital computer as in claim 16, in which step (e) comprises computing shapes for the altered regions such that the altered regions have a substantially minimum size for containing the cells and wiring having the wiring densities computed in step (d).
Claim 32
Dependent Claim
39 words
A programmed digital computer as in claim 16, in which the processing means, memory means and program further operate in combination for performing the step of: (g) iteratively performing steps (c) to (f) until an end criterion is reached.
References Cited (Backward Citations)
US4613941A
Cited
US4811237A
Cited
US5404310A
Cited
US5402358A
Cited
US5420800A
Cited
US5303161A
Cited
US5587923A
Cited
US5619419A
Cited
US5539652A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-09 | 2002-05-11 | 2002-11-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-09 | 2006-05-11 | 2006-11-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-09 | 2010-05-11 | 2010-11-10 | $7700.00 | Window Closed / Lapsed |