US5661663A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Physical design automation system and method using hierarchical clusterization and placement improvement based on complete re-placement of cell clusters
Assignee: Bell Semiconductor LLC
•
Filing: 1995-03-24
•
Granted: 1997-08-26
•
Expires: 2015-03-24
Abstract
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.
Inventors
- 👤 Ranko Scepanovic
- 👤 James S. Koford
- 👤 Valeriy B. Kudryavtsev
- 👤 Alexander E. Andreev
- 👤 Stanislav V. Aleshin
- 👤 Alexander S. Podkolzin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 17:30
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
116 words
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.
Claim 2
Independent Claim
116 words
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.
Claim 3
Dependent Claim
47 words
A method as in claim 1, in which step (a) comprises the substeps of: (a1) representing said cells and said interconnects as a hypergraph; and (a2) converting said hypergraph into a graph in which said cells are represented by vertices and said interconnects are represented by edges.
Claim 4
Dependent Claim
17 words
A method as in claim 2, wherein said edges are defined in accordance with a predetermined function.
Claim 5
Dependent Claim
18 words
A method as in claim 3, wherein said predetermined function comprises defining said edges in a chain configuration.
Claim 6
Dependent Claim
18 words
A method as in claim 3, wherein said predetermined function comprises defining said edges in a star configuration.
Claim 7
Dependent Claim
18 words
A method as in claim 3, wherein said predetermined function comprises defining said edges in a tree configuration.
Claim 8
Dependent Claim
59 words
A method as in claim 1, in which step (a) comprises the substeps of: (a1) creating disjoint clusters of said cells in accordance with a first predetermined function to produce said lowest level; and (a2) merging clusters of each successively lower level in accordance with a second predetermined function to produce said clusters of each respective successively higher level.
Claim 9
Dependent Claim
34 words
A method as in claim 7, wherein said first predetermined function comprises creating each disjoint cluster as including a selected cell, and cells that are connected to said selected cell by one interconnect respectively.
Claim 10
Dependent Claim
15 words
A method as in claim 7, wherein said second predetermined function comprises a min-cut operation.
Claim 11
Dependent Claim
64 words
A method as in claim 9, in which step (a2) comprises the substeps, for each cell, of: (i) computing a first number of intra-cluster interconnects; (ii) computing a second number of inter-cell interconnects; and (iii) if said second number is larger than said first number, moving said cell to a cluster to which said cell is connected by a largest number of inter-cell interconnects.
Claim 12
Dependent Claim
40 words
A method as in claim 7, in which step (a) further comprises the substep of: (a3) iteratively repeating step (a2) for each level until said level comprises a number of cells or clusters from lower levels within a predetermined range.
Claim 13
Dependent Claim
20 words
A method as in claim 11, in which said predetermined range is approximately 50-100 cells or clusters from lower levels.
Claim 14
Dependent Claim
34 words
A method as in claim 7, in which step (a) further comprises the substep of: (a3) performing step (a2) for progressively higher levels until a highest level is produced which consists of one cluster.
Claim 15
Dependent Claim
45 words
A method as in claim 1, wherein step (b) comprises the substeps, for each level of clusters, the steps of: (b1) generating an initial placement of said clusters; and (b2) modifying said initial placement in accordance with a predetermined function to produce an improved placement.
Claim 16
Dependent Claim
72 words
A method as in claim 1, wherein modifying cell placement based on a predetermined gravity point adjustment function comprises: (i) computing a new gravity point for each cluster based on the current gravity point and a number of interconnects connecting cluster vertices, wherein clusters are modeled as masses and interconnects are modeled as springs pulling clusters together; and (ii) moving each cluster from said current gravity point to said new gravity point.
Claim 17
Dependent Claim
57 words
A method as in claim 15, in which step (i) further comprises, for each cluster, computing said new gravity point in accordance with directions and distances from said current gravity point to said current gravity points of other clusters to which said cluster is connected, and numbers of interconnects that connect said cluster to said other clusters.
Claim 18
Dependent Claim
21 words
A method as in claim 15, further comprising: (iii) iteratively repeating steps (i) and (ii) until a predetermined criterion is satisfied.
Claim 19
Dependent Claim
71 words
A method as in claim 17, in which step (iii) comprises the substeps, performed after each iteration of steps (i) and (ii), of: (A) computing a quality factor of said placement of said clusters of said level; and (B) iteratively repeating steps (i) and (ii) if said computed quality factor has a value that is different from a computed quality factor of a previous iteration by more than a predetermined value.
Claim 20
Dependent Claim
26 words
A method as in claim 18, wherein said quality factor is a total length of said interconnects of said placement of said clusters of said level.
Claim 21
Dependent Claim
62 words
A method as in claim 1, in which step (c) comprises the substeps, for each cluster of said lowest level, of: (c1) calculating positions of said cells in a first direction; and (c2) placing said cells along lines which extend in a second direction that is perpendicular to said first direction in increasing order of said calculated positions in said first direction.
Claim 22
Dependent Claim
125 words
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.
Claim 23
Dependent Claim
125 words
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.
Claim 24
Dependent Claim
52 words
A system as in claim 21, in which the tree construction means comprises: cell representation means for representing said cells and said interconnects as a hypergraph; and graph conversion means for converting said hypergraph into a graph in which said cells are represented by vertices and said interconnects are represented by edges.
Claim 25
Dependent Claim
17 words
A system as in claim 22, wherein said edges are defined in accordance with a predetermined function.
Claim 26
Dependent Claim
20 words
A system as in claim 23, wherein said predetermined function comprises means for defining said edges in a chain configuration.
Claim 27
Dependent Claim
20 words
A system as in claim 23, wherein said predetermined function comprises means for defining said edges in a star configuration.
Claim 28
Dependent Claim
20 words
A system as in claim 23, wherein said predetermined function comprises means for defining said edges in a tree configuration.
Claim 29
Dependent Claim
63 words
A system as in claim 21, in which the tree construction means comprises: pre-clusterization means for creating disjoint clusters of said cells in accordance with a first predetermined function to produce said lowest level; and cluster modification means for merging clusters of each successively lower level in accordance with a second predetermined function to produce said clusters of each respective successively higher level.
Claim 30
Dependent Claim
37 words
A system as in claim 27, in which the first predetermined function comprises means for creating each disjoint cluster as including a selected cell, and cells that are connected to said selected cell by one interconnect respectively.
Claim 31
Dependent Claim
22 words
A system as in claim 27, in which the second predetermined function comprises means for merging said clusters using a min-cut operation.
Claim 32
Dependent Claim
72 words
A system as in claim 29, in which the cluster modification means comprises: first computation means for computing, for each cell, a first number of intra-cluster interconnects; second computation means for computing a second number of inter-cluster interconnects; and cell movement means for, if said second number is larger than said first number, moving said cell to a cluster to which said cell is connected by a largest number of inter-cell interconnects.
Claim 33
Dependent Claim
46 words
A system as in claim 27, in which the tree construction means further comprises: control means for controlling the cluster modification means to iteratively merge clusters of each level until said level comprises a number of cells or clusters from lower levels within a predetermined range.
Claim 34
Dependent Claim
20 words
A system as in claim 31, in which said predetermined range is approximately 50-100 cells or clusters from lower levels.
Claim 35
Dependent Claim
40 words
A system as in claim 27, in which the tree construction means further comprises: control means for controlling the cluster modification means to merge clusters for progressively higher levels until a highest level is produced which consists of one cluster.
Claim 36
Dependent Claim
46 words
A system as in claim 21, in which the cluster placement means further comprises: initial placement generation means for generating an initial placement of said clusters; and placement modification means for modifying said initial placement in accordance with a predetermined function to produce an improved placement.
Claim 37
Dependent Claim
90 words
A system as in claim 21, wherein modifying cell placement based on a predetermined gravity point adjustment function comprises: new gravity point computation means for computing a new gravity point for each cluster in accordance with said current gravity points and said interconnects based on the current gravity point and a number of interconnects connecting cluster vertices, wherein clusters are modeled as masses and interconnects are modeled as springs pulling clusters together; and cluster movement means for moving each cluster from said current gravity point to said new gravity point.
Claim 38
Dependent Claim
62 words
A system as in claim 35, in which: the new gravity point computation means comprises means for computing, for each cluster, said new gravity point in accordance with directions and distances from said current gravity point to said current gravity points of other clusters to which said cluster is connected, and numbers of interconnects that connect said cluster to said other clusters.
Claim 39
Dependent Claim
34 words
A system as in claim 35, in which the cluster placement means further comprises: control means for controlling the placement modification means to iteratively modify said initial placement until a predetermined criterion is satisfied.
Claim 40
Dependent Claim
70 words
A system as in claim 37, in which the control means comprises: quality computation means for computing a quality factor of said placement of said clusters of each level; and iteration means for controlling the placement modification means to iteratively modify said initial placement if said computed quality factor has a value that is different from a computed quality factor of a previous iteration by more than a predetermined value.
Claim 41
Dependent Claim
26 words
A system as in claim 38, wherein said quality factor is a total length of said interconnects of said placement of said clusters of said level.
Claim 42
Dependent Claim
64 words
A system as in claim 21, in which the cell placement means comprises: calculation means for calculating positions of said cells in each cluster of said lowest level in a first direction; and means for placing said cells along lines which extend in a second direction that is perpendicular to said first direction in increasing order of said calculated positions in said first direction.
Claim 43
Dependent Claim
31 words
A system as in claim 21, in which the tree construction means, cluster placement means and cell placement means collectively comprise a parallel processing system including a plurality of parallel processors.
References Cited (Backward Citations)
US4577276A
Cited
US4908772A
Cited
US4918614A
Cited
US4815003A
Cited
US5239465A
Cited
US5202840A
Cited
US5521837A
Cited
US5557533A
Cited
US5568636A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-25 | 2001-02-24 | 2001-08-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-25 | 2005-02-24 | 2005-08-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-25 | 2009-02-24 | 2009-08-26 | $7700.00 | Window Closed / Lapsed |