Method and system for improving a placement of cells using energetic placement with alternating contraction and expansion operations
First Claim
1. 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.
8 Assignments
0 Petitions
Accused Products
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.
63 Citations
31 Claims
-
1. 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. - View Dependent Claims (2, 3, 4)
-
-
5. 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.
-
-
6. 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. - View Dependent Claims (7, 8)
-
-
9. 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.
-
-
10. 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.
-
-
11. 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. - View Dependent Claims (12, 13, 14)
-
-
15. 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.
-
-
16. 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. - View Dependent Claims (17, 18)
-
-
19. 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.
-
-
20. 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.
-
-
21. 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. - View Dependent Claims (22, 23, 24, 25)
-
-
26. 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.
-
-
27. 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. - View Dependent Claims (28, 29)
-
-
30. 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.
-
-
31. 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.
-
Specification