Method and system for improving a placement of cells using energetic placement units alternating contraction and expansion operations

• US 5,754,444 A
• Filed: 10/29/1996
• Issued: 05/19/1998
• Est. Priority Date: 09/13/1994
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Koford, James S.
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/735,249
• Time in Patent Office: 567 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 395/500
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

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.

Claims

1. A method for improving a placement of cells for an integrated circuit chip, comprising the steps of:

(a) representing said cells as masses;

(b) representing interconnect nets between cells as springs such that each spring is connected between two of said masses;

(c) bringing said masses toward a minimum energy configuration by forces of said springs;

(d) moving said masses away from said minimum energy configuration; and

(e) repeatedly performing steps (c) and (d) until a predetermined criteria has been reached.

2. A method as in claim 1, wherein step (c) comprises moving a plurality of said masses toward gravity points at which net forces on said plurality of said masses are zero.

3. A method as in claim 2, wherein step (c) comprises moving a 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.

4. A method as in claim 1, wherein said moving 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 period of time.

5. A method as in claim 1, wherein step (d) comprises the substeps of:

(d1) computing a skew axis of said masses; and

(d2) moving said masses away from said skew axis.

6. A method as in claim 5, in which step (d1) comprises computing said skew axis as a regression line.

7. A method as in claim 6, in which step (d2) comprises moving said masses perpendicular to said regression line.

8. A method as in claim 7, wherein:

step (d1) comprises the substeps of;

(e1) computing a variance of said masses along said regression line;

(e2) computing a bias perpendicular to said regression line in accordance with said variance; and

step (d2) comprises computing new velocities for said masses in accordance with said bias and current velocities of said masses.

9. A method as in claim 1, 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.

10. A method as in claim 1, wherein step (e) further comprises the substeps of:

(e1) computing a total wirelength of said interconnect nets; and

(e2) repeatedly performing steps (c) and (d) until said total wirelength is less than a predetermined value.

11. A method for improving an arrangement of masses and nets that interconnect the masses, comprising the steps of:

(a) representing said nets as springs such that each spring is connected between two of said masses;

(b) bringing said masses toward a minimum energy configuration by forces of said springs;

(c) moving said masses away from said minimum energy configuration; and

(d) repeatedly performing steps (b) and (c) until a predetermined criteria has been reached.

12. A method as in claim 11, wherein step (b) comprises moving a plurality of said masses toward gravity points at which net forces on said plurality of masses are zero.

13. A method as in claim 12, wherein step (b) 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.

14. A method as in claim 11, wherein step (c) comprises the substeps of:

(c1) determining current positions of a plurality of said masses respectively;

(c2) determining current velocities of said plurality of said masses respectively;

(c3) computing net forces exerted by said springs on said plurality of said masses respectively;

(c4) computing new velocities of said plurality of said masses resulting from said net forces being applied thereto over a predetermined period of time; and

(c5) 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.

15. A method as in claim 11, wherein step (c) comprises the substeps of:

(c1) computing a skew axis of said masses; and

(c2) moving said masses away from said skew axis.

16. A method as in claim 15, in which step (c1) comprises computing said skew axis as a regression line.

17. A method as in claim 16, in which step (c2) comprises moving said masses perpendicular to said regression line.

18. A method as in claim 17, wherein

step (c1) comprises the substeps of:

(d1) computing a variance of said masses along said regression line; and

(d2) computing a bias perpendicular to said regression line in accordance with said variance; and

step (e) comprises computing new velocities for said masses in accordance with said bias and current velocities of said masses.

19. A method as in claim 11, in which step (d) comprises the substeps of:

(d1) computing a potential energy of said masses in accordance with forces of said springs;

(d2) computing a kinetic energy of said masses in accordance with velocities thereof;

(d3) performing step (b) if said kinetic energy is above a first predetermined value; and

(d4) performing step (c) if said potential energy is below a second predetermined value that is lower than said first predetermined value.

20. A method as in claim 11, wherein step (d) comprises the substeps of:

(d1) computing a total length of said nets; and

(d2) repeatedly performing steps (b) and (c) 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:

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 bringing said masses toward a minimum energy configuration by forces of said springs;

expansion means for propelling said masses 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 a predetermined criteria has been reached.

22. A system as in claim 21, wherein said contraction means move a plurality of said masses toward gravity points at which net forces on said plurality of said masses are zero.

23. A system as in claim 22, wherein said contraction means move said plurality of masses from current positions toward said gravity points by a predetermined percentage of distances between said current positions and said gravity points, respectively.

24. A system as in claim 21, wherein 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.

25. A system as in claim 21, wherein:

the computing means computes a skew axis of said masses; and

the expansion means moves said masses away from said skew axis.

26. A system as in claim 25, wherein the computing means computes said skew axis as a regression line.

27. A system as in claim 26, wherein the expansion means moves said masses perpendicular to said regression line.

28. A system as in claim 27, wherein 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.

29. A system as in claim 21, wherein:

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.

30. A system as in claim 21, further comprising:

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.

31. A system as in claim 21, wherein the placement representation means, contraction means, and expansion means collectively comprise a parallel processing system including a plurality of parallel processors.