Integrated circuit cell placement using optimization-driven clustering

• US 5,566,078 A
• Filed: 05/26/1993
• Issued: 10/15/1996
• Est. Priority Date: 05/26/1993
• Status: Expired due to Term

• Current Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Ding, Cheng-Liang, Ho, Ching-Yen
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/068,013
• Time in Patent Office: 1,238 Days
• Field of Search: 364/490, 364/491, 364/488, 364/489, 257/208, 257/211
• US Class Current: 716/124
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

An integrated circuit layout technique is described which employs an optimization-driven clustering technique to provide improved cell placement. The technique utilizes clustering of cells based upon Rent'"'"'s rule, with global-optimization-derived inter-cell distances being used to break ties when identical Rent exponents are encountered. A constraint on the number of cells permitted to be in a cluster and a constraint on the maximum Rent exponent which to be considered for merging clusters minimize the "overgrowth" of clusters and serve to even out cluster size, ideally suiting the technique to conventional partitioning and placement schemes.

Claims

1. A method of making, including layout functions for, an integrated circuit, comprising:

providing an integrated circuit design, said design including a plurality of cells and a plurality of interconnections between the cells, each cell having a one or more connection points;

providing an integrated circuit die size and shape and defining within the die size and shape a layout area;

globally optimizing a placement of all of the cells within the layout area based upon an objective function, wherein said step of optimizing assigns a location to each cell within the layout area and yields inter-cell physical distances for each pair of cells;

defining each cell as a single-cell cluster;

identifying neighboring clusters according to the placement;

grouping pairs of neighboring clusters into larger multi-cell clusters having internal connections, external connections and a total number of included cells, by;

selecting a pair of neighboring clusters which, if merged, would form a larger cluster with a relatively high degree of internal connectivity and a relatively low degree of external connectivity according to a single figure-of-merit for the larger clusters,

selecting from multiple pairs of clusters which have the same figure-of-merit only that pair of clusters which has a least inter-cluster physical distance, whereby said least inter-cluster physical distance serves as a tie-breaker for selecting between the multiple pairs of clusters having the same figure of merit, and

merging the selected pair of neighboring clusters into a larger multi-cell cluster and eliminating the pair of neighboring clusters, if the larger cluster has a total number of included cells which is less than a pre-defined number;

repeatedly grouping pairs of clusters into larger clusters until a termination condition is met;

completing a layout process based upon the integrated circuit design, the integrated circuit die size and shape, and die area partitioning and placement of the clusters of cells, said layout process resulting in an integrated circuit layout.

2. A method of making, including layout functions for, an integrated circuit, according to claim 1, wherein the figure-of-merit for each larger cluster is determined according to:

##EQU6## where r is the figure-of-merit, E is the number of connections between cells within the larger cluster and cells outside of the larger cluster, B is the total number of cells within the larger cluster, and T is the total number of connection points on cells included within the larger cluster.

3. A method of making, including layout functions for, an integrated circuit, according to claim 2, wherein:

the selection of a pair of neighboring cells according to the figure-of-merit is accomplished by selecting the pair of neighboring cells having the lowest figure-of-merit value for the larger cluster to be formed therefrom.

4. A method of making, including layout functions for, an integrated circuit according to claim 1, wherein:

the distance between each neighboring pair of clusters C_i and C_j is determined according to the equation;

space="preserve" listing-type="equation">dist(C.sub.i,C.sub.j)=max{dist(c.sub.k,c.sub.l)|.sub.∀

(c.sbsb.k.sub.ε

C.sbsb.i.sub.,c.sbsb.l.sub.ε

c.sbsb.j.sub.) }

where;

c_k is a cell k within cluster C_i, c_l is a cell l within cluster C_j, and dist(c_k,c_l) is the distance from cell c_k to cell c_l.

5. A method of making, including layout functions for, an integrated circuit according to claim 1, further comprising the step of forming a pair list of neighboring clusters containing the figure-of-merit for each of the neighboring clusters, wherein:

