Physical design automation system and process for designing integrated circuit chips using highly parallel sieve optimization with multiple "jiggles"
First Claim
1. A process for designing an integrated circuit chip, comprising the steps of:
- (a) providing a placement of clusters of cells, each cluster being assigned to one of plural predefined and non-overlapping regions on the chip;
(b) combining the pre-defined and non-overlapping regions to form region groups;
(c) performing a first cluster placement improvement operation within respective region groups that re-assigns the clusters in each region group to the other pre-defined and non-overlapping regions in said each region group when a cell placement cost function is reduced;
(d) re-combining the pre-defined and non-overlapping regions to form different region groups; and
(e) performing a second cluster placement improvement operation within respective different region groups that re-assigns the clusters in each different region group to the other pre-defined and non-overlapping regions in said each different region group when a cell placement cost function is reduced.
8 Assignments
0 Petitions
Accused Products
Abstract
A process for implementation on a programmed digital computer includes providing a placement of clusters of cells which are assigned to regions on an integrated circuit chip, and combining the regions to form region groups. The region groups collectively constitute a "jiggle" which resembles a sieve. The clusters in each region group are re-assigned to the regions in the region group. The regions are recombined to form different region groups (a different jiggle), and the clusters in each different region group are re-assigned to the regions in the different region group. These steps are repeated using at least two, preferably four different jiggles, until an end criterion is reached. Then, the regions and clusters are hierarchically subdivided, and the process is repeated for each hierarchical level until the clusters have been reduced to individual cells. The regions of the region groups at each level are contiguous, and the region groups overlap, such that a cluster can be moved from any region to any other region on the chip by sufficient repetition of the assignment step using alternating jiggles.
37 Citations
32 Claims
-
1. A process for designing an integrated circuit chip, comprising the steps of:
-
(a) providing a placement of clusters of cells, each cluster being assigned to one of plural predefined and non-overlapping regions on the chip; (b) combining the pre-defined and non-overlapping regions to form region groups; (c) performing a first cluster placement improvement operation within respective region groups that re-assigns the clusters in each region group to the other pre-defined and non-overlapping regions in said each region group when a cell placement cost function is reduced; (d) re-combining the pre-defined and non-overlapping regions to form different region groups; and (e) performing a second cluster placement improvement operation within respective different region groups that re-assigns the clusters in each different region group to the other pre-defined and non-overlapping regions in said each different region group when a cell placement cost function is reduced. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A programmed digital computer for designing an integrated circuit chip, comprising:
-
memory means for storing a program including instructions and data; and processing means for executing the program; the processing means, memory means and program operating in combination for performing the steps of; (a) providing a placement of clusters of cells, each cluster being assigned to one of plural pre-defined and non-overlapping regions on the chip; (b) combining the pre-defined and non-overlapping regions to form region groups; (c) performing a first cluster placement improvement operation within respective region groups that re-assigns the clusters in each region group to the other pre-defined and non-overlapping regions in said each region group when a cell placement cost function is reduced; (d) re-combining the pre-defined and non-overlapping regions to form different region groups; and (e) performing a second cluster placement improvement operation within respective different region groups that re-assigns the clusters in each different region group to the other pre-defined and non-overlapping regions in said each different region group when a cell placement cost function is reduced. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
Specification