US6134702A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Physical design automation system and process for designing integrated circuit chips using multiway partitioning with constraints
Assignee: Bell Semiconductor LLC
•
Filing: 1997-12-16
•
Granted: 2000-10-17
•
Expires: 2017-12-16
Abstract
Abstract A process for designing an integrated circuit chip includes specifying a set of cells, a set of wiring nets for interconnecting the cells, and a set of regions on the chip in which the cells are to be placed. An assignment of the cells of the set to the regions is generated, and the set of cells is randomly divided into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment. Penalties are computed for assigning the cells of the second subset to the regions respectively, and the cells of the second subset are assigned to the regions such that a total penalty thereof is minimized. The process is repeated iteratively with the size of the second subset being progressively reduced relative to the size of the first subset until an end criterion is reached.
Inventors
- 👤 Ranko Scepanovic
- 👤 James S. Koford
- 👤 Valeriy B. Kudryavtsev
- 👤 Alexander E. Andreev
- 👤 Stanislav V. Aleshin
- 👤 Alexander S. Podkolzin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:30
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
98 words
A process for improving a placement of cells of a circuit design, wherein the cells are assigned to predefined regions in an assignment and are functionally interconnected by wiring nets, the process comprising the steps of: (a) dividing the cells into a first set of cells which remain in the assignment, and a second set of cells which are removed from the assignment; (b) computing penalties for assigning the cells of the second set to the regions respectively; and (c) assigning the cells of the second set to the regions such that a total penalty thereof is minimized.
Claim 2
Dependent Claim
98 words
A process for improving a placement of cells of a circuit design, wherein the cells are assigned to predefined regions in an assignment and are functionally interconnected by wiring nets, the process comprising the steps of: (a) dividing the cells into a first set of cells which remain in the assignment, and a second set of cells which are removed from the assignment; (b) computing penalties for assigning the cells of the second set to the regions respectively; and (c) assigning the cells of the second set to the regions such that a total penalty thereof is minimized.
Claim 3
Dependent Claim
47 words
The process as in claim 1, further comprising the step, performed before step (c), of: (d) specifying capacities of the regions for containing cells respectively; in which step (c) comprises assigning the cells of the second set to the regions such that the capacities are not exceeded.
Claim 4
Dependent Claim
79 words
The process as in claim 2, further comprising the step, performed after steps (a) and (d), of: (e) computing modified capacities for the regions from which the cells of the second set were removed as being equal to the capacities specified in step (d) minus the sizes of the cells that were removed in step (a); in which step (c) comprises assigning the cells of the second set to the regions such that the modified capacities are not exceeded.
Claim 5
Dependent Claim
49 words
The process as in claim 1, further comprising the steps, performed after step (c), of: (d) determining if an end criterion has been reached; (e) if an end criterion has been reached, terminating the process; and (f) if the end criterion has not been reached, jumping to step (a).
Claim 6
Dependent Claim
35 words
The process as in claim 4, further comprising the step, performed after step (f), of: (g) reducing a number of cells of the second set relative to a number of cells of the first set.
Claim 7
Dependent Claim
29 words
The process as in claim 5, in which the end criterion is such that the number of cells of the second set has been reduced below a predetermined value.
Claim 8
Dependent Claim
144 words
The process as in claim 4, further comprising the steps, performed after step (f), of: (g) reducing the number of cells of the second set relative to the number of cells of the first set and then jumping to step (a) if step (f) has been performed a predetermined number of times without reducing a number of cells of the second set relative to a number of cells of the first set; (h) determining if step (f) has been performed a predetermined number of times without reducing a number of cells of the second set relative to a number of cells of the first set; and (i) if step (f) has not been performed a predetermined number of times without reducing the number of cells of the second set relative to the number of cells of the first set, jumping directly to step (a).
Claim 9
Dependent Claim
30 words
The process as in claim 1, in which step (b) comprises computing the penalties as wirelengths of all of the nets connected to the cells of the second set respectively.
Claim 10
Dependent Claim
32 words
The process as in claim 1, in which step (c) comprises computing the total penalty as a total wirelength of all of the nets connected to the cells of the second set.
Claim 11
Dependent Claim
84 words
The process as in claim 1, in which step (c) comprises the substeps of: (d) constructing an initial assignment of the cells of the second set to the regions; (e) selecting a number of cells of the second set for movement between the regions; (f) computing an optimal permutation of movement of the selected number of cells between the regions such that the total penalty is minimized; and (g) modifying the initial assignment by moving the selected number of cells through the optimal permutation.
Claim 12
Dependent Claim
24 words
The process as in claim 10, in which step (f) comprises computing the optimal permutation as starting and ending in one of the regions.
Claim 13
Dependent Claim
111 words
A programmed digital computer for improving a placement of cells of a circuit design, wherein the cells are assigned to predefined regions and are functionally interconnected by wiring nets and said programmed digital computer has processing means, memory means and program operating in combination to perform the steps comprising: (a) dividing the cells into a first set of cells which remain in the assignment, and a second set of cells which are removed from the assignment; (b) computing penalties for assigning the cells of the second set to the regions respectively; and (c) assigning the cells of the second set to the regions such that a total penalty thereof is minimized.
Claim 14
Dependent Claim
111 words
A programmed digital computer for improving a placement of cells of a circuit design, wherein the cells are assigned to predefined regions and are functionally interconnected by wiring nets and said programmed digital computer has processing means, memory means and program operating in combination to perform the steps comprising: (a) dividing the cells into a first set of cells which remain in the assignment, and a second set of cells which are removed from the assignment; (b) computing penalties for assigning the cells of the second set to the regions respectively; and (c) assigning the cells of the second set to the regions such that a total penalty thereof is minimized.
Claim 15
Dependent Claim
61 words
The programmed digital computer as in claim 12, in which the processing means, memory means and program further operate in combination to perform the step, before step (c), of: (d) specifying capacities of the regions for containing cells respectively; in which step (c) comprises assigning the cells of the second set to the regions such that the capacities are not exceeded.
Claim 16
Dependent Claim
94 words
The programmed digital computer as in claim 13, in which the processing means, memory means and program further operate in combination to perform the step, performed after steps (a) and (d), of: (e) computing modified capacities for the regions from which the cells of the second set were removed as being equal to the capacities specified in step (d) minus the sizes of the cells that were removed in step (a); in which step (c) comprises assigning the cells of the second set to the regions such that the modified capacities are not exceeded.
Claim 17
Dependent Claim
62 words
The programmed digital computer as in claim 12, in which the processing means, memory means and program further operate in combination to perform the steps, after step (c), of: (d) determining if an end criterion has been reached; (e) if the end criterion has been reached, terminating operation; and (f) if the end criterion has not been reached, jumping to step (a).
Claim 18
Dependent Claim
49 words
The programmed digital computer as in claim 15, in which the processing means, memory means and program further operate in combination to perform the step, after step (f), of: (g) reducing a number of cells of the second set relative to a number of cells of the first set.
Claim 19
Dependent Claim
31 words
The programmed digital computer as in claim 16, in which the end criterion is such that the number of cells of the second set has been reduced below a predetermined value.
Claim 20
Dependent Claim
158 words
The programmed digital computer as in claim 15, in which the processing means, memory means and program further operate in combination to perform the step, after step (f), of: (g) determining if step (f) has been performed a predetermined number of times without reducing a number of cells of the second set relative to a number of cells of the first set; (h) if step (f) has not been performed a predetermined number of times without reducing the number of cells of the second set relative to the number of cells of the first set, jumping directly to step (a); and (i) if step (f) has been performed a predetermined number of times without reducing a number of cells of the second set relative to a number of cells of the first set, reducing the number of cells of the second set relative to the number of cells of the first set and then jumping to step (a).
Claim 21
Dependent Claim
32 words
The programmed digital computer as in claim 12, in which step (b) comprises computing the penalties as wirelengths of all of the nets connected to the cells of the second set respectively.
Claim 22
Dependent Claim
34 words
The programmed digital computer as in claim 12, in which step (c) comprises computing the total penalty as a total wirelength of all of the nets connected to the cells of the second set.
Claim 23
Dependent Claim
86 words
The programmed digital computer as in claim 12, in which step (c) comprises the substeps of: (d) constructing an initial assignment of the cells of the second set to the regions; (e) selecting a number of cells of the second set for movement between the regions; (f) computing an optimal permutation of movement of the selected number of cells between the regions such that the total penalty is minimized; and (g) modifying the initial assignment by moving the selected number of cells through the optimal permutation.
Claim 24
Dependent Claim
26 words
The programmed digital computer as in claim 12, in which step (f) comprises computing the optimal permutation as starting and ending in one of the regions.
References Cited (Backward Citations)
US5699265A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-17 | 2004-04-17 | 2004-10-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-17 | 2008-04-17 | 2008-10-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-17 | 2012-04-17 | 2012-10-17 | $7700.00 | Window Closed / Lapsed |