the termination condition is met when either of two conditions, designated "first condition" and "second condition," is met;

the first condition being that there are no remaining entries in the pair list; and

the second condition being that the figures-of-merit associated with all of the remaining entries in the pair list are outside of a pre-defined range of values.

6. A method of making, including layout functions for, an integrated circuit, comprising the steps of:

a) providing an integrated circuit die size and shape;

b) defining with the integrated circuit die size and shape a layout area;

c) providing an integrated circuit design including a plurality of cells, and a plurality of inter-cell connections, said cells each having one or more connection points by which the inter-cell connections are accomplished;

d) performing a global optimization process to arrive at an optimal placement of all of the cells within the layout area based upon an objective function, wherein said optimization assigns a location to each cell within the layout area, and storing location coordinates of each cell in a cluster list, according to the placement;

e) defining each cell in the cluster list as a cluster;

f) identifying pairs of neighboring clusters according to the placement, computing a single figure-of-merit for each pair of neighboring clusters, and storing an identifier and the computed figure-of-merit for each pair of neighboring clusters in a pair list;

g) sorting the pair list according to the figure-of-merit;

h ) selecting and removing the pair list entry for a neighboring pair of clusters having a best figure-of-merit according to a pre-defined criterion, unless there is a "tie" where two or more entries in the pair list have equal best figures-of-merit, in that case selecting and removing from the pair list the entry corresponding to the neighboring pair of clusters having the best figure-of-merit and having the least physical distance between the clusters, whereby the least physical distance between clusters serves as a tie-breaker for selecting between the entries in the pair list having the equal best figures-of-merit;

i) proceeding to step "m" if the figure-of-merit for the selected neighboring pair of clusters fails to meet a pre-determined first constraint, otherwise proceeding to step "j";

j) proceeding to step "1" if the total number of cells within the neighboring pair of clusters fails to meet a pre-defined second constraint, otherwise proceeding to step "k";

k) forming a new cluster by merging the selected neighboring pair of clusters into a single cluster, updating the cluster list to include the new cluster and a set of coordinates for the new cluster, computing new figures-of-merit for new entries in the pair list which includes neighboring pairs of clusters which include the new cluster, eliminating entries in the pair list corresponding to any neighboring pair of clusters which includes either of the clusters in the selected neighboring pair, and re-sorting the pair list according to the figure of merit;

l) proceeding to step "h" if there are any remaining entries in the pair list, otherwise proceeding to step "m";

m) completing a layout process based upon the integrated circuit design, the integrated circuit die size and shape, and die area partitioning and placement of the clusters of cells, said layout process resulting in an integrated circuit layout.

7. A method of making, including layout functions for, an integrated circuit, according to claim 6, wherein the figure-of-merit for each pair of neighboring clusters is determined according to:

##EQU7## where r is the figure-of-merit, E is the number of connections between cells within the pair of neighboring clusters and cells outside of the larger cluster, B is the total number of cells within the pair of neighboring clusters, and T is the total number of connection points on cells included within the pair of neighboring clusters.

8. A method of making, including layout functions for, an integrated circuit, according to claim 7, wherein:

the first pre-determined constraint is that the figure-of-merit is below a pre-determined value.

9. A method of making, including layout functions for, an integrated circuit according to claim 6, wherein:

the second pre-determined constraint is that the total number of cells within a cluster may not exceed a pre-determined number.

10. A method of making, including layout functions for, an integrated circuit according to claim 6, wherein:

the distance between each neighboring pair of clusters C_i and C_j is determined according to the equation;

space="preserve" listing-type="equation">dist(C.sub.i,C.sub.j)=max{dist(c.sub.k,c.sub.l)|.sub.∀

(c.sbsb.k.sub.ε

C.sbsb.i.sub.,c.sbsb.l.sub.ε

c.sbsb.j.sub.) }

where;

c_k is a cell k within cluster C_i, c_l is a cell l within cluster C_j, and dist(c_k,c_l) is the distance from cell c_k to cell c_l.