Method of cell placement for an integrated circuit chip comprising chaotic placement and moving windows
First Claim
1. A method of cell placement for an integrated circuit chip, comprising the steps of:
- (a) computing centroids for a plurality of cells of said placement as a first predetermined function of locations of cells to which said cells are connected respectively;
(b) computing first distances from current locations of said cells to said centroids respectively;
(c) computing second distances as a second predetermined function of said first distances respectively;
(d) moving said cells from said current locations toward said centroids by said second distances respectively;
(e) defining a movable window that delineates subsets of cells of said placement; and
(f) individually performing a predetermined placement improvement operation on said subsets.
3 Assignments
0 Petitions
Accused Products
Abstract
In a physical design automation system for producing an optimized cell placement for an integrated circuit chip, a placement optimization methodology is decomposed into a plurality of cell placement optimization processes that are performed simultaneously by parallel processors on input data representing the chip. The results of the optimization processes are recomposed to produce an optimized cell placement. The fitness of the optimized cell placement is analyzed, and the parallel processors are controlled to selectively repeat performing the optimization processes for further optimizing the optimized cell placement if the fitness does not satisfy a predetermined criterion. The system can be applied to initial placement, routing, placement improvement and other problems. The processors can perform the same optimization process on different placements, or on areas of a single placement. Alternatively, the processors can perform different optimization processes simultaneously on a single initial placement, with the resulting processed placement having the highest fitness being selected as the optimized placement. The processors can further selectively reprocess areas of a placement having high cell interconnect congestion or other low fitness parameters.
-
Citations
40 Claims
-
1. A method of cell placement for an integrated circuit chip, comprising the steps of:
-
(a) computing centroids for a plurality of cells of said placement as a first predetermined function of locations of cells to which said cells are connected respectively; (b) computing first distances from current locations of said cells to said centroids respectively; (c) computing second distances as a second predetermined function of said first distances respectively; (d) moving said cells from said current locations toward said centroids by said second distances respectively; (e) defining a movable window that delineates subsets of cells of said placement; and (f) individually performing a predetermined placement improvement operation on said subsets. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A method of cell placement for an integrated circuit chip, comprising the steps of:
-
(a) performing a chaotic placement improvement operation on said placement; and (b) performing a predetermined fitness improvement operation on said placement within at least one moving window. - View Dependent Claims (36, 37, 38, 39)
-
-
40. A method of cell placement for an integrated circuit chip, comprising the steps of:
-
performing a chaotic cell placement of said cells using the attractive properties and repelling properties between said cells; distributing cells occupying the same location as other cells into respective locations such that each location is occupied by one cell; defining a movable window delineating subsets of cells of said placement; and performing a predetermined placement improvement operation on said subsets defined by the movable window.
-
Specification