Method of cell placement for an itegrated circuit chip comprising integrated placement and cell overlap removal
First Claim
1. A computer implemented method of spatially distributing cells in a cell placement for an integrated circuit chip, comprising the steps of:
- (a) computing a density map representing cell densities in incremental blocks of said placement respectively;
(b) computing, from the density map, a warp map representing first repulsive forces exerted at centers of said blocks by cell densities in surrounding blocks respectively;
(c) interpolating, from the warp map, second repulsive forces acting on selected cells in the placement; and
(d) spatially distributing said selected cells in accordance with said second repulsive forces.
8 Assignments
0 Petitions
Accused Products
Abstract
A method of cell placement for an integrated circuit chip includes performing a chaotic improvement operation on an initial cell placement. At least some of the cells are relocated to new locations that provide lower interconnect wirelength and congestion. 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 λ. The value of λ is selected such that the cell relocation operations will cause the placement to converge toward an optimal configuration without chaotic diversion, but with a sufficiently high chaotic element to prevent the optimization operation from becoming stuck at local fitness maxima. The chaotic placement operation can generate illegal placements in which two or more cells can occupy one location, some locations can contain no cells and/or two or more cells can partially overlap. Cell overlap is reduced and the spatial distribution of the placement improved by computing a density map representing cell densities in incremental blocks of the placement respectively, computing, from the density map, a warp map representing first repulsive forces exerted at centers of said blocks by cell densities in surrounding blocks respectively, interpolating, from the warp map, second repulsive forces acting on selected cells in the placement and spatially distributing the selected cells in accordance with the second repulsive forces. Overlapping cells are then moved away from each other by a separate cell-to-cell repulsive force based on cell overlap to reduce any remaining overlap. The chaotic placement and spatial distribution phases are repeated, with the scale of movement for chaotic placement being progressively decreased and the scale of movement for spatial distribution being progressively increased. A final phase is then performed in which only the cell-to-cell repulsive force is used to eliminate the remaining overlap.
-
Citations
42 Claims
-
1. A computer implemented method of spatially distributing cells in a cell placement for an integrated circuit chip, comprising the steps of:
-
(a) computing a density map representing cell densities in incremental blocks of said placement respectively; (b) computing, from the density map, a warp map representing first repulsive forces exerted at centers of said blocks by cell densities in surrounding blocks respectively; (c) interpolating, from the warp map, second repulsive forces acting on selected cells in the placement; and (d) spatially distributing said selected cells in accordance with said second repulsive forces. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A computer implemented method of improving a placement of cells for an integrated circuit chip, comprising the steps of:
-
(a) selecting and moving a plurality of first cells in accordance with a first predetermined function to reduce a cost factor of said placement; (b) selecting and moving a plurality of second cells in accordance with a second predetermined function to improve a spatial distribution of said placement; (c) altering said first and second predetermined functions to decrease a scale factor for movement of said first cells and increase a scale factor for movement of second cells respectively; and (d) repeating steps (a) to (c). - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A method of improving a placement of cells for an integrated circuit chip, comprising the steps of:
-
(a) selecting and moving a plurality of first cells in accordance with a first predetermined function to reduce a cost factor of said placement; (b) selecting and moving a plurality of second cells in accordance with a second predetermined function to improve a spacial distribution of said placement; (c) altering said first and second predetermined functions to decrease a scale factor for movement of said first cells and increase a scale factor for movement of second cells respectively; and (d) repeatedly performing steps (a) to (c); in which said second predetermined function in step (b) comprises performing the substeps of; (e) computing a density map representing cell densities in incremental blocks of said placement respectively; (f) computing, from the density map, a warp map representing first repulsive forces exerted at centers of said blocks by cell densities in surrounding blocks in the placement respectively; (g) interpolating, from the warp map, second repulsive forces acting on said second cells; and (h) moving said second cells in accordance with said second repulsive forces. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42)
-
Specification