Patent US3715416A successfully refreshed from Google Patents.
Patent US3046550A successfully refreshed from Google Patents.
US5202840A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for partitioning of connected circuit components before placement in one or more integrated circuits
Assignee: NXP BV
•
Filing: 1990-12-19
•
Granted: 1993-04-13
•
Expires: 2010-12-19
Abstract
Abstract In a method for partitioning components of an integrated circuit into clusters in preparation for placement of the clusters onto an integrated circuit, a connectivity cost is assigned to every pair of connected components. Then, beginning with a pair of connected components with a lowest assigned connectivity cost and proceeding to a pair of connected components with a highest assigned connectivity cost, the components are placed in a cluster tree so that when merging cluster tree nodes, a cluster tree node with a higher connectivity cost is made a parent cluster tree node of a cluster tree node with a lower connectivity cost. The cluster tree may then traversed to partition the components into clusters. The clusters can be optimized by moving individual components to clusters when such a move results in a lower incremental connectivity cost. Once the components have been partitioned into clusters, the clusters of components may be placed on an integrated circuit.
Inventors
- 👤 Dale M. Wong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 03:43
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
135 words
A computer implemented method for partitioning components of an integrated circuit into clusters in preparation for placement of the clusters onto an integrated circuit, the method implemented by a computer and comprising the steps of: (a) assigning, by the computer, a connectivity cost to every pair of connected components; (b) beginning with a pair of connected components with a lowest assigned connectivity cost and proceeding to a pair of connected components with a highest assigned connectivity cost, placing, by the computer, the components in a cluster tree so that when merging cluster tree nodes, a cluster tree node with a higher connectivity cost is made a parent cluster tree node of a cluster tree node with a lower connectivity cost; and, (c) traversing, by the computer, the cluster tree to partition the components into clusters.
Claim 2
Dependent Claim
135 words
A computer implemented method for partitioning components of an integrated circuit into clusters in preparation for placement of the clusters onto an integrated circuit, the method implemented by a computer and comprising the steps of: (a) assigning, by the computer, a connectivity cost to every pair of connected components; (b) beginning with a pair of connected components with a lowest assigned connectivity cost and proceeding to a pair of connected components with a highest assigned connectivity cost, placing, by the computer, the components in a cluster tree so that when merging cluster tree nodes, a cluster tree node with a higher connectivity cost is made a parent cluster tree node of a cluster tree node with a lower connectivity cost; and, (c) traversing, by the computer, the cluster tree to partition the components into clusters.
Claim 3
Dependent Claim
24 words
A computer implemented method as in claim 1 wherein the connectivity cost in step (a) is calculated using the formula: cost=(total.sub.-- connections--total.sub.-- interconnections)/total.sub.-- connections.
Claim 4
Dependent Claim
157 words
A computer implemented method as in claim 1 wherein step (b) includes the following substeps: (b.1) sorting the pairs of connected components based on the connectivity cost associated with each pair; and, (b.2) for each pair of connected components beginning with the pair of connected components with the lowest assigned connectivity cost and proceeding to the pair of connected components with the highest assigned connectivity cost, if both components in the pair of connected components are not in a same class of connected components, performing the following substep: (b.2.1) merging a first class containing a first component of the pair of connected components into a second class containing a second component of the pair of connected components to form a cluster tree node and making the first class a child cluster tree node of the cluster tree node when a connectivity cost of the first class is not greater than a connectivity cost of the second class.
Claim 5
Dependent Claim
21 words
A computer implemented method as in claim 3 wherein in substep (b.1) the sorting is done using a heap sort algorithm.
Claim 6
Dependent Claim
24 words
A computer implemented method as in claim 3 wherein the connectivity cost in step (a) is calculated using the formula: cost=(total.sub.-- connections--total.sub.-- interconnections)/total.sub.-- connections.
Claim 7
Dependent Claim
37 words
A computer implemented method as in claim 3 additionally comprising the step of: (d) optimizing, by the computer, the clusters by moving individual components to clusters when such a move results in a lower incremental connectivity cost.
Claim 8
Dependent Claim
23 words
A computer implemented method as in claim 6 additionally comprising the step of: (e) placing the clusters of components on an integrated circuit.
Claim 9
Dependent Claim
22 words
A computer implemented method as in claim 3 wherein in step (c) a criterion used in partitioning components is size of cluster.
Claim 10
Dependent Claim
28 words
A computer implemented method as in claim 3 wherein in step (c) a criterion used in partitioning components is a maximum number of external connections from each cluster.
Claim 11
Dependent Claim
22 words
A computer implemented method as in claim 3 wherein in step (c) a criterion used in partitioning components is a packaging cost.
Claim 12
Dependent Claim
34 words
A computer implemented method as in claim 3 wherein the substep (b.2) the connectivity cost for each class is a maximum of connectivity costs associated with a pair of connected components in the class.
Claim 13
Dependent Claim
31 words
A computer implemented method as in claim 3 wherein in substep (b.2) the connectivity cost for each class is calculated by summing connectivity costs for all component pairs in the class.
Claim 14
Dependent Claim
74 words
A computer implemented method as in claim 3 wherein in substep (b.2) the connectivity cost for a class is calculated by subtracting a number of connections which are connected to at least two components in the class from a number of connections which are connected to at least one component in the class and dividing a resulting difference by the number of connections which are connected to at least one component in the class.
Claim 15
Dependent Claim
37 words
A computer implemented method as in claim 1 additionally comprising the step of: (d) optimizing, by the computer, the clusters by moving individual components to clusters when such a move results in a lower incremental connectivity cost.
Claim 16
Dependent Claim
23 words
A computer implemented method as in claim 14 additionally comprising the step of: (e) placing the clusters of components on an integrated circuit.
Claim 17
Dependent Claim
22 words
A computer implemented method as in claim 1 wherein the step (c) a criterion used in partitioning components is size of cluster.
Claim 18
Dependent Claim
28 words
A computer implemented method as in claim 1 wherein in step (c) a criterion used in partitioning components is a maximum number of external connections from each cluster.
Claim 19
Dependent Claim
22 words
A computer implemented method as in claim 1 wherein in step (c) a criterion used in partitioning components is a packaging cost.
References Cited (Backward Citations)
UST944001I4
Cited
US4495559A
Cited
US4593363A
Cited
US4890238A
Cited
US4908772A
Cited
US4815003A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-04-12 | 1996-10-12 | 1997-04-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-04-12 | 2000-10-12 | 2001-04-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-04-12 | 2004-10-12 | 2005-04-13 | $7700.00 | Window Closed / Lapsed |