Cell placement method for microelectronic integrated circuit combining clustering, cluster placement and de-clustering
First Claim
1. A method of cell placement for a microelectronic circuit including a plurality of cells and interconnections between said cells, comprising the steps of:
- (a) grouping said cells into clusters using an optimization-driven technique including a predetermined local function of said interconnections and a predetermined global function of said interconnections;
(b) placing said clusters using a global optimization and partitioning technique; and
(c) placing said cells within said clusters using a partitioning technique.
6 Assignments
0 Petitions
Accused Products
Abstract
A large number of microelectronic circuit cells that are interconnected by a set of wiring nets are optimally placed on an integrated circuit chip such that all interconnects can be routed and the total wirelength of the interconnects is minimized. Cells are first grouped into disjoint clusters by an optimization-driven clustering technique, which uses both local and global connectivity information among the cells. This technique uses Rent'"'"'s rule for combining pairs of neighboring clusters, and selects among pairs of clusters having the same Rent'"'"'s exponent using distance information derived from global optimization processing. Clusters are prevented from growing to an excessive size by limiting the number of cells per cluster and the maximum area per cluster to predetermined maximum values. After the clusters are generated, they are placed using an optimization-driven placement technique, preferably "Gordian". Finally, the cells within each cluster are de-clustered and locally placed using a partitioning technique, preferably "min-cut".
-
Citations
24 Claims
-
1. A method of cell placement for a microelectronic circuit including a plurality of cells and interconnections between said cells, comprising the steps of:
-
(a) grouping said cells into clusters using an optimization-driven technique including a predetermined local function of said interconnections and a predetermined global function of said interconnections; (b) placing said clusters using a global optimization and partitioning technique; and (c) placing said cells within said clusters using a partitioning technique. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method determining an optimal placement for a plurality of objects having predetermined interconnections therebetween, comprising the steps of:
-
(a) grouping said objects into clusters using an optimization-driven technique including a predetermined local function of said interconnections and a predetermined global function of said interconnections; (b) placing said clusters using a global optimization and partitioning technique; and (c) placing said objects within said clusters using a partitioning technique. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification