Patent US5699265A successfully refreshed from Google Patents.
US5699265A
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: 1995-09-08
•
Granted: 1997-12-16
•
Expires: 2015-09-08
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-10-30 14:12
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
123 words
A process for designing an integrated circuit chip, comprising the steps of: (a) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.
Claim 2
Dependent Claim
123 words
A process for designing an integrated circuit chip, comprising the steps of: (a) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.
Claim 3
Dependent Claim
47 words
A process as in claim 1, further comprising the step, performed before step (c), of: (g) specifying capacities of the regions for containing cells respectively; in which step (f) comprises assigning the cells of the second subset to the regions such that the capacities are not exceeded.
Claim 4
Dependent Claim
79 words
A process as in claim 2, further comprising the step, performed between steps (d) and (e), of: (h) computing modified capacities for the regions from which the cells of the second subset were removed as being equal to the capacities specified in step (g) minus the sizes of the cells that were removed in step (d); in which step (f) comprises assigning the cells of the second subset to the regions such that the modified capacities are not exceeded.
Claim 5
Dependent Claim
49 words
A process as in claim 1, further comprising the steps, performed after step (f), of: (g) determining if an end criterion has been reached; (h) if the end criterion has been reached, terminating the process; and (i) if the end criterion has not been reached, jumping to step (d).
Claim 6
Dependent Claim
37 words
A process as in claim 4, further comprising the step, performed between steps (i) and (d), of: (j) reducing a number of cells of the second subset relative to a number of cells of the first subset.
Claim 7
Dependent Claim
29 words
A process as in claim 5, in which the end criterion is such that the number of cells of the second subset has been reduced below a predetermined value.
Claim 8
Dependent Claim
146 words
A process as in claim 4, further comprising the step, performed between steps (i) and (d), of: (j) determining if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset; (k) if step (i) has not been performed a predetermined number of times without reducing the number of cells of the second subset relative to the number of cells of the first subset, jumping directly to step (d); and (l) if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset, reducing the number of cells of the second subset relative to the number of cells of the first subset and then jumping to step (d).
Claim 9
Dependent Claim
30 words
A process as in claim 1, in which step (e) comprises computing the penalties as wirelengths of all of the nets connected to the cells of the second set respectively.
Claim 10
Dependent Claim
33 words
A process as in claim 1, in which step (f) further 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
A process as in claim 1, in which step (f) comprises the substeps of: (g) constructing an initial assignment of the cells of the second subset to the regions; (h) selecting a number of cells of the second subset for movement between the regions; (i) computing an optimal permutation of movement of the selected number of cells between the regions such that the total penalty is minimized; and (j) modifying the initial assignment by moving the selected number of cells through the optimal permutation.
Claim 12
Dependent Claim
24 words
A process as in claim 10, in which step (i) comprises computing the optimal permutation as starting and ending in one of the regions.
Claim 13
Dependent Claim
154 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) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.
Claim 14
Dependent Claim
154 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) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.
Claim 15
Dependent Claim
61 words
A 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: (g) specifying capacities of the regions for containing cells respectively; in which step (f) comprises assigning the cells of the second subset to the regions such that the capacities are not exceeded.
Claim 16
Dependent Claim
93 words
A programmed digital computer as in claim 13, in which the processing means, memory means and program further operate in combination to perform the step, between steps (d) and (e), of: (h) computing modified capacities for the regions from which the cells of the second subset were removed as being equal to the capacities specified in step (g) minus the sizes of the cells that were removed in step (d); in which step (f) comprises assigning the cells of the second subset to the regions such that the modified capacities are not exceeded.
Claim 17
Dependent Claim
62 words
A 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 (f), of: (g) determining if an end criterion has been reached; (h) if the end criterion has been reached, terminating operation; and (i) if the end criterion has not been reached, jumping to step (d).
Claim 18
Dependent Claim
51 words
A programmed digital computer as in claim 15, in which the processing means, memory means and program further operate in combination to perform the step, between steps (i) and (d), of: (j) reducing a number of cells of the second subset relative to a number of cells of the first subset.
Claim 19
Dependent Claim
31 words
A programmed digital computer as in claim 16, in which the end criterion is such that the number of cells of the second subset has been reduced below a predetermined value.
Claim 20
Dependent Claim
160 words
A programmed digital computer as in claim 15, in which the processing means, memory means and program further operate in combination to perform the steps, between steps (i) and (d), of: (j) determining if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset; (k) if step (i) has not been performed a predetermined number of times without reducing the number of cells of the second subset relative to the number of cells of the first subset, jumping directly to step (d); and (l) if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset, reducing the number of cells of the second subset relative to the number of cells of the first subset and then jumping to step (d).
Claim 21
Dependent Claim
32 words
A programmed digital computer as in claim 12, in which step (e) 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
A programmed digital computer as in claim 12, in which step (f) 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
A programmed digital computer as in claim 12, in which step (f) comprises the substeps of: (g) constructing an initial assignment of the cells of the second subset to the regions; (h) selecting a number of cells of the second subset for movement between the regions; (i) computing an optimal permutation of movement of the selected number of cells between the regions such that the total penalty is minimized; and (j) modifying the initial assignment by moving the selected number of cells through the optimal permutation.
Claim 24
Dependent Claim
26 words
A programmed digital computer as in claim 21, in which step (i) comprises computing the optimal permutation as starting and ending in one of the regions.
References Cited (Backward Citations)
US3617714A
Cited
US5187784A
Cited
US5521836A
Cited
US5359538A
Cited
US5513124A
Cited
US5566078A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-15 | 2001-06-16 | 2001-12-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-15 | 2005-06-16 | 2005-12-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-15 | 2009-06-16 | 2009-12-16 | $7700.00 | Window Closed / Lapsed |