Optimization processing for integrated circuit physical design automation system using chaotic fitness improvement method
First Claim
1. A method of relocating a cell in a cell placement for an integrated circuit chip, comprising the step of:
- (a) computing a centroid as a first predetermined function of relationships between said cell and other associated cells on the chip;
(b) computing a first length from a current location of said cell to said centroid;
(c) computing a second length as a second predetermined function of said first length; and
(d) moving said cell from said current location toward said centroid by said second length.
8 Assignments
0 Petitions
Accused Products
Abstract
The fitness of a cell placement for an integrated circuit chip is optimized by relocating at least some of cells to new locations that provide lower interconnect 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 new cell locations can be modified to include the effects of cells in other locations, such as by incorporating a function of cell density gradient or force direction into the computation. This spreads out clumps of cells so that the density of cells is more uniform throughout the placement. The attraction between cells in the nets is balanced against repulsion caused by a high local cell density, providing an optimized tradeoff of wirelength, feasibility and congestion.
-
Citations
34 Claims
-
1. A method of relocating a cell in a cell placement for an integrated circuit chip, comprising the step of:
-
(a) computing a centroid as a first predetermined function of relationships between said cell and other associated cells on the chip; (b) computing a first length from a current location of said cell to said centroid; (c) computing a second length as a second predetermined function of said first length; and (d) moving said cell from said current location toward said centroid by said second length. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method of increasing the fitness of a cell placement for an integrated circuit chip, comprising the steps of:
-
(a) computing centroids for a plurality of cells in said placement as a first predetermined function of relationships between said cells and other associated cells on the chip; (b) computing first lengths from current locations of said cells to said centroids respectively; (c) computing second lengths as a second predetermined function of said first lengths respectively; and (d) moving said cells from said current locations toward said centroids by said second lengths respectively. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
30. A method of relocating an entity in a permutation of a predetermined number of entities that are arranged in a pattern of locations respectively, comprising the steps of:
-
(a) computing a centroid as a first predetermined function of relationships between said entity and other associated entities in a predetermined manner; (b) computing a first length from a current location of said entity to said centroid; (c) computing a second length as a second predetermined function of said first length; and (d) moving said entity from said current location toward said centroid by said second length. - View Dependent Claims (31, 32, 33, 34)
-
Specification