Physical design automation system and method using hierarchical clusterization and placement improvement based on complete re-placement of cell clusters
First Claim
1. A method of producing a placement of cells for a microelectronic integrated circuit in accordance with specified cell interconnects, comprising the steps:
- (a) constructing a hierarchial cluster tree in accordance with said interconnects in which a lowest level of said tree includes clusters of said cells, and each successively higher level includes clusters of clusters from a respective successively lower level;
(b) placing said clusters of each successively lower level within respective clusters of each successively higher level in progressively decreasing order of levels by computing a gravity point for each cluster and modifying cell placement based on a predetermined gravity point adjustment function; and
(c) placing said cells within respective clusters of said lowest level.
8 Assignments
0 Petitions
Accused Products
Abstract
A method of producing a placement of cells for a microelectronic integrated circuit in accordance with specified cell interconnects includes constructing a hierarchial cluster tree based on the interconnects in which a lowest level of the tree includes clusters of interconnected cells, and each successively higher level includes clusters of interconnected clusters from a successively lower level. Clusters in each level are merged by a min-cut operation. Clusters of each successively lower level are then placed within clusters of each successively higher level in progressively decreasing order of levels. Clusters are placed in each level by computing a current gravity point for each cluster in accordance with the cells therein, computing a new gravity point for each cluster in accordance with the current gravity points and the interconnects, and moving each cluster from the current gravity point to the new gravity point. Cells within clusters of the lowest level are then placed by calculating positions of the cells in a row direction, and placing the cells in columns in increasing order of the calculated positions in the row direction. The method is implemented by a parallel processing system including a plurality of parallel processors.
55 Citations
41 Claims
-
1. A method of producing a placement of cells for a microelectronic integrated circuit in accordance with specified cell interconnects, comprising the steps:
-
(a) constructing a hierarchial cluster tree in accordance with said interconnects in which a lowest level of said tree includes clusters of said cells, and each successively higher level includes clusters of clusters from a respective successively lower level; (b) placing said clusters of each successively lower level within respective clusters of each successively higher level in progressively decreasing order of levels by computing a gravity point for each cluster and modifying cell placement based on a predetermined gravity point adjustment function; and (c) placing said cells within respective clusters of said lowest level. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A physical design automation system for producing a placement of cells for a microelectronic integrated circuit in accordance with specified cell interconnects, comprising:
-
tree construction means for constructing a hierarchial cluster tree in accordance with said interconnects in which a lowest level of said tree includes clusters of said cells, and each successively higher level includes clusters of clusters from a respective successively lower level; cluster placement means for placing said clusters of each successively lower cell within respective clusters of each successively higher level in progressively decreasing order of levels by computing a gravity point for each cluster and modifying cell placement based on a predetermined gravity point adjustment function; and cell placement means for placing said cells respective clusters of said lowest level. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41)
-
Specification