US5909376A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Physical design automation system and process for designing integrated circuit chips using highly parallel sieve optimization with multiple "jiggles"
Assignee: Bell Semiconductor LLC
•
Filing: 1995-11-20
•
Granted: 1999-06-01
•
Expires: 2015-11-20
Abstract
Abstract A process for implementation on a programmed digital computer includes providing a placement of clusters of cells which are assigned to regions on an integrated circuit chip, and combining the regions to form region groups. The region groups collectively constitute a "jiggle" which resembles a sieve. The clusters in each region group are re-assigned to the regions in the region group. The regions are recombined to form different region groups (a different jiggle), and the clusters in each different region group are re-assigned to the regions in the different region group. These steps are repeated using at least two, preferably four different jiggles, until an end criterion is reached. Then, the regions and clusters are hierarchically subdivided, and the process is repeated for each hierarchical level until the clusters have been reduced to individual cells. The regions of the region groups at each level are contiguous, and the region groups overlap, such that a cluster can be moved from any region to any other region on the chip by sufficient repetition of the assignment step using alternating jiggles.
Inventors
- 👤 Ranko Scepanovic
- 👤 James S. Koford
- 👤 Valeriy B. Kudryavtsev
- 👤 Alexander E. Andreev
- 👤 Stanislav V. Aleshin
- 👤 Alexander S. Podkolzin
- 👤 Edward M. Roseboom
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 18:35
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
142 words
A process for designing an integrated circuit chip, comprising the steps of: (a) providing a placement of clusters of cells, each cluster being assigned to one of plural predefined and non-overlapping regions on the chip; (b) combining the pre-defined and non-overlapping regions to form region groups; (c) performing a first cluster placement improvement operation within respective region groups that re-assigns the clusters in each region group to the other pre-defined and non-overlapping regions in said each region group when a cell placement cost function is reduced; (d) re-combining the pre-defined and non-overlapping regions to form different region groups; and (e) performing a second cluster placement improvement operation within respective different region groups that re-assigns the clusters in each different region group to the other pre-defined and non-overlapping regions in said each different region group when a cell placement cost function is reduced.
Claim 2
Dependent Claim
142 words
A process for designing an integrated circuit chip, comprising the steps of: (a) providing a placement of clusters of cells, each cluster being assigned to one of plural predefined and non-overlapping regions on the chip; (b) combining the pre-defined and non-overlapping regions to form region groups; (c) performing a first cluster placement improvement operation within respective region groups that re-assigns the clusters in each region group to the other pre-defined and non-overlapping regions in said each region group when a cell placement cost function is reduced; (d) re-combining the pre-defined and non-overlapping regions to form different region groups; and (e) performing a second cluster placement improvement operation within respective different region groups that re-assigns the clusters in each different region group to the other pre-defined and non-overlapping regions in said each different region group when a cell placement cost function is reduced.
Claim 3
Dependent Claim
26 words
A process as in claim 1, in which the regions in each region group are contiguous; and the regions in each different region group are contiguous.
Claim 4
Dependent Claim
20 words
A process as in claim 2, in which: the region groups partially overlap; and the different region groups partially overlap.
Claim 5
Dependent Claim
24 words
A process as in claim 3, further comprising the step of: (f) repeating steps (d) and (e) until an end criterion has been reached.
Claim 6
Dependent Claim
33 words
A process as in claim 4, in which the region groups are combined, and the different region groups are re-combined, such that each cluster can be re-assigned to any region in step (f).
Claim 7
Dependent Claim
24 words
A process as in claim 1, further comprising the step of: (f) repeating steps (d) and (e) until an end criterion has been reached.
Claim 8
Dependent Claim
38 words
A process as in claim 6, further comprising the step of: (g) specifying interconnections for the cells, in which: the end criterion is such that a total length of the interconnections has been reduced below a predetermined value.
Claim 9
Dependent Claim
80 words
A process as in claim 1, further comprising the steps of: (f) re-clustering the cells to form smaller clusters; (g) subdividing the regions to form subregions; (h) combining the subregions to form subregion groups; (i) re-assigning the smaller clusters in each subregion group to the subregions in said each subregion group; (j) re-combining the subregions to form different subregion groups; and (k) re-assigning the smaller clusters in each different subregion group to the subregions in said each different subregion group.
Claim 10
Dependent Claim
24 words
A process as in claim 8, further comprising the step of: (l) repeating steps (f) to (k) until an end criterion has been reached.
Claim 11
Dependent Claim
26 words
A process as in claim 9, in which the end criterion is such that a number of the subregions has been increased above a predetermined value.
Claim 12
Dependent Claim
24 words
A process as in claim 1, in which: each region group comprises four contiguous regions; and each different region group comprises four contiguous regions.
Claim 13
Dependent Claim
20 words
A process as in claim 11, in which: the region groups partially overlap; and the different region groups partially overlap.
Claim 14
Dependent Claim
24 words
A process as in claim 12, further comprising the step of: (f) repeating steps (d) and (e) until an end criterion has been reached.
Claim 15
Dependent Claim
33 words
A process as in claim 13, in which the region groups are combined, and the different region groups are re-combined, such that each cluster can be re-assigned to any region in step (f).
Claim 16
Dependent Claim
192 words
A process as in claim 1, in which: step (c) comprises the substeps, for each region group, of: (f) specifying penalties for the cells to be placed in the regions respectively; (g) constructing an assignment of the cells to the regions; (h) selecting a number of cells for movement between the regions; (i) computing an optimal permutation of movement of the selected number of cells between the regions such that a cost corresponding to the total penalties for the assignment is maximally reduced; and (j) modifying the assignment by moving the selected number of cells through the optimal permutation; and step (e) comprises the substeps, for each different region group, of: (k) specifying penalties for the cells to be placed in the regions respectively; (l) constructing an assignment of the cells to the regions; (m) selecting a number of cells for movement between the regions; (n) computing an optimal permutation of movement of the selected number of cells between the regions such that a cost corresponding to the total penalties for the assignment is maximally reduced; and (o) modifying the assignment by moving the selected number of cells through the optimal permutation.
Claim 17
Dependent Claim
41 words
A process as in claim 15, in which: step (i) comprises computing the optimal permutation as starting and ending in one of the regions; and step (n) comprises computing the optimal permutation as starting and ending in one of the regions.
Claim 18
Dependent Claim
173 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) providing a placement of clusters of cells, each cluster being assigned to one of plural pre-defined and non-overlapping regions on the chip; (b) combining the pre-defined and non-overlapping regions to form region groups; (c) performing a first cluster placement improvement operation within respective region groups that re-assigns the clusters in each region group to the other pre-defined and non-overlapping regions in said each region group when a cell placement cost function is reduced; (d) re-combining the pre-defined and non-overlapping regions to form different region groups; and (e) performing a second cluster placement improvement operation within respective different region groups that re-assigns the clusters in each different region group to the other pre-defined and non-overlapping regions in said each different region group when a cell placement cost function is reduced.
Claim 19
Dependent Claim
173 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) providing a placement of clusters of cells, each cluster being assigned to one of plural pre-defined and non-overlapping regions on the chip; (b) combining the pre-defined and non-overlapping regions to form region groups; (c) performing a first cluster placement improvement operation within respective region groups that re-assigns the clusters in each region group to the other pre-defined and non-overlapping regions in said each region group when a cell placement cost function is reduced; (d) re-combining the pre-defined and non-overlapping regions to form different region groups; and (e) performing a second cluster placement improvement operation within respective different region groups that re-assigns the clusters in each different region group to the other pre-defined and non-overlapping regions in said each different region group when a cell placement cost function is reduced.
Claim 20
Dependent Claim
28 words
A programmed digital computer as in claim 17, in which: the regions in each region group are contiguous; and the regions in each different region group are contiguous.
Claim 21
Dependent Claim
22 words
A programmed digital computer as in claim 18, in which: the region groups partially overlap; and the different region groups partially overlap.
Claim 22
Dependent Claim
38 words
A programmed digital computer as in claim 19, in which the processing means, memory means and program operating in combination further perform the step of: (f) repeating steps (d) and (e) until an end criterion has been reached.
Claim 23
Dependent Claim
35 words
A programmed digital computer as in claim 20, in which the region groups are combined, and the different region groups are re-combined, such that each cluster can be re-assigned to any region in step (f).
Claim 24
Dependent Claim
38 words
A programmed digital computer as in claim 17, in which the processing means, memory means and program operating in combination further perform the step of: (f) repeating steps (d) and (e) until an end criterion has been reached.
Claim 25
Dependent Claim
52 words
A programmed digital computer as in claim 22, in which the processing means, memory means and program operating in combination further perform the step of: (g) specifying interconnections for the cells, in which: the end criterion is such that a total length of the interconnections has been reduced below a predetermined value.
Claim 26
Dependent Claim
94 words
A programmed digital computer as in claim 17, in which the processing means, memory means and program operating in combination further perform the steps of: (f) re-clustering the cells to form smaller clusters; (g) subdividing the regions to form subregions; (h) combining the subregions to form subregion groups; (i) re-assigning the smaller clusters in each subregion group to the subregions in said each subregion group; (j) re-combining the subregions to form different subregion groups; and (k) re-assigning the smaller clusters in each different subregion group to the subregions in said each different subregion group.
Claim 27
Dependent Claim
38 words
A programmed digital computer as in claim 24, in which the processing means, memory means and program operating in combination further perform the step of: (l) repeating steps (f) to (k) until an end criterion has been reached.
Claim 28
Dependent Claim
28 words
A programmed digital computer as in claim 25, in which the end criterion is such that a number of the subregions has been increased above a predetermined value.
Claim 29
Dependent Claim
26 words
A programmed digital computer as in claim 17, in which: each region group comprises four contiguous regions; and each different region group comprises four contiguous regions.
Claim 30
Dependent Claim
22 words
A programmed digital computer as in claim 27, in which the region groups partially overlap; and the different region groups partially overlap.
Claim 31
Dependent Claim
38 words
A programmed digital computer as in claim 28, in which the processing means, memory means and program operating in combination further perform the step of: (f) repeating steps (d) and (e) until an end criterion has been reached.
Claim 32
Dependent Claim
35 words
A programmed digital computer as in claim 29, in which the region groups are combined, and the different region groups are re-combined, such that each cluster can be re-assigned to any region in step (f).
Claim 33
Dependent Claim
194 words
A programmed digital computer as in claim 17, in which: step (c) comprises the substeps, for each region group, of: (f) specifying penalties for the cells to be placed in the regions respectively; (g) constructing an assignment of the cells to the regions; (h) selecting a number of cells for movement between the regions; (i) computing an optimal permutation of movement of the selected number of cells between the regions such that a cost corresponding to the total penalties for the assignment is maximally reduced; and (j) modifying the assignment by moving the selected number of cells through the optimal permutation; and step (e) comprises the substeps, for each different region group, of: (k) specifying penalties for the cells to be placed in the regions respectively; (l) constructing an assignment of the cells to the regions; (m) selecting a number of cells for movement between the regions; (n) computing an optimal permutation of movement of the selected number of cells between the regions such that a cost corresponding to the total penalties for the assignment is maximally reduced; and (o) modifying the assignment by moving the selected number of cells through the optimal permutation.
Claim 34
Dependent Claim
43 words
A programmed digital computer as in claim 31, in which: step (i) comprises computing the optimal permutation as starting and ending in one of the regions; and step (n) comprises computing the optimal permutation as starting and ending in one of the regions.
References Cited (Backward Citations)
US4701778A
Cited
US5051917A
Cited
US5490419A
Cited
US5566078A
Cited
US5513119A
Cited
US5495419A
Cited
US5699265A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-31 | 2002-11-30 | 2003-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-31 | 2006-11-30 | 2007-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-31 | 2010-11-30 | 2011-06-01 | $7700.00 | Window Closed / Lapsed |