Physical design automation system and method using monotonically improving linear clusterization
First Claim
1. A method of improving a placement of cells, and a routing including wires interconnecting said cells, for a microelectronic integrated circuit, the method comprising the steps of:
- (a) defining a grid including a plurality of first gridlines that extend parallel to a first axis, and a plurality of second gridlines that extend parallel to a second axis that is angularly displaced from said first axis;
(b) representing said cells as vertices located at intersections of said first and second gridlines;
(c) representing said wires as edges that extend along said first and second gridlines;
(d) creating clusters of vertices such that each cluster includes vertices located on a respective first gridline;
(e) computing a cover as including a minimum block of clusters that are connected to all other clusters by said wires extending along said second gridlines; and
(f) spatially reordering clusters outside said cover along said second axis in accordance with a predetermined reordering function.
6 Assignments
0 Petitions
Accused Products
Abstract
An initial placement of cells, and a routing including wires interconnecting the cells, is provided for a microelectronic integrated circuit. A grid is defined as including a plurality of first gridlines that extend parallel to a first axis, and a plurality of second gridlines that extend parallel to a second axis that is angularly displaced from the first axis. The cells are represented as vertices located at intersections of first and second gridlines, and the wires are represented as edges that extend along the first and second gridlines. Clusters of vertices are created such that each cluster includes vertices located on a respective first gridline. A "cover" is computed as including a minimum block of clusters that are connected to all other clusters by wires extending along the second gridlines. Clusters outside the cover are spatially reordered along the second axis away from the cover in descending order of numbers of wires extending from the clusters along the second gridlines. The placement is then updated and rerouted, and these operations are performed in the opposite direction and the two perpendicular directions. A quality factor, preferably the total wirelength of the routing, is computed and compared to a previous value. The entire operation is iteratively performed until the improvement in quality factor between consecutive iterations becomes less than a predetermined value. Due to the nature of the reordering, the quality factor improves monotonically for each iteration. The rerouting steps can be omitted, and edges defined by bounding boxes constructed around interconnect nets.
25 Citations
35 Claims
-
1. A method of improving a placement of cells, and a routing including wires interconnecting said cells, for a microelectronic integrated circuit, the method comprising the steps of:
-
(a) defining a grid including a plurality of first gridlines that extend parallel to a first axis, and a plurality of second gridlines that extend parallel to a second axis that is angularly displaced from said first axis; (b) representing said cells as vertices located at intersections of said first and second gridlines; (c) representing said wires as edges that extend along said first and second gridlines; (d) creating clusters of vertices such that each cluster includes vertices located on a respective first gridline; (e) computing a cover as including a minimum block of clusters that are connected to all other clusters by said wires extending along said second gridlines; and (f) spatially reordering clusters outside said cover along said second axis in accordance with a predetermined reordering function. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A physical design automation system for improving a placement of cells, and a routing including wires interconnecting said cells, for a microelectronic integrated circuit, the system comprising:
-
definition means for defining a grid as including a plurality of first gridlines that extend parallel to a first axis, and a plurality of second gridlines that extend parallel to a second axis that is angularly displaced from said first axis; representation means for representing said cells as vertices located at intersections of said first and second gridlines, and representing said wires as edges that extend along said first and second gridlines; clusterization means for creating clusters of vertices such that each cluster includes vertices located on a respective first gridline; cover computing means for computing a cover as including a minimum block of clusters that are connected to all other clusters by said wires extending along said second gridlines; and reordering means for spatially reordering clusters outside said cover along said second axis in accordance with a predetermined reordering function. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A method of improving a placement of cells and wires that interconnect said cells for an integrated circuit layout, comprising:
-
(a) defining a grid including a plurality of first gridlines that extend parallel to a first axis, and a plurality of second gridlines that extend parallel to a second axis that is angularly displaced from said first axis; (b) representing said cells as vertices located at intersections of said first and second gridlines; (c) representing said wires as edges that extend along said first and second gridlines; (d) forming a first set of clusters of vertices such that each cluster includes vertices located on respective first gridlines; (e) forming a cover as including a block of clusters that are connected to all other clusters by said wires extending along said second gridlines; (f) spatially reordering clusters outside said cover according to the number of said wires connecting other clusters outside of said cover in order to improve said placement of cells; and (g) re-routing said interconnect wires in order to maintain the same interconnection of the placement of cells. - View Dependent Claims (34, 35)
-
Specification