Patent US5568636A successfully refreshed from Google Patents.
US5568636A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for improving a placement of cells using energetic placement with alternating contraction and expansion operations
Assignee: Bell Semiconductor LLC
•
Filing: 1994-09-13
•
Granted: 1996-10-22
•
Expires: 2014-09-13
Abstract
Abstract A method of cell placement for an integrated circuit chip includes performing a contraction operation by which at least some of the cells are relocated to new positions that provide lower interconnect wirelength. For each cell, the centroid of the net of cells to which the cell is connected is computed. The cell is then moved toward the centroid by a distance that is equal to the distance from the current position of the cell to the centroid multiplied by a "chaos" factor. This process continues until a specific energy condition is met; then the `expansion` mode is entered. An expansion operation is then performed by which the net force exerted on each cell by other cells in the placement and a resulting altered velocity of the cell are calculated, and a new cell position is calculated based on the altered velocity over an incremental length of time. The system stays in expansion mode until another energy criterion is met. The contraction and expansion modes are repeated in alternation, with the expansion operation preventing the cells from being undesirably converged by the contraction operation. At the start of each expansion operation, a normalization operation is performed to prevent skewing of the cells along a particular axis.
Inventors
- 👤 James S. Koford
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 10:18
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
106 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (f) repeatedly performing steps (d) and (e) until an optimization criteria has been reached.
Claim 2
Dependent Claim
106 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (f) repeatedly performing steps (d) and (e) until an optimization criteria has been reached.
Claim 3
Dependent Claim
33 words
A method as in claim 1, in which step (d) comprises moving a plurality of said masses toward gravity points at which net forces on said plurality of said masses are zero respectively.
Claim 4
Dependent Claim
39 words
A method as in claim 2, in which step (d) comprises moving said plurality of said masses from current positions toward said gravity points by a predetermined percentage of distances between said current positions and said gravity points respectively.
Claim 5
Dependent Claim
79 words
A method as in claim 1, in which step (f) comprises the substeps of: (f1) computing a potential energy of said masses in accordance with forces of said springs; (f2) computing a kinetic energy of said masses in accordance with velocities thereof; (f3) performing step (d) if said kinetic energy is above a first predetermined value; and (f4) performing step (e) if said potential energy is below a second predetermined value that is lower than said first predetermined value.
Claim 6
Dependent Claim
191 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (e) comprises the substeps of: (e1) determining current positions of a plurality of said masses respectively; (e2) determining current velocities of said plurality of said masses respectively; (e3) computing net forces exerted by said springs on said plurality of said masses respectively; (e4) computing new velocities of said plurality of said masses resulting from said net forces being applied thereto over a predetermined period of time; and (e5) computing new positions of said plurality of said masses in accordance with movement thereof from said current positions at said new velocities over said predetermined length of time.
Claim 7
Dependent Claim
191 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (e) comprises the substeps of: (e1) determining current positions of a plurality of said masses respectively; (e2) determining current velocities of said plurality of said masses respectively; (e3) computing net forces exerted by said springs on said plurality of said masses respectively; (e4) computing new velocities of said plurality of said masses resulting from said net forces being applied thereto over a predetermined period of time; and (e5) computing new positions of said plurality of said masses in accordance with movement thereof from said current positions at said new velocities over said predetermined length of time.
Claim 8
Dependent Claim
118 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (e) comprises the substeps of: (e1) computing a skew axis of said masses; and (e2) moving said masses away from said skew axis.
Claim 9
Dependent Claim
118 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (e) comprises the substeps of: (e1) computing a skew axis of said masses; and (e2) moving said masses away from said skew axis.
Claim 10
Dependent Claim
19 words
A method as in claim 6, in which step (e1) comprises computing said skew axis as a regression line.
Claim 11
Dependent Claim
19 words
A method as in claim 7, in which step (e2) comprises moving said masses perpendicular to said regression line.
Claim 12
Dependent Claim
192 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: step (e) comprises the substeps of: (f) computing a skew axis of said masses; and (g) moving said masses away from said skew axis; step (f) comprises computing said skew axis as a regression line; step (g) comprises moving said masses perpendicular to said regression line; step (f) comprises the substeps of: (f1) computing a variance of said masses along said regression line; (f2) computing a bias perpendicular to said regression line in accordance with said variance; and step (g) comprises computing new velocities for said masses in accordance with said bias and current velocities of said masses.
Claim 13
Dependent Claim
192 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: step (e) comprises the substeps of: (f) computing a skew axis of said masses; and (g) moving said masses away from said skew axis; step (f) comprises computing said skew axis as a regression line; step (g) comprises moving said masses perpendicular to said regression line; step (f) comprises the substeps of: (f1) computing a variance of said masses along said regression line; (f2) computing a bias perpendicular to said regression line in accordance with said variance; and step (g) comprises computing new velocities for said masses in accordance with said bias and current velocities of said masses.
Claim 14
Dependent Claim
142 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (f) repeatedly performing steps (d) and (e) until an optimization criteria has been reached; in which step (f) comprises the substeps of: (f1) computing a total wirelength of said interconnect nets; and (f2) repeatedly performing steps (d) and (e) until said total wirelength is less than a predetermined value.
Claim 15
Dependent Claim
142 words
A computer implemented method for improving a placement of cells for an integrated circuit chip, comprising the steps of: (a) generating an initial placement of said cells; (b) representing said cells as masses; (c) representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; (d) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and (e) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (f) repeatedly performing steps (d) and (e) until an optimization criteria has been reached; in which step (f) comprises the substeps of: (f1) computing a total wirelength of said interconnect nets; and (f2) repeatedly performing steps (d) and (e) until said total wirelength is less than a predetermined value.
Claim 16
Dependent Claim
98 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (e) repeatedly performing steps (c) and (d) until an optimization criteria has been reached.
Claim 17
Dependent Claim
98 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (e) repeatedly performing steps (c) and (d) until an optimization criteria has been reached.
Claim 18
Dependent Claim
33 words
A method as in claim 11, in which step (c) comprises moving a plurality of said masses toward gravity points at which net forces on said plurality of said masses are zero respectively.
Claim 19
Dependent Claim
39 words
A method as in claim 12, in which step (c) comprises moving said plurality of said masses from current positions toward said gravity points by a predetermined percentage of distances between said current positions and said gravity points respectively.
Claim 20
Dependent Claim
79 words
A method as in claim 11, in which step (e) comprises the substeps of: (e1) computing a potential energy of said masses in accordance with forces of said springs; (e2) computing a kinetic energy of said masses in accordance with velocities thereof; (e3) performing step (c) if said kinetic energy is above a first predetermined value; and (e4) performing step (d) if said potential energy is below a second predetermined value that is lower than said first predetermined value.
Claim 21
Dependent Claim
182 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (d) comprises the substeps of: (d1) determining current positions of a plurality of said masses respectively; (d2) determining current velocities of said plurality of said masses respectively; (d3) computing net forces exerted by said springs on said plurality of said masses respectively; (d4) computing new velocities of said plurality of said masses resulting from said net forces being applied thereto over a predetermined period of time; and (d5) computing new positions of said plurality of said masses in accordance with movement thereof from said current positions at said new velocities over said predetermined length of time.
Claim 22
Dependent Claim
182 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (d) comprises the substeps of: (d1) determining current positions of a plurality of said masses respectively; (d2) determining current velocities of said plurality of said masses respectively; (d3) computing net forces exerted by said springs on said plurality of said masses respectively; (d4) computing new velocities of said plurality of said masses resulting from said net forces being applied thereto over a predetermined period of time; and (d5) computing new positions of said plurality of said masses in accordance with movement thereof from said current positions at said new velocities over said predetermined length of time.
Claim 23
Dependent Claim
109 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (d) comprises the substeps of: (d1) computing a skew axis of said masses; and (d2) moving said masses away from said skew axis.
Claim 24
Dependent Claim
109 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which step (d) comprises the substeps of: (d1) computing a skew axis of said masses; and (d2) moving said masses away from said skew axis.
Claim 25
Dependent Claim
19 words
A method as in claim 16, in which step (d1) comprises computing said skew axis as a regression line.
Claim 26
Dependent Claim
19 words
A method as in claim 17, in which step (d2) comprises moving said masses perpendicular to said regression line.
Claim 27
Dependent Claim
183 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: step (d) comprises the substeps of: (d1) computing a skew axis of said masses; and (d1) moving said masses away from said skew axis; step (e) comprises computing said skew axis as a regression line; step (f) comprises moving said masses perpendicular to said regression line; step (e) comprises the substeps of: (e1)computing a variance of said masses along said regression line; and (e2) computing a bias perpendicular to said regression line in accordance with said variance; and step (f) comprises computing new velocities for said masses in accordance with said bias and current velocities of said masses.
Claim 28
Dependent Claim
183 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: step (d) comprises the substeps of: (d1) computing a skew axis of said masses; and (d1) moving said masses away from said skew axis; step (e) comprises computing said skew axis as a regression line; step (f) comprises moving said masses perpendicular to said regression line; step (e) comprises the substeps of: (e1)computing a variance of said masses along said regression line; and (e2) computing a bias perpendicular to said regression line in accordance with said variance; and step (f) comprises computing new velocities for said masses in accordance with said bias and current velocities of said masses.
Claim 29
Dependent Claim
132 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (e) repeatedly performing steps (c) and (d) until an optimization criteria has been reached; in which step (e) comprises the substeps of: (e1) computing a total length of said nets; and (e2) repeatedly performing steps (c) and (d) until said total length is less than a predetermined value.
Claim 30
Dependent Claim
132 words
A computer implemented method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of: (a) generating an initial arrangement of said masses; (b) representing said nets as springs such that each spring is connected between two of said masses; (c) performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; (d) performing an expansion operation by which said masses are moved away from said minimum energy configuration; and (e) repeatedly performing steps (c) and (d) until an optimization criteria has been reached; in which step (e) comprises the substeps of: (e1) computing a total length of said nets; and (e2) repeatedly performing steps (c) and (d) until said total length is less than a predetermined value.
Claim 31
Dependent Claim
131 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration; and control means for controlling the contraction means and the expansion means to repeatedly perform said contraction operation and said expansion operation respectively until an optimization criteria has been reached.
Claim 32
Dependent Claim
131 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration; and control means for controlling the contraction means and the expansion means to repeatedly perform said contraction operation and said expansion operation respectively until an optimization criteria has been reached.
Claim 33
Dependent Claim
33 words
A system as in claim 21, in which the contraction means moves a plurality of said masses toward gravity points at which net forces on said plurality of said masses are zero respectively.
Claim 34
Dependent Claim
39 words
A system as in claim 22, in which the contraction means moves said plurality of said masses from current positions toward said gravity points by a predetermined percentage of distances between said current positions and said gravity points respectively.
Claim 35
Dependent Claim
95 words
A system as in claim 21, in which: the control means comprises computing means for computing a potential energy of said masses in accordance with forces of said springs and computing a kinetic energy of said masses in accordance with velocities thereof; the control means controls the contraction means to perform said contraction operation if said kinetic energy is above a first predetermined value; and the control means controls the expansion means to perform said expansion operation if said potential energy is below a second predetermined value that is lower than said first predetermined value.
Claim 36
Dependent Claim
33 words
A system as in claim 21, in which the initial placement generating means, placement representation means, contraction means and expansion means collectively comprise a parallel processing system including a plurality of parallel processors.
Claim 37
Dependent Claim
201 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which the expansion means comprises: determination means for determining current positions of a plurality of said masses respectively, and determining current velocities of said plurality of said masses respectively; computing means for computing net forces exerted by said springs on said plurality of said masses respectively, computing new velocities of said plurality of said masses resulting from said net forces being applied thereto over a predetermined period of time, and computing new positions of said plurality of said masses in accordance with movement thereof from said current positions at said new velocities over said predetermined length of time.
Claim 38
Dependent Claim
201 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration; in which the expansion means comprises: determination means for determining current positions of a plurality of said masses respectively, and determining current velocities of said plurality of said masses respectively; computing means for computing net forces exerted by said springs on said plurality of said masses respectively, computing new velocities of said plurality of said masses resulting from said net forces being applied thereto over a predetermined period of time, and computing new positions of said plurality of said masses in accordance with movement thereof from said current positions at said new velocities over said predetermined length of time.
Claim 39
Dependent Claim
126 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: the computing means computes a skew axis of said masses; and the expansion means moves said masses away from said skew axis.
Claim 40
Dependent Claim
126 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: the computing means computes a skew axis of said masses; and the expansion means moves said masses away from said skew axis.
Claim 41
Dependent Claim
19 words
A system as in claim 27, in which the computing means computes said skew axis as a regression line.
Claim 42
Dependent Claim
19 words
A system as in claim 28, in which the expansion means moves said masses perpendicular to said regression line.
Claim 43
Dependent Claim
192 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: the computing means computes a skew axis of said masses; the expansion means moves said masses away from said skew axis; the computing means computes said skew axis as a regression line; the expansion means moves said masses perpendicular to said regression line; and the computing means computes a variance of said masses along said regression line, computes a bias perpendicular to said regression line in accordance with said variance, and computes new velocities for said masses in accordance with said bias and current velocities of said masses.
Claim 44
Dependent Claim
192 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; and expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration, in which: the computing means computes a skew axis of said masses; the expansion means moves said masses away from said skew axis; the computing means computes said skew axis as a regression line; the expansion means moves said masses perpendicular to said regression line; and the computing means computes a variance of said masses along said regression line, computes a bias perpendicular to said regression line in accordance with said variance, and computes new velocities for said masses in accordance with said bias and current velocities of said masses.
Claim 45
Dependent Claim
145 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration; computing means for computing a total wirelength of said interconnect nets; and control means for repeatedly controlling the contraction means and the expansion means to perform said contraction operation and said expansion operation respectively until said total wirelength is less than a predetermined value.
Claim 46
Dependent Claim
145 words
A physical design automation system for generating an optimized placement of cells for an integrated circuit chip, comprising: initial placement generating means for generating an initial placement of said cells; placement representation means for representing said cells as masses, and representing interconnect nets of said cells as springs such that each spring is connected between two of said masses; contraction means for performing a contraction operation by which said masses are moved toward a minimum energy configuration by forces of said springs; expansion means for performing an expansion operation by which said masses are moved away from said minimum energy configuration; computing means for computing a total wirelength of said interconnect nets; and control means for repeatedly controlling the contraction means and the expansion means to perform said contraction operation and said expansion operation respectively until said total wirelength is less than a predetermined value.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-22 | 2000-04-22 | 2000-10-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-22 | 2004-04-22 | 2004-10-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-22 | 2008-04-22 | 2008-10-22 | $7700.00 | Window Closed / Lapsed |